Assignment 5

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

1. (2p) Let NN be the set containing all closed expressions e that implement functions from ℕ to ℕ, i.e. expressions e that, for some function f ∈ ℕ → ℕ, satisfy ∀ n ∈ ℕ. ⟦ e ⌜n⌝ ⟧ = ⌜f n⌝.

   Either prove that the following function is χ-computable, or that it is not χ-computable:

     has-fixpoint ∈ NN → Bool
     has-fixpoint e = if ∃ n ∈ ℕ. ⟦ e ⌜n⌝ ⟧ = ⌜n⌝ then true else false

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

3. (1p) The following Turing machine implements a (total) function on the natural numbers. Which one? The natural number n is represented by 1ⁿ0 (n ones followed by a single zero).

   • Input alphabet: {0, 1}.

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

   • States: {s₀, s₁, s₂}.

   • Initial state: s₀.

   • Transition function:

     • δ(s₀, 1) = (s₀, 1, R)
     • δ(s₀, 0) = (s₁, 1, R)
     • δ(s₁, ␣) = (s₂, 0, R)

4. (2p) Implement a Turing machine (with accepting states) that checks if two natural numbers are equal. The machine should use {0, 1} as the input alphabet; you may use more symbols in the tape alphabet. The machine should accept input of the form 1ⁿ01ⁿ0 (for any n ∈ ℕ). Input of the form 1^m01ⁿ0 where m ≠ n should be rejected.

   Explain how your Turing machine works.

   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.)

5. (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).

6. (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.