TÖL203F Algorithms, Logic and Complexity

Homework 10

We have seen how Turing machines can be simulated by recursive functions (8.1), thus closing the circle of simulations between Turing machines, abacus machines and recursive functions. We also looked at some results that we can prove based on the equivalence between the three models (8.2). We skip sections 8.3, so next week we will start on chapter 9 on first-order logic syntax.

Homework

  1. Problem 8.1 on page 97 in the textbook.

  2. Problem 8.2 on page 97 in the textbook.

  3. Assume that M is a Turing machine, with code number m, that will never use more than tx steps on input x. Show that the function F(m, x) simulating M is primitive recursive (not just recursive).

  4. Assume that a Turing machine has one tape but k read heads, where each read head moves or writes independently based on the symbol it sees and the state of the machine. Show that this multi-head Turing machine is equivalent to the version that we have used.

  5. Researchers have been interested in finding the smallest Universal Turing machines, i.e. the smallest Turing machine that can simulate any other Turing machine. Stephen Wolfram had a candiate machine, but couldn't prove it, so he announced a $25.000 prize for a proof. The prize was won by a 20 year old student from Birmingham.
    Describe the machine in the way we are used to (i.e. with a state diagram and transitions as labelled arrows). and briefly describe how it simulates other Turing machines (no detailed description needed!).

Hand this homework in before 12:00 on friday March 14th.

hh (hja) hi.is, March 7th, 2014.