Equars People

So, it seems that the simplest universal turing machine has been demonstrated.

The simplest universal turing machine (T. M.) is, well, the simplest: 2 states and 3 symbols (or colors, as they are called by Stephen Wolfram), since a 2-states 2-symbols T.M. can not be universal.

This particular machine has however a subtle issue, for it requires an infinite memory (or ”tape” in the original definition of Turing), not satisfying perfectly the definition of universality given by Davis and Minsky.

The answer to the issue is that the pattern of bits in the memory can be set up without an universal T.M., so the universality is independent from the encoding of the pattern. I wonder if a (2,3) universal T.M. can be built with finite memory.