

The Shortest Universal
Machine Implementation
Subscribe to the Newsletter
Current and previous records
The shortest implementations will be posted in descending order of size. The winners earn the privilege of having written the shortest implementation of a universal machine (in the chosen language). Read the FAQs for more information.
The universal machine implementation in language must be capable of simulating any Turing machine starting from an 'empty' tape (filled with zeros) following the usual 5tuple formalism described in the formalism section. Submitted entries will include be tested by computing all the known busy beaver 2symbol Turing machines (we call this the busy beaver test, for an explanation see the FAQs section).
In order to be included in the table below, any new record holder n+1 should fulfill: K_sc(n+1) < K_sc(n), where K_sc(n) is the programsize complexity measured in number of source code operational characters (for an explanation see the Rules and FAQs sections) of the current record holder with submission number n. For an automatic approximation to K_sc download this basic programsize calculator (written in Mathematica).
submission
number 
submission date 
last update* 
author(s) name(s) 
file name
(click to download) 
K_sc
source code size
(operational characters) 
K_c
compiled size
(in bytes) 
K_cc
compiled compressed size
(in bytes)

author(s) comments (including updates) 
1 
15Dec08 



638 
13,224 
2,240 

2 
23Dec08 

Hein Hundal 

436 
13,052 
1,822 

3 
24Dec08 



340 
13,152 
2,085 

4 
2Jan09 



320 
13,068 
1,751 

5 
7Jan09 



284 
13,028 
1,738 

6 
20Jan09 



208 
12,928 
1,781 

7 
28Jan09 



285 



* To know what kind of updates authors are allowed to make read the FAQs section.
The code of the current shortest (285 characters long) universal Turing machine implementation in C/C++ (by Alex Stangl and John Tromp) is:
#include<iostream>
#define Z atoi(b[a++])
int main(int a,char**b){
int c=a=1,d=0,e=2;
char*f,*g=0,*h,*i=0;
while(c){if(i<=gi>=g+e)f=g,g=(char*)calloc(e,2),i=f?(memcpy(g+e/2,f,e),if+e/2+g):g+e,h=f?hf+e/2+g:i,e*=2;
a=ZcZ*i%2?a+3:(c=Z,*i=Z48,i+=Z,h=i<h,++d,1);
}printf("%s\n%d",h,d);}
Submitted current shortest implementations in other languages
programming language 
submission date 
last update 
author(s) name(s) 
file name
(click to download) 
K_sc
source code size
(operational characters) 

author(s) comments (including updates) 
FASM for 64bit Windows only 
1Jan09 

Rickey Bowers Jr. 

1,845 
Yes 

Haskell 
20Jan09 



321 
Yes 

Perl 
24Feb09 



198 
Yes 

^ Handle carefully if nontested.
Other interesting (and short) implementations of Turing machines
programming language 
source 
last update 
author(s) name(s) 
source code 
K_sc
source code size
(operational characters) 

Pure Lisp 




139 
Yes 
Mathematica 




63 
Yes 
Send all your submissions or comments to shortestutm [at] mathrix.org
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 these 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 it is necessary to stick to a formalism providing a framework. For this contest the chosen formalism is 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 program shows the behavior, step by step, of all known busy beaver machines so far. In his 1962 paper[66], Tibor Radó introduced the busy beaver game. Since then, the Turing machine formalism for the busy beaver competition has beenas follows :

The Turing machine runs on a 2way 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 :
 a unique symbol to write (the machine can overwrite a 0 or a previously written symbol) usually denoted from 0 to n;
 a direction to move in (Left or Right but "none" is not allowed in this model except when the machine halts); and
 a state to transition into (may be the same as the one it was in) usually numbered from 1 to m.
 The machine halts if and when it reaches the special halting state.
In other terms :
 A Turing machine is a 5tuple of sets: M = (Q, Sigma, delta, q0, qH) where
 Q is a finite set of states including q0 and qH
 Sigma is a finite set of input symbols (there is no special 'blank' character, the background is a list of zeros)
 delta is a transition mapping Q{qH} x Sigma to Q x Sigma x {1,1,0}
 q0 is the initial state (1) in F
 qH is the halting state (0) in F
 F is a finite set of final states
A transition is a five tuple: fromstate inputsymbol tostate symboltowrite move. Every input entry must be an integer.
 The transition rules are flattened 5tuples of the form:
's_i_1' 'c_i_1' 's_n_1' 'c_n_1' 'd(11)' ... 's_i_k' 'c_i_k' 's_n_k' 'c_n_k' 'd(11)'
for k rules (the number of rules is 2*s with s the total number of states)
Each rule encoded as:
 s_i fromstate (1,...j) (starting state is always state '1')
 c_i inputsymbol (01, otherwise change 'symbols' variable)
 s_i tostate (1,...,j) (the halting state is always state '0')
 c_n symboltowrite
 d the head direction, either left ('1'), right ('1') or none ('0' when it enters into the halting state)
Programsize complexity
Also called algorithmic complexity or programsize complexity, the programsize 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. It is said 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 program size of 158 operational characters producing the 2400 first decimal digits of the number pi written in ANSI C:
int a=10000,b,c=8400,d,e,f[8401],g;main(){for(;bc;)
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);}


Emil Post 
All theorems in algorithmic information theory depend on additive constants, which depend on the size of the universal Turing machine. One might decide to encode a universal machine following a different computational model such as combinatory logic, a cellular automata or a Post tagsystem, to name a few, in order to reduce the size length. However, because the contest constrains the implementation to an input/output in terms of a Turing machine encodig (among other reasons because it gives sense to compare and test different implementations), the size of the translator/compiler that converts from one formalism to another may undermine any substantial decrease in size. We think that this is an interesting question per se.
Goals and motivation
The contest is premised on the fact that programsize complexity is not computable. Hence it is always an open question whether a particular implementation of a universal machine is the shortest. We think that the contest will motivate othersas it is motivating usto conduct research into the possible size ratios among different computational models when constrained 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 dependent on the chosen programming language although we have recently suggested a way to overcome this problem and provide a stable definition of programsize complexity[21].
Andrei Kolmogorov 

For instance, in quest of an utterly simple computer model, John Tromp has written a short program universal binary lambda computer[73] using combinatorics and from the same motives as those driving this contest, viz. to define and shed light on algorithmic information theory. Implemented in Haskell, the description and source code can be found here.
Gregory Chaitin[8] has also written short versions of selfdelimiting universal Turing machines in a dialect of Lisp he has written, the source code 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[77] 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 what the first 100 cells of the output tape look like.
The fact that all these languages are Turingequivalent means that, strictly speaking, one can write any program in any of them. However, implementations of a Turing machine in lowerlevel or structured programming languages may require several lines of code. We think that the contest may shed some light on the relations among several models of computation, since if one chooses a particular language or model for an implementation, the compiler may turn out to be long enough to counteract any effort to reduce the total size of the implementation. To confirm this and to understand how it happens, we are randomly fixing a language and a model, bearing in mind that ANSI C/C++ and a Turing machine are a very well known standard programming language 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 perhaps find 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. 

Leonid Levin 
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[32] and his collection of canonical solutions to the same problem in a number of languages.
By employing several implementations one can begin trying to find out what the ratio between different models and compilers may be. Also whether there is a convergence in output distribution from several different models of computation for which one could define "naturalness" for certain expected behaviors (disregarding the implementation size), as JeanPaul Delahaye and Hector Zenil have recently suggested in [21].
General Rules
In the spirit of the busy beaver competition[66] but related to our interest in programsize complexity—following our own research on the programsize complexity for short sequences and in pursuit of a stable definition of programsize complexity[19,20] independent of additive constants we challenge contestants to write the shortest universal machine implementations in any standard programming language and the simpler in terms of programsize complexity of a Turinguniversal machine. The contest is openended and it is open to anyone. To enter, a competitor must submit a universal machine implementation with smaller size values than the latest published records on this page.
Gregory Chaitin 

The size of a universal machine implementation will be given by the operational characters necessary to compile the source code by using a standard public available compiler (the same compiler will be used for all contestants). For C++ for instance, g++ version 4.0.1 under Mac OS X 10.5 will be used. Only operational characters will be counted. An operational character is a nonspace, nonpart of a comment ASCII character, disregarding variables and constant name lengths. In other words, if an operational character is removed the source code would not compile. Variables and constant names each count for 1 character (so naming a variable longer or shorter does not affect the final calculation, but it does if fewer are required). So make your code legible by choosing selfexplanatory variable names, and indenting and commenting on the code. All other characters will be taken into account in ascertaining the final sum. The combination of the following sizesthe 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 needs to be smaller than the previous champion implementation in order to take its place in the ranking. Once a program is submitted and accepted no further changes will be allowed, but new submissions are always welcome as long as they fulfill the prescribed requirements. 
A lower bound of the programsize length of the source code may be calculated with this Mathematica program. This Mathematica program will provide an approximation to the actual operationalcharacters length of the source code. However, submitters will have to perform the following steps and provide the exact calculation of their program length together with their submission:

Remove all comments.

Globally replace each variable/constant name with a unique singlecharacter replacement.

