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.

Improve this question
$\endgroup$
2
  • $\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$
    – Mohammad Alaggan
    Commented Feb 17, 2012 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
    Commented Feb 17, 2012 at 11:57

2 Answers 2

Reset to default
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).

Improve this answer
$\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]."

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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