TÖL203F Algorithms, Logic and Complexity

Homework 4

We have now seen Turing machines and how Turing computability is defined. Next week we will look at uncomputable problems, such as the Halting Problem from Chapter 4.

Homework

  1. Problem 3.1 on page 34 in the textbook. Show the Turing machine and give a short description of it.

  2. Problem 3.3 on page 34 in the textbook. Show the Turing machine and give a short description of it.

  3. Problem 3.5 on page 34 in the textbook. Give at least a detailed description of the Turing machine, preferably the full machine.

  4. Implement the function f(n) = floor(n/2) as a Turing machine. Have it start in the standard initial configuration and end in the standard final configuration.

  5. Implement the function minus(p, q) as a Turing machine (i.e. subtract q from p). Assume that p > q.

Hand this homework in before 12:00 on friday January 31st.

hh (hja) hi.is, January 24th, 2014.