4
$\begingroup$

I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram?

I need this as a reference, so preferably a book or a published article. I don't want anything strange, just a standard Turing Machine with one tape that computes the Universal Turing Machine. The tape will contain a Turing machine and an input string. The rest of the tape is filled with blank.

I would prefer historic references.

$\endgroup$
  • $\begingroup$ Maybe this Wolfram demonstration is close to what you are looking for: demonstrations.wolfram.com/… . I think a similar style was used in Wolfram's book 'A new kind of science'. $\endgroup$ – M. Alaggan Feb 17 '12 at 8:55
  • $\begingroup$ According to the information found on this web page (rdrop.com/~half/General/UTM/index.html), the complete description of an UTM is contained in one of the first editions of the book: "Formal Languages and Their Relation to Automata" by Hopcroft & Ullman. Perhaps someone can search the book in its library and see if the information is correct (... and scan the pages with the UTM). $\endgroup$ – Marzio De Biasi Feb 17 '12 at 11:57
2
$\begingroup$

I found the book:

@book{Hopcroft:1969:FLR:1096945,
 author = {Hopcroft, John E. and Ullman, Jeffrey D.},
 title = {Formal languages and their relation to automata},
 year = {1969},
 publisher = {Addison-Wesley Longman Publishing Co., Inc.},
 address = {Boston, MA, USA},
} 

and this is a link to a pdf scan of the UM description (7 pages).

$\endgroup$
3
$\begingroup$

Here are some references:

Also Odifreddi writes ["Classical Recursion Theory", vol I, p. 133]:

"..., and explicit constructions of universal Turing machines are in Turing [1936], Wang [1957a] and in many textbooks, e.g. Hermes [1965], Minsky [1967], Arbib [1969], Hopcroft and Ullman [1979]. More information on the topic is in Davis [1956], [1957], Shannon [1956], Rogers [1967] and Priese [1979]."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.