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 5-tuple formalism described in the formalism section. Submitted entries will include be tested by computing all the known busy beaver 2-symbol 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 program-size 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 program-size 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
15-Dec-08
638
13,224
2,240
2
23-Dec-08
Hein Hundal
436
13,052
1,822
3
24-Dec-08
340
13,152
2,085
4
2-Jan-09
320
13,068
1,751
5
7-Jan-09
284
13,028
1,738
6
20-Jan-09
208
12,928
1,781
7
28-Jan-09
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<=g|i>=g+e)f=g,g=(char*)calloc(e,2),i=f?(memcpy(g+e/2,f,e),i-f+e/2+g):g+e,h=f?h-f+e/2+g:i,e*=2;
a=Z-c|Z-*i%2?a+3:(c=Z,*i=Z|48,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)

tested^

author(s) comments (including updates)
FASM for 64-bit Windows only
1-Jan-09
Rickey Bowers Jr.
1,845
Yes
Haskell
20-Jan-09
 
Alex Stangl with an improvement from John Tromp
321
Yes
 
Perl
24-Feb-09
 
198
Yes
 

^ Handle carefully if non-tested.

 

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)

tested

Pure Lisp
139
Yes
Mathematica
63
Yes


Send all your submissions or comments to shortest-utm [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 2-way unbounded tape filled with zeros (no blank symbol).
  • At each step, two conditions :
  1. the machine's current "state" (instruction); and
  2. the tape symbol the machine's head is scanning

define each of the following :

  1. a unique symbol to write (the machine can overwrite a 0 or a previously written symbol) usually denoted from 0 to n;
  2. a direction to move in (Left or Right but "none" is not allowed in this model except when the machine halts); and
  3. 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 5-tuple 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: from-state input-symbol to-state symbol-to-write move. Every input entry must be an integer.

  • The transition rules are flattened 5-tuples of the form:
    's_i_1' 'c_i_1' 's_n_1' 'c_n_1' 'd(1|-1)' ... 's_i_k' 'c_i_k' 's_n_k' 'c_n_k' 'd(1|-1)'
    for k rules (the number of rules is 2*s with s the total number of states)

    Each rule encoded as:
  • s_i from-state (1,...j) (starting state is always state '1')
  • c_i input-symbol (0|1, otherwise change 'symbols' variable)
  • s_i to-state (1,...,j) (the halting state is always state '0')
  • c_n symbol-to-write
  • d the head direction, either left ('-1'), right ('1') or none ('0' when it enters into the halting state)

Program-size complexity

Also called algorithmic complexity or program-size 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. 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(;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);}

 

 

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 tag-system, 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 program-size 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 others---as it is motivating us---to 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 program-size 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 self-delimiting 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 Turing-equivalent means that, strictly speaking, one 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 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 Jean-Paul 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 program-size complexity—following our own research on the program-size complexity for short sequences and in pursuit of a stable definition of program-size 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 program-size complexity of a Turing-universal machine. The contest is open-ended 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 non-space, non-part 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 self-explanatory 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 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-- 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 program-size length of the source code may be calculated with this Mathematica program. This Mathematica program will provide an approximation to the actual operational-characters 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:

  1. Remove all comments.
  2. Globally replace each variable/constant name with a unique single-character replacement.
  3. Concatenate all lines if possible (i.e., all except preprocessor directives) in editor, remove all whitespace except minimal required.
  4. Compile and test the manually compressed version, to confirm that it still compiles and operates correctly.
  5. 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 program-size 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 on-screen 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 non-Turing 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 time-complexity related dimension of the implementations. Time-complexity has figured integrally in the formulation of this contest, as we seek answers to the question of whether there is any practical trade-off between time and program-size 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 shortest-utm [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 machine-style) 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 program-size 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 non-step 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 2-symbol 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 n-states Turing machines in terms of behavior since it either writes more non-zero 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 non-halting 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 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. 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 non-blank (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 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 be discovered., If not, it is known 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, with program-size 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 hands-on 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 5-tuple 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 non-zero or right of the rightmost non-zero?

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 program-size terms) in at least these two programming language paradigms, being perhaps midway between the transitional iterative behavior of a Turing machine and the expression re-writing 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 program-size complexity evaluated in terms of what we call “operational characters,” the program-size 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 program-size shortenings have involved better memory management (the use of re-allocation and dynamic memory) as well as re-use 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 5-tuplet 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 ("do-while", 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 Turing-completeness 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 Turing-complete.

Of course the best way to prove that a programming language is Turing-complete 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 Turing-complete? 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 Turing-completeness 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 Paul-Delahaye (Lille 1/LIFL)

Send your submissions, questions or comments to shortest-utm [at] mathrix.org

Subscribe to the Newsletter

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. Calude, C., 'Information and Randomness. An Algorithmic Perspective,' 2nd Edition, Revised and Extended, Springer-Verlag, 2002, 490 pp. Table of contents. Revised and Extended, Pushchino Publishing House, Moscow (Russian translation by Victor Vladimirovich Ivanov and Robert Polozov).
  6. Calude, C., Simplicity via Provability for Universal Prefix-free Turing Machines, to appear.
  7. Chaitin, G., 'On the length of programs for computing finite binary sequences,' Journal of the ACM, 13(4):547--569, 1966.
  8. Chaitin, G., 'Meta Math! The Quest for Omega,' Atlantic Books, 2004.
  9. Church, A., 'A Set of Postulates for the Foundation of Logic (Second Paper)', Annals of Mathematics, second series, 33, Princeton, 839-864, 1933.
  10. Church, A., 'A Note on the Entscheidungsproblem,' Journal of Symbolic Logic, 1, 40-41; correction 1, Menasha, Wis., 101-102, 1936.
  11. Church, A., 'An Unsolvable Problem of Elementary Number Theory,' American Journal of Mathematics, 58, Baltimore, 345-363, 1936.
  12. 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.
  13. Cook, S., 'The Complexity of Theorem Proving Procedures,' Proceedings of the Third Annual ACM STOC Symposium, Shaker Heights, Ohio, 151-158, 1971.
  14. Davis, M. 'The Universal Computer: the Road from Leibniz to Turing,' W. W. Norton & Company, New York, 2000.
  15. Davis, M. 'Computability and Unsolvability,' Dover Publications, 1985.
  16. Davis, M. (Ed.) 'The Undecidable: Basic Papers on Undecidable Propositions,' Unsolvable Problems and Computable Functions. Dover Publications, 2004.
  17. Davis, M. 'The Universal Computer: The Road from Leibniz to Turing,' W. W. Norton & Company, 2000.
  18. Delahaye, JP and Zenil, H. 'Towards a stable definition of Kolmogorov-Chaitin complexity', (submitted to Fundamenta Informaticae), 2008.
  19. 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.
  20. Dewdney, A.K., 'A computer trap for the busy beaver, the hardest working Turing machine,' Scientific American, 251 (2), 10-17, 1984.
  21. Dewdney, A.K., 'Busy beaver programs' in Scientific American, pages 19-23, August 1984, p. 23 March 1985 and p. 30 April 1985.
  22. Edmonds, J., 'Paths, Trees and Flowers', Canadian Journal of Mathematics, 17, Toronto, 449-467, 1965.
  23. Enderton, H. B., 'A Mathematical Introduction to Logic,' Academic Press, New York, 1972.
  24. Gacs, P. 'On the symmetry of algorithmic information,' Soviet Mathematics Doklady, 15:1477-1480, 1974.
  25. Garey, M. and Johnson, DS.,'Computers and Intractability,' Freeman, New York, 1979.
  26. Gödel, K., 'The Completeness of the Axioms of the Functional Calculus,' (1930) in van Heijenoort, 582-591, 1967.
  27. Gödel, K., 'On Formally Undecidable Propositions of Principia Mathematica and Related Systems I,' (1931) in van Heijenoort, 592-617, 1967.
  28. Graham, P., "Hackers and Painters: Big Ideas from the Computer Age", O'Reilly, 2004.
  29. Grigorieff, Serge and Marion, Jean-Yves, 'Kolmogorov complexity and non-determnism,' Theoretical Computer Science, Volume 271 , Issue 1-2, pag: 151-180, 2002
  30. Hartmanis, Juris, 'Overview of computational Complexity Theory' in J. Hartmanis, ed., Computational Complexity Theory, American Mathematical Society, Providence, 1-17, 1989.
  31. Herken, R. 'The Universal Turing Machine: A Half-Century Survey,' Springer Verlag, 1995.
  32. 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.
  33. Hodges, Andrew, 'Alan Turing: the Enigma,' Random House, London, 1992.
  34. Hofstadter, Douglas, 'Gödel, Escher, Bach: an Eternal Golden Braid,' Basic Books, New York, 1979.
  35. Hopcroft, John E., 'Turing Machines', Scientific American, 250(5), New York, 70-80, 1984.
  36. Hutter, M. On Universal Prediction and Bayesian Confirmation. Theoretical Computer Science, 384:1, 33-48, 2007.
  37. 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.
  38. Kleene, Stephen C., 'Introduction to Metamathematics,' North-Holland Publishing Company, 1952.
  39. Kleene, Stephen C., 'A Theory of Positive Integers in Formal Logic,' American Journal of Mathematics, 57, Baltimore, 153-173, 219-244, 1935.
  40. Kleene, Stephen C., 'Introduction to Metamathematics,' Van Nostrand, Princeton, 1950.
  41. Kolmogorov, A. N. 'Combinatorial foundations of information theory and the calculus of probabilities,' Russian Mathematical Surveys, 38(4):27--36, 1983.
  42. Kolmogorov, A. N. 'Three approaches to the quantitative definition of information,' Problems of Information and Transmission, 1(1):1--7, 1965.
  43. 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.
  44. 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.
  45. Li M. and Vitanyi. 'An Introduction to Kolmogorov Complexity and its Applications'. Springer, New York, 2nd edition, 1997.
  46. 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.
  47. 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.
  48. 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.
  49. Machlin, R. and Stout, Quentin F.,' The complex behavior of simple machines,' Physica D, No. 42, pp. 85-98, 1990.
  50. Margenstern, M. 'Frontier between Decidability and Undecidability: A Survey.' Theoretical Computer Science 231, no. 2 217-251, 2000.
  51. Markov, A.A., 'The Theory of Algorithms,' American Mathematical Society Translations, series 2, 15, Providence, 1-14.
  52. Marxen, H. and Buntrock, J., 'Attacking the Busy Beaver 5,' Bulletin of the EATCS, No 40, pp. 247-251, 1990.
  53. Minsky, M. 'Computation: Finite and Infinite Machines. Prentice-Hall,' Inc., 1967.
  54. Neary, T. and Woods, D. 'Small fast universal Turing machines,' Theoretical Computer Science, Volume 362, Issues 1-3, 11, pp 171-195., 2006.
  55. 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.
  56. Papadimitriou, C. H., 'Computational Complexity,' Addison-Wesley, Reading, Mass., 1994.
  57. Pascal M., 'Small Turing machines and generalized busy beaver competition,' Theoretical Computer Science
  58. Radó, Tibor, On non-computable functions, Bell Systems Tech. J. 41, 3.1962.
  59. Rogers, H. Jr., 'Theory of Recursive Functions and Effective Computability,' 1967, McGraw-Hill, New York.
  60. Rogozhin, Yu. 'Small Universal Turing Machines.' Theoretical Computer Science 168, no. 2 (1996): 215-240.
  61. Solomonoff, R. 'A formal theory of inductive inference: Parts 1 and 2. Information and Control,' 7:1--22 and 224--254, 1964.
  62. Sutner, K. 'Cellular Automata and Intermediate Degrees.' Poster presented at NKS 2004.
  63. Sutner, K. 'Universality and Cellular Automata.' In Lecture Notes in Computer Science: Machines, Computations, and Universality: 4th International Conference, MCU 3354: 50-59, 2005.
  64. Whitehead, Alfred North and Bertrand Russell, 'Principia Mathematica,' Cambridge University Press, Cambridge, 1910.
  65. 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.
  66. Meyer, A. and Dennis, M. Ritchie, 'The complexity of loop programs', Proceedings A.C.M. National Meeting, 1967.

 

Send your submissions or comments to shortest-utm [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

Program-size 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

Jean-Paul 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