⟸ Go Back ⟸
Exercise 2 (Homework 5).
(Turing machines)

Equivalent models of Turing machines

A computation model is Turing-complete if it can be used to compute every Turing-computable function.

  1. Show that every partial function computable on a Turing machine with k tapes can be computed on a Turing machine with only 1 tape.
  2. Show that every partial function computable on a nondeterministic Turing machine can be computed on a deterministic Turing machine.
  3. Consider the following variation of PDAs: one that has two stacks instead of just one. Transitions then depend on the current state and on the top symbol of each stack. At each step, the automaton can remove the top element from either stack or push new symbols onto them. Such a machine can be used to compute functions: at the start of the computation, one of the stacks contains the input, and at the end, the output is left on a stack. Show that every Turing-computable function can be computed with this 2-stack version of PDAs.
  4. Consider the following variation of PDAs: one that has a queue instead of a stack. Transitions depend on the current state and on the first element of the queue. At each step, the first element of the queue can be removed and new elements can be added at the end. Such a machine can be used to compute functions: at the start of the computation, the queue contains the input, and at the end, the output is left on the queue. Show that every Turing-computable function can be computed with this queue version of PDAs.
Tip

To show that a certain computational model is Turing-complete, it is enough to show how to simulate the behaviour of a Turing machine. For this exercise there is no need to give a very detailed description of the simulations. Just the general idea is enough.

Computable functions

Recall that a partial function f : \mathbb N^k \to \mathbb N is (Turing-)computable if there exists a Turing machine M_f s.t.

  • if f(x_1,\dots,x_k) is defined, then, on input (x_1,\dots,x_k) the machine M_f terminates and the value f(x_1,\dots,x_k) is written in the memory;
  • if f(x_1,\dots,x_k) is not defined, the machine M_f does not terminate on input (x_1,\dots,x_k).