Concatenate all lines if possible (i.e., all except preprocessor directives) in editor, remove all whitespace except minimal required.

Compile and test the manually compressed version, to confirm that it still compiles and operates correctly.

Count every character and send the final sum together with your submission, the manually compressed version (with that number of characters and still compilable) and the readme file.
If the final count of the compressed version of the program is missing in the submission, it will be approached using the Mathematica program and it will be considered a lower bound and marked on the record holders table with a tilde symbol preceding the programsize value if it is clear that it is shorter than the previous implementations. Later the original author or any of the organizers can decide to replace the count by the actual verified value, specially if there is any hesitation on whether it is the shortest or not.
It is strongly suggested that contestants include a readme.txt file in the submission package, highlighting the code carrying out the computation of the machine implementation, if they don't then their submission email (or the part in which the program is specified) may be used instead as a readme file.
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 onscreen with no further computation or decoding. For C++ only the standard iostream ANSI/ISO 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 as the input, along with an integer indicating the total number of steps before halting. For nonTuring machine implementations an embedded compiler has to be included such that one can still provide the same input and get the expected output in the output form of a Turing machine in a finite (and reasonable) period of 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 a particular 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 output in a fixed form in a finite (and reasonable) time also stresses a timecomplexity related dimension of the implementations. Timecomplexity has figured integrally in the formulation of this contest, as we seek answers to the question of whether there is any practical tradeoff between time and programsize complexity.

Old convention (before January 20th. 2009):
Input syntax convention :
TuringMachine n transition_rules
with 'n' a long integer and 'transition_rules' a list of transition rules as integers. 'n' is the max number of steps
Input example :
bash$./TuringMachine 6 1 0 2 1 1 1 1 2 1 1 2 0 1 1 1 2 1 0 1 0
where '6' was the max number of steps and '1 0 2 1 1 1 1 2 1 1 2 0 1 1 1 2 1 0 1 0' are the four transition rules according to the busy beaver for 2 states, for example.

