10.4 A UNIVERSAL TURING MACHINE
Consider the following argument against Turing’s thesis: “A Turing machine as presented in Definition 9.1 is a special-purpose computer. Once δ is defined, the machine is restricted to carrying out one particular type of computation. Digital computers, on the other hand, are general-purpose machines that can be programmed to do different jobs at different times. Consequently, Turing machines cannot be considered equivalent to general-purpose digital computers.”
This objection can be overcome by designing a reprogrammable Turing machine, called a universal Turing machine. A universal Turing machine Mu is an automaton that, given as input the description of any Turing machine M and a string w, can simulate the computation ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
