The Shortest Universal Turing
Machine Implementation Contest

Current and previous records

Subscribe to the newsletter

The shortest implementations will be posted in descending size order. The winner will earn the privilege of having written the shortest universal Turing machine implementation (in C/C++ language ).

The universal machine implementation in C/C++ language must be capable of simulating any Turing machine provided with an empty tape (filled with zeros) following the usual 5-tuple formalism described in the next section. The tests for the submitted candidates will include the computation of all the known busy beaver Turing machines (we call it the busy beaver test).

For any new submission n, K_sc(n), K_c(n), K_cc(n) < K_sc(n-1), K_c(n-1), K_cc(n-1) in order to be included in the list above. Download the program-size calculator (written in Mathematica).

Send your submissions to hector.zenil [at-] lifl.fr and/or jean-paul.delahaye [at-] lifl.fr

The machine formalism Described by Alonzo Church and Stephen Cole Kleene in the 1930s, λ-calculus, is a formal system designed to investigate function definition, function application and recursion. λ-calculus emerged as a useful tool in the investigation of problems in computability, and together with Gödel's Type System it is a paradigm of computer programming. Several computer languages capable of functional programming such as Haskell, Lisp, Scheme, ML and Mathematica are based on those powerful ideas. Among other features, they can automatically infer the types of most values without requiring explicit type annotations. First described by Alan M. Turing in 1936, a Turing machine is an extremely basic abstract device for symbol manipulation which, despite its simplicity, can be adapted to simulate any other machine. A Turing machine that is able to simulate any other Turing machine is called a Universal Turing machine (UTM). Both Church and Turing used their constructions to give a negative answer to the Entscheidungsproblem and Turing proved that both formulations were equivalent. The Wolfram's Demonstrations project contains several visual examples of Turing machines. Some years later all these ideas have materialized in what nowadays we know as digital computers.

Alonzo Church

Alan Turing

For the purpose of this contest we must stick to a formalism providing a framework. We have chosen as formalism the one used in the busy beaver competition for Turing machines. In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine which, when given an empty tape writes the largest number of 1s on its tape before halting. This Demonstration shows the behavior, step by step, of all known busy beaver machines so far. In his 1962 paper[64], Tibor Radó introduces the busy beaver game. Since then, the Turing machine formalism for the busy beaver competition is as follows : The Turing machine runs on a 2-way unbounded tape filled with zeros (no blank symbol). At each step, two conditions : the machine's current "state" (instruction); and the tape symbol the machine's head is scanning

define each of the following :

Program-size complexity

Also called algorithmic complexity or Kolmogorov-Chaitin complexity, the program-size complexity K(s) of a string s can be measured by the length of the shortest program that produces s running on a universal Turing machine or in some fixed description language. We say that a program p is a description of string s on a Turing machine T if T(p)=s. The length of the shortest description is denoted by K(s)={ |p| : T(p)=s} with |p| the length of the program p. An example of a very short implementation with length size 158 operational characters producing the 2400 first decimal numbers of Pi written in ANSI C: int a=10000,b,c=8400,d,e,f[8401],g;main(){for(;b-c ;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+ d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b ;d*=b);}

Gregory Chaitin

All theorems in algorithmic information theory depend on additive constants, which depend on sizes of universal Turing machines. One might decide to encode a universal machine following a different computational model such as combinatory logic, a cellular automata or a Post tag-system, to name a few, in order to reduce the size length. However, because we are constraining the implementation to input/output in terms of a Turing machine (among other reasons because it gives sense to compare and test along different implementations, without affecting the research scope of the contest), the size of the translator/compiler that converts from one formalism to another may offset any gained decrease in size. We think that this is per se an interesting question.

Goals and motivation

The contest is based on the fact that program-size complexity is not computable, so it is always an open question whether a particular implementation of a universal machine is the shortest. We think that the contest will encourage (at least it is encouraging us) to do research on the possible size ratios between different computational models when forced to input/output as a particular model of computation (in this case a Turing machine).