New convention (no more step limit):
Input syntax convention :
TuringMachine transition_rules
with 'transition_rules' a list of transition rules as integers. 'n' is the max number of steps
Input example :
bash$./TuringMachine 1 0 2 1 1 1 1 2 1 1 2 0 1 1 1 2 1 0 1 0
where '1 0 2 1 1 1 1 2 1 1 2 0 1 1 1 2 1 0 1 0' are the four transition rules according to the busy beaver for 2 states, for example.
Output is just the tape traversed. If any further questions contact the Shortest UTM Team by email.
Referees will be the previous holders of the record along with the organizers, all acting in good faith as there is nothing at stake but the honor of having encoded the shortest Turing machine while bearing in mind the ultimate goal of shedding some light on the discussion in question.
In order to take part in this competition you must submit the source code which must 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 preferably released under the GNU General Public License (GPL) licence in order to allow us to make them available on this web site for downloading and executing.
Bear in mind that the essence of the challenge, in accordance with which the above rules have been formulated, is to find ways of redesigning the code at the algorithmic level, not simply to redesign it aesthetically.
Send your submissions, questions or comments to shortestutm [at] mathrix.org
FAQs
Because we don't want to stifle any unexpected creativity, and because contests with C/C++ or any other programming language programs as entries are not easy to conduct, an excessive specification of rules has been deliberately avoided. If as a result the organizers are unclear, don't hesitate to ask for clarification. Any possible issue that might be left open will be resolved by the organizers, in consultation with record holders at the time, and based on the merit of the submission and in keeping with the spirit of the contest (in technical terms).
Together with the rules stated on the previous sectionparticipants must adhere to the following technical rules that we have formulated in a question/answer style:
What is this contest for?
A: On one hand, it would be interesting to know if there can be verydifferent implementation algorithms for a single model of computation or if the model of computation completely determines the implementation algorithm of the actual encoding. On the other hand, it would be interesting to know whether following other models of computation an implementation can be shortened in terms of program length and what is the one that may allow shortest implementations of a universal machine (although the question in general is undecidable, actual instances are possible). It would be also interesting to find whether any gained program size reduction is always lost once an interpreter from one model to another is included (e.g. SK combinators simulating Turing machines), and the impact that such a simulation may have in terms of computational time as well. Having several implementations of a universal machine may provide some empirical results.
Who is allowed to participate?
A: The contest is open to everybody.
Q: Is the contest constrained to the Turing machine model?
A: Not at all. Actually we encourage people to follow other models of computation (sk combinators, rewriting systems, cellular automata, tag systems, neural networks, register machines, etc.) and write down the shortest implementation you can come up with and write an encoder/decoder to accept the required (Turing machinestyle) input syntax and fulfill the required output format of the contest. Of course that may undermine any possible length reduction ensuing from the chosen model, but that is precisely the issue we want to address.
Isn't it ironic that the function to implement was only primitive recursive?
A: Yes it was. Implementations before January the 20th. 2009 are loop programs that always halt. They are only universal when the step limit, that was required as input by the former rules, is dropped. To do so, in terms of coding is quite easy since one would just delete the aditional condition for reaching the given maximum of steps. The possibility of unbounded computation is essential to a universal machine. One could write a C++ simulator that could simulate any halting program for a suitably big sizeof(int) == sizeof(void *) and corresponding memory. A nice paper on the complexity of loop programs is [82].
For that reason, starting on January the 20th. 2009 we have changed the rules regarding the step limit. From that day on all submissions are capable of unbounded computation. See the Rules section with the new input convention or ask the contest organizers if you have any question. Since the programsize of the implementations that were initially submitted following the old convention (with a step limit) would remain very close to the original size if the step limit were dropped, the comparison list of record holders with mixed step limit and nonstep limit versions remains still valid but notice that a readme file point out to the place in time when the rule change was made and applied from then on.
Q: Is the contest constrained to ANSI/ISO C++?
A: Not at all. Implementations in different programming languages are grouped and ordered by size for publication in this site.
Q: Will only the winning universal machines be published?
A: No. We encourage participants to send their universal machine implementations if they consider them interesting enough. The organizers will then decide whether to publish them in a special section devoted to interesting machines. For example, machines following different models of computations even if they are not smaller than the previous record holders, machines illustrating encoding/decoding interesting facts such as undermining any gained reduction in length, very efficient or inefficient machines, or machines following a previous model of computation but using a very different and interesting algorithm.
Q: Why 2symbol Turing machines?
A: Since discrete information and any Turing computation can be reduced to a binary language, we have decided to set the number of symbols at 2 for all implementations (as a hint to shorten the first submission since it is capable of computing with an arbitrary number of symbols).
Q: Why the so called busy beaver test?
A: A busy beaver Turing machine bb(n) is the most complex halting Turing machine in the class of the nstates Turing machines in terms of behavior since it either writes more nonzero symbols than any other and/or moves more (in terms of number of steps) than any other, so that if the machine is capable of simulating the behavior of the busy beavers it is likely to simulate any other machine in the same class.
Among other tests (such as the running of nonhalting Turing machines), each submitted entry will be required to compute all known busy beaver Turing machines. We have chosen this test because we think that:
Conjecture (Zenil): For all n>2, bb(n) the nstate busy beaver Turing machine is a (weak) universal Turing machine.
If so, this conjecture characterizes an interesting countable infinite set of universal Turing machines. Cris Calude[6] has recently proposed a definition of simplicity in terms of whether ZFC or PA are capable of providing a proof of the universality of a Turing machine, which is an interesting open question related to the possible path to take for proving this particular set of universal Turing machines determined by the behavior, starting from a blank tape, of a Turing machine, and whether they are simple in Calude's terms.
The busy beaver test also allows us to test the input/output requirement from the rules, also working as a stressing test as well (because of the traditional complexity in terms of head movement that busy beavers use to exhibit).
Q: Why might this be an interesting challenge?
A: There are several open questions related to the nature of the encoding/decoding process and the notion of universal computation. One such question is whether an implementation of a universal machine is efficient in terms of its code length compared to the encoding/decoding performance. The supposition is that a short description is only useful if the string can be reconstructed in a reasonable amount of time. 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[78,79] proved that some very small (weak)universal Turing machines are 'efficient' (in polynomial time) simulators of the tag systems they emule.
In the literature some authors make a technical distinction between machines that start with a blank tape as initial configuration and those that start with a nonblank (but still simple enough) initial configuration, such as a periodic background[52]. 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 what the compiler would look like in terms of programsize and time complexity. Is there an effective and efficient encoding for each nonperiodic encoding preserving universality? Will the encoding always be more complex if the machine is simpler? If so there is a relation to be discovered., If not, it is known that by adding states/symbols a nonblank 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) tradeoff between programsize 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 programsize complexity as two axes, with programsize complexity minimizing along one axis and time/space complexity along the second axis. Little work has been done on simultaneous minimization and their actual relation, if any. We think this challenge is a good handson chance to think about these issues and hopefully shed some light on them.
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.
Q: What ANSI C/C++ libraries are allowed?
A: None but 'iostream' (arbitrarily chosen after one of the organizers wrote the first record holder to be beaten using 'cout'). 'stdio.h' will not be allowed since we don't want to add/subtract whatever the compiled version of one program takes in bits as a consequence of using one or the other. No other library will be allowed. Since we are not concerned with program efficiency in terms of memory or programming best practices, the use of memory management (such as the use of malloc, calloc, realloc and free, included in 'stdlib.h') is optional. The only command allowed in 'iostream' is 'cout' streaming with destination to the screen.
Q: What about using the preprocessor (#define etc)?
A: It is allowed and will count as operational characters like any others.
Q: How many states and symbols should the Turing machine be able to carry out?
A: Any arbitrary number of states up to that allowed by the variable int (the actual value depends on the compiler/computer, but we specify a minimum of 16 bits).
Q: What runtime lengths should the universal machine implementation be capable of?
A: The max number of steps must be only restricted to the values of the 'long' internal variable type handling the machine execution, so any implementation should be able to compute as much as it (preferably unsigned). The same type constraints apply to the rest of the values [the number of allowed states (n) and all the products in play: 2n (number of rules), 5*2n (the 5tuple elements per rule), and the total number of machines (4n+2)^(2n)].
Q: What format must the output be in?
A: A contiguous string of binary digits with the content of the tape after halting, unique symbols if the machine does not halt after t steps, and in either case, the number of steps that the machine went through before halting or reaching the given maximum number of steps. In general, a rule entering into the halting state should make no movement either to the left or to the right but to stay in the same cell (indicated by a 0 in the shift rule place), otherwise authors would need to manage to print out only what the head actually printed on and no other blank character from the background.
Q: Do explicit zeroes written actively to the tape need to be printed even when they appear left of the leftmost nonzero or right of the rightmost nonzero?
A: Yes. In other words, just '1' instead of '01' would not be a permissible output if the head actually wrote "01" on the tape.
Q: Should the implementation run on the following input?
./TuringMachine 1 0 2 0 1 2 0 0 1 1
01
2
A: It is not mandatory. You can assume that the input determines a complete deterministic and consistent (not ambiguous) rule table. If implementations handle these cases gracefuly however, and still behaves as expected for the complete and consistent input case the implementation will be considered valid.
Q: What is the required input for the Turing machine before execution? Would this be a valid input?
./TuringMachine 1 0 2 1 1 2 0 2 1 1
A: No. It is assumed a complete and consistent rule input. This Turing machine has 2 symbols and 2 states. Consequently it is necessary to provide the full transition table of 4 rules in this case (the halting state '0' does not require an extrarule definition). In general it is required 2n rules with n the number of states (halting state not included).
Q: Are authors allowed to change their submissions or readme files?
A: Yes they are as long as they don't change their position in the winners table. If the position in the table is changed after a change then it will be considered a new submission. Of course fixes and improvements to the functionality of their implementations are encouraged but avoid sending changes that are not worth to make. Changes to the comments or the readme file will not count as an update, but try to make them seldom.
Other considerations:
Restrict your code lines to a maximum length of 80. This will help when printing it on paper.
The number and specification of the rules (and the number of symbols and states) is constrained by the variable types of the programming language and code itself. One could use a library for infinite arithmetic precision to get around this issue, such as the GNU Multiple Precision Arithmetic Library or GMP, but since it is not the purpose of the contest to actually (but only potentially) be able to compute any Turing machine to any runtime, we will only test it up to the allowed values of the specified variable types.
Programs would be disqualified if they:
• dump core or have compiler warnings (unless you warn us in the 'remark' header item and it doesn't affect the results of the tests we will perform).
• won't compile under a standard compiler for the chosenlanguage.
• depend on a utility or application.
• abuse the build file to get around the size limit.
• are too similar to previous winners.
• are identical to previous winners or losers.
We suggest that you format your program in a more creative way than simply forming excessively long lines.
What we have learned so far
We have encouraged the submission of implementations of universal machines written in any language following formalisms other than the Turing machine model, e.g. Cellular Automata, Tag systems or SK combinators. John Tromp has reasonably pointed out that it's no fun to write a TM simulator in SK combinators because one has to implement natural numbers from scratch. As long as the input describes a transition table and the number of transitions to iterate, the implementations will be heavily biased toward imperative languages.
It would appear that even when different formalisms of computation reach the same computational power they are highly dependent on the implementation language in which they are written, as long as the input/output format is determined. It’s as if it is the formalism thatwould determine the programming paradigm to be followed in order to keep the implementation down to a minimal size. While a Turing machine formalism seems to be favored when encoded into an imperative programming language, others like SK and Tag systems appear to be better suited for functional programming languages. But they don't seem to be readilyly compatible with each other, in the sense that encoding a simulator of one into the other takes as many resources as the original implementation itself. On the other hand, the formalism of Cellular Automata seems to be equally implementable (in programsize terms) in at least these two programming language paradigms, being perhaps midway between the transitional iterative behavior of a Turing machine and the expression rewriting of lists such as Tag systems. This is something that should be perhaps studied further.
We also didn't quite anticipate that there were going to be some inconsistencies between the programsize complexity evaluated in terms of what we call “operational characters,” the programsize complexity obtained after compilation, and the compressed version of the compilation. However this is not very surprising since both the compiler and the compression algorithm rely on many particularities that becomemore readily evident when very short programs are involved.
Most of the programsize shortenings have involved better memory management (the use of reallocation and dynamic memory) as well as reuse of variables. However it now seems hard to reduce the number of variables involved to less than the following: the maximum number of steps (from the input); the content of the tape at any given time; the machine head pointer; the tape boundaries; at least one iterator variable; a state variable, and a step counter. This is already very close to the number of variables used in the definition of the Turing machine 5tuplet formalism.
No submission has really come up with a very different approach other than sequential improvements to the original code based on the nested cycle ("dowhile", or "for") imposed by the iterative transition table format and characteristic of a Turing machine input/output specification, which at the same time constitutes the operators making the implementations in C++ capable of universal computation. In other words, this seems to be where the imperative paradigm outperforms any alternative approach, since imperative programming languages reach their Turingcompleteness through the power of the cyclic operators. We are interested in bibliography on this issue, papers proving the Turing completeness of different programming paradigms rather than particular programming languages (although we are interested in references for the particular languages as well). We also wonder if there is research on the minimal set of operators making a given programming paradigm Turingcomplete.
Of course the best way to prove that a programming language is Turingcomplete is by programming a Turing machine in that language. Here is an example of such a work, and we are aware of some other references, but we are also looking for more abstract generalized results on language paradigms and minimal languages. What makes a programming paradigm Turingcomplete? I think the answer is quite clear for the imperative paradigm in its quest to achieve unbounded computation through cycles or loops, but perhaps less so for the other cases, although it is clear some of them (such as Haskell and Prolog) reach Turingcompleteness through recursion.
Related conferences to the content of this contest
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, Alex Stangl, John Tromp and Gustavo Lacerda for their comments and suggestions. Of course, any mistake in the content of this web site is only responsibility of the contest organizers.
Organizers
Hector Zenil (Lille 1/LIFL, Paris 1/IHPST)
Jean PaulDelahaye (Lille 1/LIFL)
Send your submissions, questions or comments to shortestutm [at] mathrix.org
Subscribe to the Newsletter
References

Blum, L., Cucker, F., Shub, M. and Smale, S. 'Complexity and Real Computation,' Springer, 1997.

Böerger, E, Grädel, E. and Gurevich, Y., 'The Classical Decision Problem,' Springer, Heidelberg, 1997.

Brady, A.H., 'The determination of the value of Rado's noncomputable function Sigma(k) for fourstate Turing machines,' Mathematics of Computation, Vol. 40, No. 162 (April 1983), pp. 647665. B, 1983.

Brady, A.H., 'The Busy Beaver Game and the Meaning of Life,' p 237254, appearing in Herken, Rolf (ed)., The Universal Turing Machine: A HalfCentury Survey, 2nd edition, SpringerVerlag, Wien New York, 1995.
 Calude, C., 'Information and Randomness. An Algorithmic Perspective,' 2nd Edition, Revised and Extended, SpringerVerlag, 2002, 490 pp. Table of contents. Revised and Extended, Pushchino Publishing House, Moscow (Russian translation by Victor Vladimirovich Ivanov and Robert Polozov).
 Calude, C., Simplicity via Provability for Universal Prefixfree Turing Machines, to appear.


Chaitin, G., 'On the length of programs for computing finite binary sequences,' Journal of the ACM, 13(4):547569, 1966.

Chaitin, G., 'Meta Math! The Quest for Omega,' Atlantic Books, 2004.

Church, A., 'A Set of Postulates for the Foundation of Logic (Second Paper)', Annals of Mathematics, second series, 33, Princeton, 839864, 1933.

Church, A., 'A Note on the Entscheidungsproblem,' Journal of Symbolic Logic, 1, 4041; correction 1, Menasha, Wis., 101102, 1936.

Church, A., 'An Unsolvable Problem of Elementary Number Theory,' American Journal of Mathematics, 58, Baltimore, 345363, 1936.

Cobham, A., 'The Intrinsic Computational Difficulty of Functions,' Proceedings of the 1964 Congress for Logic, Mathematics, and Philosophy of Science, NorthHolland, Amsterdam, 2430, 1964.

Cook, S., 'The Complexity of Theorem Proving Procedures,' Proceedings of the Third Annual ACM STOC Symposium, Shaker Heights, Ohio, 151158, 1971.

Davis, M. 'The Universal Computer: the Road from Leibniz to Turing,' W. W. Norton & Company, New York, 2000.

Davis, M. 'Computability and Unsolvability,' Dover Publications, 1985.

Davis, M. (Ed.) 'The Undecidable: Basic Papers on Undecidable Propositions,' Unsolvable Problems and Computable Functions. Dover Publications, 2004.

Davis, M. 'The Universal Computer: The Road from Leibniz to Turing,' W. W. Norton & Company, 2000.



Delahaye, JP and Zenil, H. 'Towards a stable definition of KolmogorovChaitin complexity', (submitted to Fundamenta Informaticae), 2008.

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): 104115, 2005.

Dewdney, A.K., 'A computer trap for the busy beaver, the hardest working Turing machine,' Scientific American, 251 (2), 1017, 1984.

Dewdney, A.K., 'Busy beaver programs' in Scientific American, pages 1923, August 1984, p. 23 March 1985 and p. 30 April 1985.


Edmonds, J., 'Paths, Trees and Flowers', Canadian Journal of Mathematics, 17, Toronto, 449467, 1965.

Enderton, H. B., 'A Mathematical Introduction to Logic,' Academic Press, New York, 1972.

Gacs, P. 'On the symmetry of algorithmic information,' Soviet Mathematics Doklady, 15:14771480, 1974.

Garey, M. and Johnson, DS.,'Computers and Intractability,' Freeman, New York, 1979.

Gödel, K., 'The Completeness of the Axioms of the Functional Calculus,' (1930) in van Heijenoort, 582591, 1967.

Gödel, K., 'On Formally Undecidable Propositions of Principia Mathematica and Related Systems I,' (1931) in van Heijenoort, 592617, 1967.
 Graham, P., "Hackers and Painters: Big Ideas from the Computer Age", O'Reilly, 2004.

Grigorieff, Serge and Marion, JeanYves, 'Kolmogorov complexity and nondetermnism,' Theoretical Computer Science, Volume 271 , Issue 12, pag: 151180, 2002

Hartmanis, Juris, 'Overview of computational Complexity Theory' in J. Hartmanis, ed., Computational Complexity Theory, American Mathematical Society, Providence, 117, 1989.

Herken, R. 'The Universal Turing Machine: A HalfCentury Survey,' Springer Verlag, 1995.

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.

Hodges, Andrew, 'Alan Turing: the Enigma,' Random House, London, 1992.

Hofstadter, Douglas, 'Gödel, Escher, Bach: an Eternal Golden Braid,' Basic Books, New York, 1979.

Hopcroft, John E., 'Turing Machines', Scientific American, 250(5), New York, 7080, 1984.

Hutter, M. On Universal Prediction and Bayesian Confirmation. Theoretical Computer Science, 384:1, 3348, 2007.

Karp, Richard, 'Reducibility Among Combinatorial Problems', in Complexity of Computations, R.E. Miller and J.W. Thatcher, eds., Plenum Press, New York, 85104, 1972.

Kleene, Stephen C., 'Introduction to Metamathematics,' NorthHolland Publishing Company, 1952.

Kleene, Stephen C., 'A Theory of Positive Integers in Formal Logic,' American Journal of Mathematics, 57, Baltimore, 153173, 219244, 1935.

Kleene, Stephen C., 'Introduction to Metamathematics,' Van Nostrand, Princeton, 1950.

Kolmogorov, A. N. 'Combinatorial foundations of information theory and the calculus of probabilities,' Russian Mathematical Surveys, 38(4):2736, 1983.

Kolmogorov, A. N. 'Three approaches to the quantitative definition of information,' Problems of Information and Transmission, 1(1):17, 1965.

Levin, Leonid, 1973, 'Universal search problems,' Problemy Peredachi Informatsii, 9(3), 265266; partial English translation in: B.A.Trakhtenbrot, 'A Survey of Russian Approaches to Perebor (Bruteforce Search) Algorithms,' IEEE Annals of the History of Computing, 6(4), Los Alamitos, CA, 384400, 1984.

Levin, L. 'Laws of information conservation (nongrowth) and aspects of the foundation of probability theory,' Problems of Information Transmission, 10(3):206210, 1974.

Li M. and Vitanyi. 'An Introduction to Kolmogorov Complexity and its Applications'. Springer, New York, 2nd edition, 1997.

Lin, S. and Radó, T., 'Computer Studies of Turing Machine Problems,' Journal of the Association for Computing Machinery, Vol. 12, No. 2, pp. 196212, 1965.
 McCarthy, J. 'Programs with common sense, Paper presented at the Symposium on the Mechanization of Thought Processes,' National Physical Laboratory, Teddington, England, Nov. 2427, Published in Proceedings of the Symposium by H. M. Stationery Office, 1958.
 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.

Machlin, R. and Stout, Quentin F.,' The complex behavior of simple machines,' Physica D, No. 42, pp. 8598, 1990.

Margenstern, M. 'Frontier between Decidability and Undecidability: A Survey.' Theoretical Computer Science 231, no. 2 217251, 2000.

Markov, A.A., 'The Theory of Algorithms,' American Mathematical Society Translations, series 2, 15, Providence, 114.

Marxen, H. and Buntrock, J., 'Attacking the Busy Beaver 5,' Bulletin of the EATCS, No 40, pp. 247251, 1990.


Minsky, M. 'Computation: Finite and Infinite Machines. PrenticeHall,' Inc., 1967.


Neary, T. and Woods, D. 'Small fast universal Turing machines,' Theoretical Computer Science, Volume 362, Issues 13, 11, pp 171195., 2006.

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.

Papadimitriou, C. H., 'Computational Complexity,' AddisonWesley, Reading, Mass., 1994.

Pascal M., 'Small Turing machines and generalized busy beaver competition,' Theoretical Computer Science



Radó, Tibor, On noncomputable functions, Bell Systems Tech. J. 41, 3.1962.

Rogers, H. Jr., 'Theory of Recursive Functions and Effective Computability,' 1967, McGrawHill, New York.

Rogozhin, Yu. 'Small Universal Turing Machines.' Theoretical Computer Science 168, no. 2 (1996): 215240.


Solomonoff, R. 'A formal theory of inductive inference: Parts 1 and 2. Information and Control,' 7:122 and 224254, 1964.

Sutner, K. 'Cellular Automata and Intermediate Degrees.' Poster presented at NKS 2004.

Sutner, K. 'Universality and Cellular Automata.' In Lecture Notes in Computer Science: Machines, Computations, and Universality: 4th International Conference, MCU 3354: 5059, 2005.




Whitehead, Alfred North and Bertrand Russell, 'Principia Mathematica,' Cambridge University Press, Cambridge, 1910.


Woods, D. and Neary, T., 'On the time complexity of 2tag systems and small universal Turing machines', FOCS  2006, 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Berkeley, California, pp 439448, 2006.


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.

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):83124, 1970.
 Meyer, A. and Dennis, M. Ritchie, 'The complexity of loop programs', Proceedings A.C.M. National Meeting, 1967.
