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 Dec 15 '16 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$ – linkhyrule5 Dec 15 '16 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$ – linkhyrule5 Dec 15 '16 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$ – Steven Stadnicki Dec 15 '16 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$ – linkhyrule5 Dec 17 '16 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.