2

I read about universal turing machines in the internet, but I did not find a concrete listing of a universal turing machine and a descreption, how a specific turing machine has to be coded that the universal machines simulates it. Does anyone know a suitable link ?

I found the following description of the smallest universal turing machine :

A   B

0 P1,R,B P2,L,A

1 P2,L,A P2,R,B

2 P1,L,A P0,R,A

As it has no halting state, how can it simulate a halting turing machine ? (Sorry for the bad format)

Peter
  • 84,454
  • http://en.wikipedia.org/wiki/Universal_Turing_machine#Example_of_universal-machine_coding – Xoff Dec 14 '13 at 15:54
  • I found the description of the storage, but not the u-machine itself. – Peter Dec 14 '13 at 16:05
  • http://www.sciencedirect.com/science/article/pii/S0304397596000771 – Xoff Dec 14 '13 at 16:13
  • There are different kind of universality. I don't think that this example is the Turing universality. Where did you find this example ? – Xoff Dec 15 '13 at 12:47
  • This is weak universality, not Turing universality : you have to encode the input of the machine in an infinite repetitive pattern. The output must be constantly observed until something happens that can be analyzed as "the simulated program halted", because as you did observe, there is no halt state in this example. So it's much less than usual Turing universality. – Xoff Dec 15 '13 at 12:59
  • Ok, thanks, but such a machine is completely useless, or am I wrong ? – Peter Dec 15 '13 at 13:00
  • Are the turing machines in your links turing-universal ? – Peter Dec 15 '13 at 13:02
  • For any practical purposes, yes, it's useless at this time. But for a better knowledge of what is computation, it's very useful. Yes my answer is about usual Turing universality. – Xoff Dec 15 '13 at 13:03
  • Thank you for your explanations. – Peter Dec 15 '13 at 13:04
  • It's very hard to find small universal Turing machines. When researchers can't solve something, they try something easier. That's why they tried to find some small weakly universal machines as your example. But it doesn't help much for real universality. – Xoff Dec 15 '13 at 13:06

1 Answers1

2

http://www.sciencedirect.com/science/article/pii/S0304397596000771 contains complete descriptions of some universal Turing machines.

On page 8 of the pdf (page 222) you have an example of a machine with 24 states and 2 symbols. On page 10 of the pdf (page 224) you have an example of a machine with 10 states and 3 symbols.

Xoff
  • 10,310