Martin Davis makes a persuasive argument that Turing's conception of what is now known as "the stored-program computer", of placing the "action table"—the instructions for the machine—in the same "memory" as the input data, strongly influenced John von Neumann's conception of the first American discrete-symbol (as opposed to analog) computer—the EDVAC.
[9] Knuth observes that the subroutine return embedded in the program itself rather than in special registers is attributable to von Neumann and Goldstine.
Interpretive routines in the conventional sense were mentioned by John Mauchly in his lectures at the Moore School in 1946 ... Turing took part in this development also; interpretive systems for the Pilot ACE computer were written under his direction.
[10] Davis briefly mentions operating systems and compilers as outcomes of the notion of program-as-data.
Rice's theorem shows that any non-trivial question about the output of a Turing machine is undecidable.
It should be no surprise that we can achieve this encoding given the existence of a Gödel number and computational equivalence between Turing machines and μ-recursive functions.
Similarly, our construction associates to every binary string α, a Turing machine Mα.
Starting from the above encoding, in 1966 F. C. Hennie and R. E. Stearns showed that given a Turing machine Mα that halts on input x within N steps, then there exists a multi-tape universal Turing machine that halts on inputs α, x (given on different tapes) in CN log N, where C is a machine-specific constant that does not depend on the length of the input x, but does depend on M's alphabet size, number of tapes, and number of states.
[12] The corresponding result for space-complexity rather than time-complexity is that we can simulate in a way that uses at most CN cells at any stage of the computation, an
Claude Shannon first explicitly posed the question of finding the smallest possible universal Turing machine in 1956.
Other small universal Turing machines have since been found by Yurii Rogozhin and others by extending this approach of tag system simulation.
[14][15][16] Rogozhin's (4, 6) machine uses only 22 instructions, and no standard UTM of lesser descriptional complexity is known.
However, generalizing the standard Turing machine model admits even smaller UTMs.
Small weakly universal Turing machines that simulate the Rule 110 cellular automaton have been given for the (6, 2), (3, 3), and (2, 4) state-symbol pairs.
[18] For those who would undertake the challenge of designing a UTM exactly as Turing specified see the article by Davies in Copeland (2004).
for clarity): The U-machine's action-table (state-transition table) is responsible for decoding the symbols.
Roger Penrose provides examples of ways to encode instructions for the Universal machine using only binary symbols { 0, 1 }, or { blank, mark | }.
He asserts that it truly is a U-machine code, an enormous number that spans almost 2 full pages of 1's and 0's.
[19] Asperti and Ricciotti described a multi-tape UTM defined by composing elementary machines with very simple semantics, rather than explicitly giving its full action table.
This approach was sufficiently modular to allow them to formally prove the correctness of the machine in the Matita proof assistant.