Furthermore, even when by the invariance theorem we know that the shortest description of a string s under T1 is at most a constant number of bits longer than the shortest description under T2 because there is always a way to write a translator between T1 and T2, the length of an actual implementation is highly dependable on the chosen programming language, although we have recently suggested a way to overcome this problem and provide a stable definition of Kolmogorov-Chaitin complexity[19].

For instance, John Tromp's has written a short program universal binary lambda computer[71] in the quest of the utterly simple computer model using combinatorics and with the very purpose of this contest, to define and shed light over algorithmic information theory. Implemented in Haskell, the description and source code can be reached here.

Gregory Chaitin[6] himself has also written very short versions of self-delimiting universal Turing machines, this is the core fragment of his universal Turing machine written in (pure) Lisp:

define (U p) cadr try no-time-limit 'eval read-exp p
(U bits 'cons x cons y cons z nil)
(U append bits 'cons a debug read-exp
bits '(b c d))

The full version with further explanations can be found here.

In Mathematica, the function TuringMachine is a universal Turing machine implementation by itself but if one wants to avoid calling a function that does all the work, it is possible to write an impressively short universal Turing machine without any dubious call to a function. The shortest implementation, among three different implementations[75] of a universal Turing machine in Mathematica is:

s = 1; a[_] = 0; n = 0; Do[{s, a[n], d} = {s, a[n]} /. rule; n += d, {t}]

so one can, for example, simulate the 2,3 Wolfram Turing machine just by providing the rule {{1, 2} -> {1, 1, -1}, {1, 1} -> {1, 2, -1}, {1, 0} -> {2, 1, 1}, {2, 2} -> {1, 0, 1}, {2, 1} -> {2, 2, 1}, {2, 0} -> {1, 2, -1}} and setting a value for the number of steps t. This notebook contains the code above for 10000 steps and shows how the first 100 cells of the output tape looks like.

The fact that all these languages are Turing-equivalent means that, strictly speaking, you can write any program in any of them. However, implementations of a Turing machine in lower level or structured programming languages may require several lines of code. We think that the contest may shed some light about the relation of several models of computation, since if one chooses a particular language or model for an implementation, the compiler might turn out to be long enough to counteract any effort to reduce the total size of the implementation. To find it out and see how this happens we are randomly fixing a language and a model, bearing in mind that both ANSI C/C++ and a Turing machine are a very well known standard programming language and an and a very well known standard abstract machine, respectively.

The rules of the contest require the input/output to be as for a Turing machine, which obligates any implementation following any other model of computation to include a translator/compiler and figure out how to keep its implementation short enough. One may find perhaps that the translator together with the machine code will always approach the size of an implementation following the model of computation for which the input/output was designed. For example, there is a Lisp interpreter in C written by Kernighan and Ritchie and published in their The C Programming Language book, that one would require in order to compile the Greg Chaitin Turing machine written in Lisp in C language. There is also a Mathematica program able to interpret Chaitin's universal Turing machine in Lisp here. For an interesting account of the comparison between programming languages in terms of algorithms implementation length, read Paul Graham's Revenge of the Nerds[30] and his collection of canonical solutions to the same problem in a number of languages.

We think that by having several implementations one can start trying to figure out what the ratio between different models and translators can be and/or if there is certain convergence of several models of computation for which one could perhaps define some kind of "naturalness" in a given model behaving efficient and being at the same time short enough as we have suggested [19].

Implementation rules

In the spirit of the busy beaver competition[64] but related to our interest on program-size complexity after our own research on the program-size complexity of short sequences[17,18], we make the challenge of writing the shortest universal Turing machine implementation in C/C++ (and then the simpler in terms of program-size complexity). It can turn out to be a universal machine following other formalism such as a Post tag-system or λ-calculus implementation or a cellular automaton. However, any implementation must agree with the input/output syntax. The contest is open-ended. It is open to everyone. To enter, a competitor must submit a universal machine implementation with lesser size values than the latest published record in this page.

Andrei Kolmogorov

The size of a universal Turing machine implementation will be given by the combination of the size in bytes of the compiled executable file using g++ version 4.0.1 under Mac OS X 10.5.2 and the size in characters of the source file opened in any standard text editor (such as vi, pico or emacs). Only operational characters will be counted. An operational character is a non-space, non-part of a comment ASCII character disregarding variables and constant names lengths. In other terms, if an operational character is removed the source code would not compile. Variables and constant names count each for 1 character (so naming a variable longer or shorter does not affect the final calculation, but it does if less are required). So make your code legible by choosing self-explanatory variable names, indenting and commenting on the code. All other characters will be accounted for in ascertaining the final sum. The combination of the following sizes: the source code in characters (K_sc), the compiled file in bytes (K_c) and the compressed ZIP (K_cc) file in bytes (lossless data compression) of the compiled version using the Deflate algorithm, need to be lesser than the previous champion implementation in order to take its place in the ranking. Once the program submitted and accepted no further changes will be allowed but new submissions are always possible as long as it fulfills the desribed requirements.

A lower bound of the program-size length of the source code may be calculated with this Mathematica program. This Mathematica program will provide an approach to the actual operational-characters length of the source code but a manual inspection will be later conducted according to the rules described in this page after submission. This manual count will be mandatory for the final calculation whether or not it coincides with the previous approximation. We also strongly suggest to include a readme.txt file in the submission package explaining the important code of the machine implementation.

It must also manage the input/output properly, so that one need only provide the specific transition rules in order to get the output either in a file or directly on-screen with no further computation or decoding. Only the standard iostream ANSI C/C++ library is allowed in the competition, and only for input/output purposes. The output, then, must simply be the string written on the tape where the machine head went through in the same language than the input, along with an integer indicating the total number of steps before halting. For non-Turing machine implementations an embedded compiler has to be included such that one can still provide exactly the same input and get the expected output in the output form of a Turing machine in finite (and reasonable) time. We know this favors a native Turing machine implementation rather than any other kind since the Turing machine would not need any further I/O encoding, but we have to stick to some formalism in order to compare capabilities. If the encoding is simple enough in computational terms (so that the encoding is not evidently universal by itself) it will not count as part of the original program size.

The fact that we are requesting to output in a fixed form in a finite (and reasonable) time also stresses a time-complexity related issue of the implementations, which also plays a role in the formulation of the contest, motivating answers to the question of whether there is any practical trade-off between time and program-size complexity.

Referees will be the previous holders of the record themselves among with the organizers (all acting in good faith as there is nothing at stake but the honor of having encoded the shortest Turing machine bearing in mind the ultimate goal of sheding some light to the discussion in question).

In order to take part in this competition you must submit the source code which will be compiled using the compiler program and version specified above. It is important that you provide the documentation of your code, either in an attached file or as commented text in the source code file.

The invitation to participate, and eligibility to win the contest, is extended to everyone. Each submitter must agree to be bound and abide by the rules. Submissions remain the sole property of submitter(s), but should be released under the GNU General Public License (GPL) licence in order to grant permission to make it available in this web site for downloading and executing.

Bear in mind that the above rules, and that the essence of the challenge is to find ways of redesigning the code at the algorithmic level, not simply to redesign it aesthetically.

Send your submissions to hector.zenil [at-] lifl.fr and/or jean-paul.delahaye [at-] lifl.fr.

FAQs

Why the busy beaver test?

A busy beaver machine bb(n) is the most complex halting machine in its class of n-states Turing machines in terms of non-zero written symbols and number of steps, so if one is able to simulate a busy beaver it is likely to simulate any other simpler machine in the same class, including even non-halting machines.

The main test for each submitted candidate will be the computation in finite time of all known busy beaver values. We have chosen this test because we claim that:

Conjecture (Zenil): For all n>2, bb(n) the n-state busy beaver Turing machine, is a (weak)universal Turing machine.

If so, this conjecture characterizes an interesting countable infinite set of universal Turing machines containing a Turing machine for each state n with n>2.

However, even when the best way might be to check whether an implementation is a universal Turing machine is by analytical means (by analyzing the source code), the busy beaver test lets us also to test the input/output requirements while letting us check that there is no obvious flaws in their computation by producing all the exact known non-trivial values of Sigma(n) and S(n), i.e. producing the actual output in the expected number of steps for all the busy beavers machines.

Why might this be an interesting challenge?

There are several open questions related to the nature of the encoding/decoding process and the notion of universal computation. An interesting question is whether an implementation of a universal machine is efficient in terms of its code length compared to the encoding/decoding performance. The idea that a short description is only useful if we can reconstruct the string in a reasonable amount of time is captured by time-bounded complexity. It could turn out that when a universal machine implementation gets shorter the encoding/decoding of the input/output is longer and harder in terms of computation steps (time complexity) as intuiton would suggest. However, Neary and Woods[76,77] proved that some very small (weak)universal machines can compute in polynomial time, which means that these very short implementations can actually be efficient universal computing devices. This is a question that can be generalized to any nature of the input/output encoding or chosen computational model.

In the literature some authors use to make a technical distinction between machines that start with a blank tape as initial configuration and those that start with a non-blank (but still simple enough) initial configuration such as a periodic background[50]. An open question is whether any configuration of one type can be translated into the other via a simple compiler without adding states or symbols, and how the compiler would look like in terms of program-size and time complexity. Is there an effective and efficient encoding for each non-periodic encoding preserving universality? Will the encoding always be more complex if the machine is simpler? If so there is a relation to find out, if not we know that by adding states/symbols a non-blank configuration can become a blank one (it suffices to use the extra states/symbols to reproduce the original background). However, to our knowledge, the actual relation is currently unknown. It would be interesting, for instance, to find out if there is a precise polynomial (or exponential) trade-off between program-size complexity and computational complexity (time/space complexity) relating the encoding/decoding, the number of symbols/states necessary to convert one into another and among different computational formalisms. One can think about computational complexity (time/space complexity) and program-size complexity as two axes. Program-size complexity minimizing along one axis and time/space complexity along the second axis. Little work has been done on the simultaneous minimization and their actual relation, if any. We think our challenge is a good hands-on chance to think about these issues and perhaps shed some light to find an answer.

Some thoughts about the nature of different initial configurations and the foundations of universal computation at the decidability/universality frontier can be found (draft and incomplete version) in this Mathematica notebook or pdf.

What if nobody submits after a long time?

It would be interesting per se. Either nobody cares or any size improvement is harder to reach than expected. If the latter, perhaps the compiler always turns out to offset any effort (to know it is what the contest is about). Feel free to give us some feedback in the process (but send your code until you are sureit is ready to compete). We will keep people updated through the contest newsletter.

If you want to get sporadic updates on the status of this contest or get the new records notifications subscribe to the contest newsletter.

Acknowledgements

Several people have contributed to the improvement of this contest. We want to thank Parker Mills, Maurice Margenstern, Stephen Wolfram, Fritz Obermeyer, Heiner Marxen and Gustavo Lacerda for their comments and suggestions.

Organizers

Hector Zenil (LIFL, Paris 1, Carnegie Mellon U.)
Jean Paul-Delahaye (LIFL)

References

1. Blum, L., Cucker, F., Shub, M. and Smale, S. 'Complexity and Real Computation,' Springer, 1997.
2. Böerger, E, Grädel, E. and Gurevich, Y., 'The Classical Decision Problem,' Springer, Heidelberg, 1997.
3. Brady, A.H., 'The determination of the value of Rado's noncomputable function Sigma(k) for four-state Turing machines,' Mathematics of Computation, Vol. 40, No. 162 (April 1983), pp. 647-665. B, 1983.
4. Brady, A.H., The Busy Beaver Game and the Meaning of Life, p 237-254, appearing in Herken, Rolf (ed)., The Universal Turing Machine: A Half-Century Survey, 2nd edition, Springer-Verlag, Wien New York, 1995.
5. Chaitin, G., 'Foundations of Mathematics.' arXiv:math.HO/0203002v2, 2002.
6. Chaitin, G., J. 'On the length of programs for computing finite binary sequences,' Journal of the ACM, 13(4):547--569, 1966.
7. Chaitin, G., 'Meta Math! The Quest for Omega,' Atlantic Books, 2004.
8. Church, A., 'A Set of Postulates for the Foundation of Logic (Second Paper)', Annals of Mathematics, second series, 33, Princeton, 839-864, 1933.
9. Church, A., 'A Note on the Entscheidungsproblem,' Journal of Symbolic Logic, 1, 40-41; correction 1, Menasha, Wis., 101-102, 1936.
10. Church, A., 'An Unsolvable Problem of Elementary Number Theory,' American Journal of Mathematics, 58, Baltimore, 345-363, 1936.
11. Cobham, A., 'The Intrinsic Computational Difficulty of Functions,' Proceedings of the 1964 Congress for Logic, Mathematics, and Philosophy of Science, North-Holland, Amsterdam, 24-30, 1964.
12. Cook, S., 'The Complexity of Theorem Proving Procedures,' Proceedings of the Third Annual ACM STOC Symposium, Shaker Heights, Ohio, 151-158, 1971.
13. Davis, M. 'The Universal Computer: the Road from Leibniz to Turing,' W. W. Norton & Company, New York, 2000.
14. Davis, M. 'Computability and Unsolvability,' Dover Publications, 1985.
15. Davis, M. (Ed.) 'The Undecidable: Basic Papers on Undecidable Propositions,' Unsolvable Problems and Computable Functions. Dover Publications, 2004.
16. Davis, M. 'The Universal Computer: The Road from Leibniz to Turing,' W. W. Norton & Company, 2000.
17. Delahaye, JP and Zenil, H. On the Kolmogorov-Chaitin complexity for short sequences, in Cristian Calude (eds) 'Complexity and Randomness: From Leibniz to Chaitin'. World Scientific, 2007.
18. Delahaye, JP and Zenil, H. 'On the Kolmogorov-Chaitin complexity for short sequences (long version)'. arXiv:abs/0704.1043, 2007.
19. Delahaye, JP and Zenil, H. 'Towards a stable definition of Kolmogorov-Chaitin complexity', (submitted to Fundamenta Informaticae), 2008.
20. Delvenne, J.-C., Kurka, P. and Blondel, V.. Computational Universality in Symbolic Dynamical Systems, 'Lecture Notes in Computer Science: Machines, Computations, and Universality: 4th International Conference,' MCU 3354 (2005): 104-115, 2005.
21. Dewdney, A.K., 'A computer trap for the busy beaver, the hardest working Turing machine,' Scientific American, 251 (2), 10-17, 1984.
22. Dewdney, A.K., 'Busy beaver programs' in Scientific American, pages 19-23, August 1984, p. 23 March 1985 and p. 30 April 1985.
23. DeWilde, P.; Vandewalle, Joos P.L. (Eds.), 'Computer Systems and Software Engineering State-of-the-Art,' Springer, 1992.
24. Edmonds, J., 'Paths, Trees and Flowers', Canadian Journal of Mathematics, 17, Toronto, 449-467, 1965.
25. Enderton, H. B., 'A Mathematical Introduction to Logic,' Academic Press, New York, 1972.
26. Gacs, P. 'On the symmetry of algorithmic information,' Soviet Mathematics Doklady, 15:1477-1480, 1974.
27. Garey, M. and Johnson, DS.,'Computers and Intractability,' Freeman, New York, 1979.
28. Gödel, K., 'The Completeness of the Axioms of the Functional Calculus,' (1930) in van Heijenoort, 582-591, 1967.
29. Gödel, K., 'On Formally Undecidable Propositions of Principia Mathematica and Related Systems I,' (1931) in van Heijenoort, 592-617, 1967.
30. Graham, P., "Hackers and Painters: Big Ideas from the Computer Age", O'Reilly, 2004.
31. Grigorieff, Serge and Marion, Jean-Yves, 'Kolmogorov complexity and non-determnism,' Theoretical Computer Science, Volume 271 , Issue 1-2, pag: 151-180, 2002
32. Hartmanis, Juris, 'Overview of computational Complexity Theory' in J. Hartmanis, ed., Computational Complexity Theory, American Mathematical Society, Providence, 1-17, 1989.
33. Herken, R. 'The Universal Turing Machine: A Half-Century Survey,' Springer Verlag, 1995.
34. Hilbert and Ackermann, 1928/1938, Grundzüge der theoretischen Logik, Springer. English translation of the 2nd edition: Principles of Mathematical Logic, Chelsea Publishing Company, New York, 1950.
35. Hodges, Andrew, 'Alan Turing: the Enigma,' Random House, London, 1992.
36. Hofstadter, Douglas, 'Gödel, Escher, Bach: an Eternal Golden Braid,' Basic Books, New York, 1979.
37. Hopcroft, John E., 'Turing Machines', Scientific American, 250(5), New York, 70-80, 1984.
38. Hutter, M. On Universal Prediction and Bayesian Confirmation. Theoretical Computer Science, 384:1, 33-48, 2007.
39. Karp, Richard, 'Reducibility Among Combinatorial Problems', in Complexity of Computations, R.E. Miller and J.W. Thatcher, eds., Plenum Press, New York, 85-104, 1972.
40. Kleene, Stephen C., 'Introduction to Metamathematics,' North-Holland Publishing Company, 1952.
41. Kleene, Stephen C., 'A Theory of Positive Integers in Formal Logic,' American Journal of Mathematics, 57, Baltimore, 153-173, 219-244, 1935.
42. Kleene, Stephen C., 'Introduction to Metamathematics,' Van Nostrand, Princeton, 1950.
43. Kolmogorov, A. N. 'Combinatorial foundations of information theory and the calculus of probabilities,' Russian Mathematical Surveys, 38(4):27--36, 1983.
44. Kolmogorov, A. N. 'Three approaches to the quantitative definition of information,' Problems of Information and Transmission, 1(1):1--7, 1965.
45. Levin, Leonid, 1973, 'Universal search problems,' Problemy Peredachi Informatsii, 9(3), 265-266; partial English translation in: B.A.Trakhtenbrot, 'A Survey of Russian Approaches to Perebor (Brute-force Search) Algorithms,' IEEE Annals of the History of Computing, 6(4), Los Alamitos, CA, 384-400, 1984.
46. Levin, L. 'Laws of information conservation (non-growth) and aspects of the foundation of probability theory,' Problems of Information Transmission, 10(3):206--210, 1974.
47. Li M. and Vitanyi. 'An Introduction to Kolmogorov Complexity and its Applications'. Springer, New York, 2nd edition, 1997.
48. Lin, S. and Radó, T., 'Computer Studies of Turing Machine Problems,' Journal of the Association for Computing Machinery, Vol. 12, No. 2, pp. 196-212, 1965.
49. McCarthy, J. 'Programs with common sense, Paper presented at the Symposium on the Mechanization of Thought Processes,' National Physical Laboratory, Teddington, England, Nov. 24-27, Published in Proceedings of the Symposium by H. M. Stationery Office, 1958.
50. McCarthy, J. 'Recursive functions of symbolic expressions and their computation by machine, Part I,' communications of the ACM archive, volume 3, issue 4, Pages: 184 - 195, 1960.
51. Machlin, R. and Stout, Quentin F.,' The complex behavior of simple machines,' Physica D, No. 42, pp. 85-98, 1990.
52. Margenstern, M. 'Frontier between Decidability and Undecidability: A Survey.' Theoretical Computer Science 231, no. 2 217-251, 2000.
53. Markov, A.A., 'The Theory of Algorithms,' American Mathematical Society Translations, series 2, 15, Providence, 1-14.
54. Marxen, H. and Buntrock, J., 'Attacking the Busy Beaver 5,' Bulletin of the EATCS, No 40, pp. 247-251, 1990.
55. Matiyasevich, Yu. 'Hilbert's 10th Problem,' MIT Press, 1993.
56. Minsky, M. 'Computation: Finite and Infinite Machines. Prentice-Hall,' Inc., 1967.
57. Minsky, M. 'Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines.' Annals of Mathematics 74, no. 3: 437-453, 1961.
58. Neary, T. and Woods, D. 'Small fast universal Turing machines,' Theoretical Computer Science, Volume 362, Issues 1-3, 11, pp 171-195., 2006.
59. Neary, T. Small polynomial time universal Turing machines. In T. Hurley, A. Seda, et al., editors, Fourth Irish Conference on the Mathematical Foundations of Computer Science and Information Technology, pages 325–329, Cork, Ireland, MFCSIT. Invited paper, 2006.
60. Papadimitriou, C. H., 'Computational Complexity,' Addison-Wesley, Reading, Mass., 1994.
61. Pascal M., 'Small Turing machines and generalized busy beaver competition,' Theoretical Computer Science
62. Post, E., 'Finite Combinatory Processes--Formulation 1.' Journal of Symbolic Logic 1, no. 3: 103-105, 1936.
63. Post, E. 'Recursive Unsolvability of a Problem of Thue.' Journal of Symbolic Logic 12, no. 3: 1-11, 1947.
64. Radó, Tibor, On non-computable functions, Bell Systems Tech. J. 41, 3.1962.
65. Rogers, H. Jr., 'Theory of Recursive Functions and Effective Computability,' 1967, McGraw-Hill, New York.
66. Rogozhin, Yu. 'Small Universal Turing Machines.' Theoretical Computer Science 168, no. 2 (1996): 215-240.
67. Shannon, C. 'A Universal Turing Machine with Two Internal States.' Automata Studies. Princeton University Press (1956): 157-165.
68. Solomonoff, R. 'A formal theory of inductive inference: Parts 1 and 2. Information and Control,' 7:1--22 and 224--254, 1964.
69. Sutner, K. 'Cellular Automata and Intermediate Degrees.' Poster presented at NKS 2004.
70. Sutner, K. 'Universality and Cellular Automata.' In Lecture Notes in Computer Science: Machines, Computations, and Universality: 4th International Conference, MCU 3354: 50-59, 2005.
71. Tromp, J., Binary Lambda Calculus and Combinatory Logic, 'Kolmogorov Complexity and Applications.' Marcus Hutter, in Wolfgang Merkle and Paul M.B. Vitanyi (eds.), Dagstuhl Seminar Proceedings, Internationales Begegnungs und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006.
72. Turing, A. M., 'On Computable Numbers, with an Application to the Entscheidungsproblem', Proceedings of the London Mathematical Society, 2(42), London, 230-265, 1936-7.
73. Turing, A. "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction." Proceedings of the London Mathematical Society Series 2, 43: 544-546, 1938.
74. Whitehead, Alfred North and Bertrand Russell, 'Principia Mathematica,' Cambridge University Press, Cambridge, 1910.
75. Wolfram, S. A New Kind of Science. Wolfram Media, 2002.
76. Woods, D. and Neary, T., 'On the time complexity of 2-tag systems and small universal Turing machines', FOCS - 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Berkeley, California, pp 439-448, 2006.
77. Woods, D. and Neary, T., 'Remarks on the computational complexity of small universal Turing machines'. MFCSIT 2006. Cork, Ireland. pp 334-338, 2006.
78. Woods, D. and Neary, T., 'The complexity of small universal Turing machines,' Computation and Logic in the Real World Third Conference of Computability in Europe, CiE 2007, Siena, Italy, June 2007. Springer Lecture Notes in Computer Science (LNCS) vol. 4497. S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (eds), 2007.
79. Zvonkin A. and Levin, L. 'The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms,' Russian Mathematical Surveys, 25(6):83--124, 1970.