Message Boards Message Boards

GROUPS:

Universality of 4-states, 2-symbols and 3-states, 2-symbols Turing Machines

Posted 1 month ago
291 Views
|
0 Replies
|
0 Total Likes
|

I've been really interested in the field of small universal Turing machines, having read some of "A new kind of Science" that I took from the library. I saw that Stephen Wolfram wrote a few words about how 4-state, 2-colour machines exhibit complex behaviour given the right rules, but I've only found proofs of universality (and indeed p-completeness due to emulation of rule 110 cellular automata) in 2-state, 4-symbol machines. I've been wondering whether the 4-state, 2-colour machines have been proven universal or have been proven non - universal or whether or not this is still an open problem? Likewise, Wolfram claimed that it is unlikely, although not impossible for a 3-state, 2-colours machine to have a universal rule, and I wish to know if this is also still open or has been resolved, and if it is possible, then it will share the property of being the smallest UTM together with the 2-state, 3-symbol machine that has already been proven to be universal.

Thanks in advance!

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract