Consider the Game of Life. Given an infinite two-dimensional plane to run the Game on, and an infinite amount of "matter" so that one can give the automata any initial conditions one wishes, it is known that the Game of Life is Turing-complete, i.e. it can simulate anything number theory can.

The Game of Life has very simple rules - slightly more rigorously, its Kolmogorov complexity is low in most naive languages. Are there simpler (lower Kolmogorov complexity) Turing machines? Is it possible to prove that a Turing machine achieves the simplest possible construction in a given language?

A note - I'm only interested in the complexity of the rules required to run the code. An infinite number of states (or equivalently symbols) is fine, so long as the complexity of the map evaluated at each program step is low. (Game of Life is already down to three statements.)

  • 1
    $\begingroup$ The Wikipedia article on UTMs has a section on “smallest machines”. “Rogozhin's [4-state, 6-symbol] machine uses only 22 instructions, and no standard UTM of lesser descriptional complexity is known.” $\endgroup$
    – MJD
    Commented Dec 15, 2016 at 17:07
  • $\begingroup$ I did find that, yes, but that doesn't seem like what I'm looking for. Under the assumptions of infinite states/symbols, the Game of Life, with only three instructions, is already much simpler in terms of its instruction count. $\endgroup$ Commented Dec 15, 2016 at 23:07
  • $\begingroup$ I suppose I should make it clearer that I only care about instruction complexity, and that you can make the "tape" as large or complex as you like. $\endgroup$ Commented Dec 15, 2016 at 23:08
  • 1
    $\begingroup$ @linkhyrule5 You haven't described what an 'instruction' is yet. (You probably don't want to use 'Universal Turing Machine' in your title since that has a formal definition; instead, maybe 'Turing-Complete system'?) And I would contest that Life has lower KC than, e.g., the (4,6) UTM that that Wikipedia article mentions. $\endgroup$ Commented Dec 15, 2016 at 23:16
  • $\begingroup$ Mm. Possibly, yes. But an "instruction" is ... well, take the Game of Life as an example. We need one function that gets the number of living cells around each point, and then we have a three-fold case statement attached to the result; and then that's it, we can run that for every cell. I would say that this machine requires four instructions to run. $\endgroup$ Commented Dec 17, 2016 at 5:40


You must log in to answer this question.

Browse other questions tagged .