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 ∈ ℕ × ℕ → ℕ | f is χ-computable } → 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 a Turing machine simulator.

Implement a Turing machine that adds one natural number to another. If the input consists of m ones, followed by the symbol +, followed by n ones (with m, n ∈ ℕ), then the machine should terminate with an output consisting of m + n ones. Make sure that the head ends up at the tape's left end.

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, #, ␣}.

• Initial state: s₀.

• Transition function:

  • δ(s₀, _) = (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, #, ., ␣}.

• 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?