Concrete universal turing machine

260 Views Asked by At

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)

1

There are 1 best solutions below

5
On BEST ANSWER

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.