2
$\begingroup$

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)

$\endgroup$
10
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Xoff
    Dec 14, 2013 at 15:54
  • $\begingroup$ I found the description of the storage, but not the u-machine itself. $\endgroup$
    – Peter
    Dec 14, 2013 at 16:05
  • $\begingroup$ sciencedirect.com/science/article/pii/S0304397596000771 $\endgroup$
    – Xoff
    Dec 14, 2013 at 16:13
  • $\begingroup$ There are different kind of universality. I don't think that this example is the Turing universality. Where did you find this example ? $\endgroup$
    – Xoff
    Dec 15, 2013 at 12:47
  • $\begingroup$ 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. $\endgroup$
    – Xoff
    Dec 15, 2013 at 12:59

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ In this link, the listing is still not visible. What can I do to get acess to it ? $\endgroup$
    – Peter
    Dec 15, 2013 at 12:53
  • $\begingroup$ Don't you have a download PDF link at the top (just under Home| Publications)? $\endgroup$
    – Xoff
    Dec 15, 2013 at 13:08
  • $\begingroup$ Yes, but is it free ? $\endgroup$
    – Peter
    Dec 15, 2013 at 13:09
  • $\begingroup$ for me it seems to be. $\endgroup$
    – Xoff
    Dec 15, 2013 at 13:10
  • $\begingroup$ Ok, thank you very much. $\endgroup$
    – Peter
    Dec 15, 2013 at 13:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .