Strict Minimum Message Length (SMML) inference is an information-theoretic criterion for inductive inference introduced by Wallace and Boulton and is known to possess several desirable statistical properties. In this paper we examine its computational complexity. We give an efficient algorithm for the binomial case and indeed for any SMML problem that is essentially one-dimensional in character. The problem in general is shown to be NP-hard. A heuristic is discussed which gives good results for binomial and trinomial SMML inference. The complexity of the trinomial case remains open and is worth further investigation.

The notion of algorithmic complexity was developed by Kolmogorov (1965) and Chaitin (1966) independently of one another and of Solomonoff's notion (1964) of algorithmic probability. Given a Turing machine T, the (prefix) algorithmic complexity of a string S is the length of the shortest input to T which would cause T to output S and stop. The Solomonoff probability of S given T is the probability that a random binary string of 0s and 1s will result in T producing an output having S as a prefix. We attempt to establish a parallel between a restricted (two-part) version of the Kolmogorov model and the minimum message length approach to statistical inference and machine learning of Wallace and Boulton (1968), in which an ‘explanation’ of a data string is modelled as a two-part message, the first part stating a general hypothesis about the data and the second encoding details of the data not implied by the hypothesis. Solomonoff's model is tailored to prediction rather than inference in that it considers not just the most likely explanation, but it also gives weights to all explanations depending upon their posterior probability. However, as the amount of data increases, we typically expect the most likely explanation to have a dominant weighting in the prediction.

We discuss Rissanen's scheme of ‘complete coding’ in which a two-part data code is further shortened by conditioning the second part not only on the estimates, but also on the fact that these estimates were preferred to any others. We show that the scheme does not lead to improved estimates of parameters. The resulting message lengths may validly be employed to select among competing model classes in a global hypothesis space, but not to select a single member of the chosen class. A related coding scheme is introduced in which the message commences by encoding an ancillary statistic, and then states parameter estimates using a code conditioned on this statistic. The use of Jeffreys priors in MDL codes is questioned and the resulting normalization difficulties and violations of the likelihood principle are discussed. We argue that the MDL objective of avoiding Bayesian priors may be better pursued by other means.

We would like to thank all the discussants for their contributions. Our paper attempts only a first step towards a satisfactory linkage between complexity theory and coding-based inference and these discussions will help to blaze the paths for future exploration. We also take this opportunity to remind the reader that, in our opinion, MDL and MML agree on many, many points. While we certainly disagree with Dr Rissanen and he with us on quite a few points, we certainly acknowledge that these disagreements would understandably appear both infrequent and minor from the perspective of someone who knew relatively little about MDL and MML.

Intrinsic classification, or unsupervised learning of a classification, was the earliest application of what is now termed minimum message length (MML) or minimum description length (MDL) inference. The MML algorithm ‘Snob’ and its relatives have been used successfully in many domains. These algorithms treat the ‘things’ to be classified as independent random selections from an unknown population whose class structure, if any, is to be estimated. This work extends MML classification to domains where the ‘things’ have a known spatial arrangement and it may be expected that the classes of neighbouring things are correlated. Two cases are considered. In the first, the things are arranged in a sequence and the correlation between the classes of successive things modelled by a first-order Markov process. An algorithm for this case is constructed by combining the Snob algorithm with a simple dynamic programming algorithm. The method has been applied to the classification of protein secondary structure. In the second case, the things are arranged on a two-dimensional (2D) square grid, like the pixels of an image. Correlation is modelled by a prior over patterns of class assignments whose log probability depends on the number of adjacent mismatched pixel pairs. The algorithm uses Gibbs sampling from the pattern posterior and a thermodynamic relation to calculate message length.

Fast algorithms for generating pseudorandom numbers from the unit-normal and unit-exponential distributions are described. The methods are unusual in that they do not rely on a source of uniform random numbers, but generate the target distributions directly by using their maximal-entropy properties. The algorithms are fast. The normal generator is faster than the commonly used Unix library uniform generator “random” when the latter is used to yield real values. Their statistical properties seem satisfactory, but only a limited suite of tests has been conducted. They are written in C and as written assume 32-bit integer arithmetic. The code is publicly available as C source and can easily be adopted for longer word lengths and/or vector processing.

A tightly coupled multiprocessor is being build in the Computer Science Department of Monash University. This paper discusses several mechanisms that support a uniform virtual memory for the multiprocessor. Some desirable properties of the virtual memory are the result of an unusual capability mechanism and the introduction of a money mechanism. The capability mechanism described also allows a simple, and flexible, solution to the confinement problem.

