so that
δ : Q × (Σ∪{λ})× Γ ×Γ→ finite subsets of Q × Γ* × Γ*.
A move depends on the tops of the two stacks and results in new values
being pushed on these two stacks. Show that the class of two-stack
automata is equivalent to the class of Turing machines.
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 M u is
an automaton that, given as input the description of any Turing machine M and a
string w, can simulate the computation of M on w. To construct such an M u , we
first choose a standard way of describing Turing machines. We may, without loss
of generality, assume that
Q = {q 1 ,q 2 ,…,q n },
with q 1 the initial state, q 2 the single final state, and
Γ = {a 1 ,a 2 ,…a m },
where a 1 represents the blank. We then select an encoding in which q 1 is
represented by 1, q 2 is represented by 11, and so on. Similarly, a 1 is encoded as
1, a 2 as 11, etc. The symbol 0 will be used as a separator between the 1’s. With
the initial and final state and the blank defined by this convention, any Turing
machine can be described completely with δ only. The transition function is
encoded according to this scheme, with the arguments and result in some
prescribed sequence. For example, δ (q 1 , a 2 ) = (q 2 , a 3 , L) might appear as
δ : Q × (Σ∪{λ})× Γ ×Γ→ finite subsets of Q × Γ* × Γ*.
A move depends on the tops of the two stacks and results in new values
being pushed on these two stacks. Show that the class of two-stack
automata is equivalent to the class of Turing machines.
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 M u is
an automaton that, given as input the description of any Turing machine M and a
string w, can simulate the computation of M on w. To construct such an M u , we
first choose a standard way of describing Turing machines. We may, without loss
of generality, assume that
Q = {q 1 ,q 2 ,…,q n },
with q 1 the initial state, q 2 the single final state, and
Γ = {a 1 ,a 2 ,…a m },
where a 1 represents the blank. We then select an encoding in which q 1 is
represented by 1, q 2 is represented by 11, and so on. Similarly, a 1 is encoded as
1, a 2 as 11, etc. The symbol 0 will be used as a separator between the 1’s. With
the initial and final state and the blank defined by this convention, any Turing
machine can be described completely with δ only. The transition function is
encoded according to this scheme, with the arguments and result in some
prescribed sequence. For example, δ (q 1 , a 2 ) = (q 2 , a 3 , L) might appear as