<p>I found the book:</p>

<pre><code>@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},
} 
</code></pre>

<p>and <a href="http://www.fractalmuse.org/misc/FLTRA_HU_UM.pdf" rel="nofollow">this is a link to a pdf scan of the UM description (7 pages)</a>.</p>

CC BY-SA 3.0
2012-02-17T13:48:33.970Z
2012-02-17T13:48:33.970Z
Marzio De Biasi
<p>Here are some references:</p>

<ul>
<li>Claude Shannon, "A universal Turing machine with two internal states", 1956.</li>
<li>Marvin Minsky, "A 6-symbol 6-state Universal Turing Machine", 1960.</li>
<li>Shigeru Watanabe, "<a href="http://dx.doi.org/10.1145/321088.321090" rel="nofollow">5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines</a>", 1961.</li>
</ul>

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

<blockquote>
  <p>"..., and explicit constructions of universal Turing machines are in Turing
  <a href="http://plms.oxfordjournals.org/cgi/reprint/s2-42/1/230" rel="nofollow">[1936]</a>, Wang <a href="http://dx.doi.org/10.1002/malq.19570030602" rel="nofollow">[1957a]</a> 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]." </p>
</blockquote>

CC BY-SA 3.0
2012-02-17T17:42:23.680Z
2012-02-17T18:07:02.343Z
2012-02-17T18:07:02.343Z
Kaveh
<p>I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram? </p>

<p>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. </p>

<p>I would prefer historic references.</p>

CC BY-SA 3.0
2012-02-17T08:55:37.220Z
Maybe this Wolfram demonstration is close to what you are looking for: http://demonstrations.wolfram.com/RuleCaseTransitionDiagramsForTheWolfram23TuringMachine/ . I think a similar style was used in Wolfram's book 'A new kind of science'.
Mohammad Alaggan
CC BY-SA 3.0
2012-02-17T11:57:48.257Z
According to the information found on this web page (http://www.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).
Marzio De Biasi
<reference-request><computability><turing-machines><universal-computation>
Transition Diagram of a Universal Turing Machine
Anonymous
# Transition Diagram of a Universal Turing Machine

(Asked by: username_0 on 2012-02-17)

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.

**Tags:** reference-request, computability, turing-machines, universal-computation

> **Comments:**
> **username_1**: Maybe this Wolfram demonstration is close to what you are looking for: http://demonstrations.wolfram.com/RuleCaseTransitionDiagramsForTheWolfram23TuringMachine/ . I think a similar style was used in Wolfram's book 'A new kind of science'.  
> **username_2**: According to the information found on this web page (http://www.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).  

---

## 2 answers

### Answer by username_2 on 2012-02-17. Score: 2 | Accepted answer

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).


---

### Answer by username_3 on 2012-02-17. Score: 3

Here are some references:

* Claude Shannon, "A universal Turing machine with two internal states", 1956.
* Marvin Minsky, "A 6-symbol 6-state Universal Turing Machine", 1960.
* Shigeru Watanabe, "[5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines](http://dx.doi.org/10.1145/321088.321090)", 1961.

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

> "..., and explicit constructions of universal Turing machines are in Turing
> [[1936]](http://plms.oxfordjournals.org/cgi/reprint/s2-42/1/230), Wang [[1957a]](http://dx.doi.org/10.1002/malq.19570030602) 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]."


---