The information measure is an objective measure of the quality of a classification and results from an information transmission view of the classification problem. So far information measures have only been derived for the case where an explicit assumption is made about the form of the distribution of attribute values within a class. One important method which involves no such explicit assumption is single link. In this paper we derive a new information measure which is optimised by classifications produced by the single link method. By investigating the properties of this information measure we are able to gain more insight into the single link method and also determine the type of problem to which it best applies.

The problem addressed is: the occupancy, by non-negative integers, of a rectangular array of given size when the row sums and column sums are all fixed. In general, a single expression for the number of array element combinations which covers all combinations of row and column sums cannot be found. Thus two algorithms which systematically count all element combinations are presented, the first applying to arrays with only two columns and the second to arrays with any number of rows and columns. The two-column algorithm is then used to derive expressions for the number of array element combinations of arrays having three rows and two columns. Five different expressions are required to cover all combinations of row and column totals.

The information measure has been developed as a criterion of merit for intrinsic classifications. The information measure for non-hierarchic classifications has been described previously and a program developed which searched for that classification optimising the information measure. However, hierarchic classifications are often of practical importance and this paper develops the information measure for hierarchic classifications. Two algorithms are outlined for generating hierarchic classifications which minimise the information measure. One of these has been programmed and first tests show a good agreement with conventional taxonomy.

In a previous paper (Wallace & Boulton, 1968) the information measure was derived. It is designed to measure the objective goodness of a nonhierarchical taxonomic classification and can be used to choose the best of a number of different classifications of the one data set. The information measure can also form the basis of a classification algorithm which searches directly for that classification with the best information measure. In the present paper such a classification algorithm is described together with an ALGOL program called Snob incorporating this algorithm.

This paper derives a measure of the goodness of a classification based on information theory. A classification is regarded as a method of economical statistical encoding of the available attribute information. The measure may be used to compare the relative goodness of classifications produced by different methods or as the basis of a classification procedure. A classification program, ‘SNOB’, has been written for the University of Sydney KDF 9 computer, and first tests show good agreement with conventional taxonomy.

The I/O control of a computer may adopt various strategies for serving competing requests from peripheral channels for access to a single core memory. The strategy adopted places some limit on the peripheral configurations which may be simultaneously active. An “ideal” strategy is exhibited which imposes no constraint other than that implied by the finite speed of the core memory, but it is expensive to implement. Limits on configurations are derived for the ideal, first come-first served, round-robin and priority systems. It is shown that the first come-first served and round-robin systems have little or no advantage over a random choice. The KDF9 at the University of Sydney, which was delivered with a first come-first served system, has been modified to incorporate a priority system. The new system uses 48 fewer circuit boards, but allows the attachment of high-rate channels which otherwise could not be accommodated.

Field-recorded data are often most conveniently recorded on magnetic tapes without interblock gaps. Gapless tapes cannot be read by certain types of computers. A simple modification to a KDF 9 computer enables it to transcribe from gapless to conventional format as a time-shared monitor operation. The counter which increases peripheral transfer addresses and detects the completion of a block is time-shared by all channels on the KDF 9. It was modified so that for any channel which, in requesting a core memory access, indicates that it is engaged in a gapless read" carries out of the 64's digit of the counter are suppressed, and any change of the 64's digit causes an interrupt to the permanently resident monitor program (Director). Thus, if an input transfer is set up on a channel with initial core memory address an exact multiple of 128, and the channel is made to signal that it is reading gapless tape, the reading will proceed indefinitely, repeatedly cycling over the same 128 word core area, and causing an entry to Director after every 64 words.

The integration method used in digital differential analyzers suffers from both truncation and round-off errors. It is shown that, if trapezoidal corrections are employed, the latter dominates. The round-off errors in successive steps of the integration are shown to be correlated whenever the function being integrated has a slope which passes through a rational fraction of small denominator. However, an analysis is presented to show that in general the correlation does not greatly affect the total round-off error. Some special cases are shown to suffer from anomalously high round-off error.

It is suggested that the economics of present large-scale scientific computers could benefit from a greater investment in hardware to mechanize multiplication and division than is now common. As a move in this direction, a design is developed for a multiplier which generates the product of two numbers using purely combinational logic, i.e., in one gating step. Using straightforward diode-transistor logic, it appears presently possible to obtain products in under 1, μsec, and quotients in 3 μsec. A rapid square-root process is also outlined. Approximate component counts are given for the proposed design, and it is found that the cost of the unit would be about 10 per cent of the cost of a modern large-scale computer.