Assignment 5

In order to pass this assignment you have to get at least four points.

1. (1p) Define what a Turing-computable function on the natural numbers is.

2. (1p) What does the following Turing machine do when the input consists of n ones (with n ∈ ℕ)?

   • Input alphabet: {1}.

   • Tape alphabet: {1, #, ␣}.

   • Initial state: s₀.

   • Transition function:

     • δ(s₀, ␣) = (s₃, 1, L)
     • δ(s₀, 1) = (s₁, #, R)
     • δ(s₁, 1) = (s₁, 1, R)
     • δ(s₁, ␣) = (s₂, 1, L)
     • δ(s₂, 1) = (s₂, 1, L)
     • δ(s₂, #) = (s₃, 1, L)

3. (2p) Implement a Turing machine (with accepting states) that checks if two natural numbers are equal. The machine should use {1, =} as the input alphabet; you may use more symbols in the tape alphabet. The machine should accept input of the following form:

   • First n ones, then the symbol =, and then n ones again (with n ∈ ℕ).

   Any other valid input (i.e., any other string formed from symbols in the input alphabet) should be rejected. The machine should always terminate.

   Make sure that you specify the Turing machine completely (the set of states, the alphabets, and so on). In addition to this specification you can also optionally submit your Turing machine in the format used by Anthony Morphett's Turing machine simulator. (If you go to "Advanced options", then you can choose to use semi-infinite tapes.)

4. (2p) Give a formal definition of (a reasonable variant of) two-tape Turing machines. Explain how such a Turing machine is defined, and what its semantics is (what partial function it computes).

5. (2p) Consider the following variant of the basic Turing machines (without accepting states) presented in the lectures:

   • There are three possible directions: {L, R, S}. S means "stay" (do not move the head).

   • The meaning of S is specified formally by extending move with another clause:

       move S t = t

   Give a translation remove-stay that takes Turing machines of this kind to Turing machines of the basic kind. The translation should satisfy the following property for every Turing machine tm of the extended kind:

   • For every input xs and output ys, the result of running tm on xs is ys if and only if the result of running remove-stay tm on xs is ys.

   You do not have to prove formally that this property holds.

   Hint: You can handle the non-moving actions by first moving the head to the right, and then back to the left, using extra states to program this movement.