Is the following problem χ-decidable?
is-pow ∈ CExp → Bool
is-pow p = if ∀ m ∈ ℕ. ∀ n ∈ ℕ. p ⌜(m, n)⌝ ⇓ ⌜mn⌝ then true else false
You can assume that 00 = 1.
Is the following problem χ-decidable?
is-pow ∈ { f ∈ ℕ × ℕ → ℕ | f is χ-computable } → Bool
is-pow f = if ∀ m ∈ ℕ. ∀ n ∈ ℕ. f (m, n) = mn then true else false
You can assume that 00 = 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:
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:
Suggest a method for representing χ programs as strings suitable for manipulation by a Turing machine.
What properties does your method have?