Item #29298 A Universal Turing Machine with Two Internal States. Claude E. Shannon, J. McCarthy, with Shannon, Elwood.
Probable offprint issue

A Universal Turing Machine with Two Internal States

Princeton, NJ: Princeton University Press 1956. [1 (title page)], [1 (blank verso)], 157-165, [3 (blank)] pages. 10 x 7 inches. Stapled printed self-wrappers, with leaves trimmed at the spine. Light staining at foreedge The construction of this item is unusual. It consists of separate leaves of the printed paper in the original journal fonts, with a new title page “AUTOMATA STUDIES” (blank verso) and an added trailing blank leaf, all stapled at the spine. All examined copies from Shannon's files are the same, leading us to conclude it was likely an author offprint even though a reprint statement is not present. Near Fine. Wraps. [29298]


Originally printed as an internal Bell Laboratories Memorandum: Number 54-114-38, May 15, 1954. “Automata Studies,” Annals of Mathematics Studies number 34, 1956 (edited by Claude Shannon and John McCarthy), first published this Shannon paper as “A Universal Turing Machine With Two Internal States“ on pages 157-165.

"Our main result is to show that a universal Turing machine can be constructed using one tape and having only two internal states. It will also be shown that it is impossible to do this with one internal state. Finally, a construction is given for a universal Turing machine with only two tape symbols." (p 158 of introduction)

"A Turing machine which, by appropriate programming using a finite length of input tape, can act as any Turing machine whatsoever. In his seminal paper, Turing himself gave the first construction for a universal Turing machine (Turing 1937, 1938). Shannon (1956) showed that two colors were sufficient, so long as enough states were used. [ as here ]" Wolfram Mathworld

PROVENANCE: The personal files of Claude E. Shannon (unmarked). There were multiple examples of this item in Shannon's files.

REFERENCES:
Sloane and Wyner, "Claude Elwood Shannon Collected Papers," #93

Price: $100.00

See all items in Mathematics