Send your submissions or comments to shortestutm [at] mathrix.org
The Experimental Algorithmic Information Project
Back to the EAIT main page
Last Updated Fri March 07 00:40 ET 2008
Laboratoire d'Informatique Fondamentale de Lille and IHPST (Paris 1)


Links
Subscribe to the Newsletter Experimental AIT
web page
Busy beaver
program
Programsize calculator in Mathematica
OEIS sequence A141474
OEIS sequence A141475
"Randomness
through
Computation"
Book ed. by H. Zenil
Related Links
Turing completeness of several programming languages
The 2,3 Wolfram Turing Machine Research Prize
John Tromp utterly simple computer model
Busy beaver from MathWorld
NKS online
Algorithmic Randomness and Complexity book
Ming Li
Paul Vitanyi
Heiner Marxen
busy beaver page
Maurice Margenstern
Serge Grigorieff
Pascal Michel's Historical survey of busy beaver results
Andrei Kolmogorov
web page
Cristian Calude
JeanPaul Delahaye
Leonid Levin
Gregory Chaitin
Ray Solomonoff
Jan Reimann
Eric Allender
Hector Zenil
Michael Somos
Allen H. Brady
Paul Graham
Revenge of the Nerds
Paul Graham collection of solutions to a problem in several programming languages
Damien Woods Turlough Neary FRG: Algorithmic Randomness
Algorithmic Information Theory
by Marcus Hutter
Algorithmic randomness from Scholarpedia
Algorithmic complexity
from Scholarpedia
Applications of AIT
from Scholarpedia
Algorithmic probability
from Scholarpedia
Turing machines from the Stanford Encyclopedia of Philosophy
Prize for Compressing Human Knowledge
The International Obfuscated C Code Contest
Laboratoire d'Informatique Fondamentale de Lille
Institute d'Histoire et Philosophie des Sciences et Techniques
