Exercises for the fifth tutorial

Is the following problem χ-decidable?

  is-pow ∈ CExp → Bool
  is-pow p = if ∀ m ∈ ℕ. ∀ n ∈ ℕ. p ⌜(m, n)⌝ ⇓ ⌜mⁿ⌝ then true else false

You can assume that 0⁰ = 1.

Is the following problem χ-decidable?

  is-pow ∈ { (f, e) | f ∈ ℕ × ℕ → ℕ, e ∈ CExp, e implements f } → Bool
  is-pow (f, _) = if ∀ m ∈ ℕ. ∀ n ∈ ℕ. f (m, n) = mⁿ then true else false

You can assume that 0⁰ = 1.

Show how one can, for an arbitrary n ∈ ℕ, construct a Turing machine that, if started on an empty tape (containing nothing but blanks), terminates with n contiguous ones on the tape, and the head at the tape's left end.

You may wish to use Anthony Morphett's Turing machine simulator. (If you go to "Advanced options", then you can choose to use semi-infinite tapes.)

Implement a Turing machine that adds one natural number to another. If the input consists of 1^m01ⁿ0 (for m, n ∈ ℕ), i.e. m ones followed by a zero, n ones, and a final zero, then the machine should terminate with 1^m + n0.

Bonus exercise: Implement truncated subtraction (λ m n. max 0 (m - n)).

What does the following Turing machine do?

• Input alphabet: {0, 1}.

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

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

• Initial state: s₀.

• Transition function:

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

What does the following Turing machine do when given input of the form 111…1#111…1?

• Input alphabet: {1, #}.

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

• States: {s₀, s₁, s₂, s₃, s₄, s₅, s₆, s₇, s₈, s₉}.

• Initial state: s₀.

• Transition function:

  • δ(s₀, 1) = (s₁, ., R)
  • δ(s₀, #) = (s₆, #, R)
  • δ(s₁, 1) = (s₁, 1, R)
  • δ(s₁, #) = (s₂, #, R)
  • δ(s₂, 1) = (s₂, 1, R)
  • δ(s₂, ␣) = (s₃, ␣, L)
  • δ(s₃, #) = (s₄, ␣, L)
  • δ(s₃, 1) = (s₅, ␣, L)
  • δ(s₄, 1) = (s₄, 1, L)
  • δ(s₄, .) = (s₉, 1, L)
  • δ(s₅, 1) = (s₅, 1, L)
  • δ(s₅, #) = (s₄, 1, L)
  • δ(s₆, 1) = (s₆, 1, R)
  • δ(s₆, ␣) = (s₇, ␣, L)
  • δ(s₇, #) = (s₉, ␣, L)
  • δ(s₇, 1) = (s₈, ␣, L)
  • δ(s₈, 1) = (s₈, 1, L)
  • δ(s₈, #) = (s₉, 1, L)

Suggest a method for representing χ programs as strings suitable for manipulation by a Turing machine.

What properties does your method have?