If natural numbers are encoded as strings using the method given in Lecture 6, 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:
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 ∈ Bool → Bool | f is Turing-computable } → Bool
is-constant f = if ∃ y ∈ Bool. ∀ x ∈ Bool. f x = y then true else false
A function in the set { f ∈ Bool → Bool | f is Turing-computable } is represented by the representation of a Turing machine witnessing the Turing-computability of the function.
Either prove that the following function is Turing-computable, or that it is not Turing-computable:
is-constant ∈ { f ∈ ℕ → Bool | f is Turing-computable } → Bool
is-constant f = if ∃ b ∈ Bool. ∀ n ∈ ℕ. f n = b then true else false
Is the intensional halting problem for closed χ expressions Turing-decidable?
Is the halting problem for Turing machines χ-decidable?
State and prove a version of Rice's theorem for Turing machines.