If natural numbers are encoded as strings using the method given in Lecture 5, what list of natural numbers does 110110111011110111111011111111100 stand for?
Either prove that the following function is Turing-computable, or that it is not Turing-computable:
halts₀ ∈ TM → Bool
halts₀ tm = if ⟦ tm ⟧ [] is defined then true else false
Either prove that the following function is Turing-computable, or that it is not Turing-computable:
is-constant ∈ TM → Bool
is-constant tm =
if ∃ ys ∈ List Γtm. ∀ xs ∈ List Σtm. ⟦ tm ⟧ xs = ys then true else false
Either prove that the following function is Turing-computable, or that it is not Turing-computable:
is-constant ∈ { (f, tm) | f ∈ Bool → Bool, tm ∈ TM, tm implements f } → Bool
is-constant (f, _) = if ∃ y ∈ Bool. ∀ x ∈ Bool. f x = y then true else false
A member (f, tm) of the set { (f, tm) | f ∈ Bool → Bool, tm ∈ TM, tm implements f } is represented by the representation of tm: ⌜(f, tm)⌝ = ⌜tm⌝.
Either prove that the following function is Turing-computable, or that it is not Turing-computable:
is-constant ∈ { (f, tm) | f ∈ ℕ → Bool, tm ∈ TM, tm implements f } → Bool
is-constant (f, _) = if ∃ b ∈ Bool. ∀ n ∈ ℕ. f n = b then true else false
Is the intensional halting problem for closed χ expressions Turing-computable?
Is the halting problem for Turing machines χ-decidable?
State and prove a version of Rice’s theorem for Turing machines.