7.Turing-decidable Languages
A language L⊂Σ∗0 is Turing-decidable iff
function χL:Σ∗0→{Y,N}
is Turing-computable, where for each w∈Σ∗0,
Example: Let Σ0={a}, and let
L={w∈Σ∗0:|w| is even}.
M erases the marks from right to left, with current parity
encode by state.
Once the string is finished, mark Y or
N as appropriate.
Turing-acceptable Languages (3)
Is every Turing-acceptible language Turing decidable?
This is the Halting Problem.
Of course, if the TA language would halt, we write Y.
But if the TA lang would not halt on an accept state, it may loop forever, can we always replace it with
logic to write N instead?
Example: Collatz function.
Does the following loop terminate for ALL positive integers n?
while (n > 1)
if (even(n)) n = n/2;
else n = 3n + 1;