8.2. Decideability vs. Acceptability¶
8.2.1. Turing-decidable Languages¶
A language L⊂Σ∗0 is Turing-decidable iff function χL:Σ∗0→{Y,N} is Turing-computable, where for each w∈Σ∗0,χL(w)={Yif w∈LNotherwiseExample: Let Σ0={a}, and let L={w∈Σ∗0:|w| is even}.
M erases the marks from left to right, with current parity encode by state. Once the string is finished, mark Y or N as appropriate.
8.2.2. Turing-acceptable Languages (1)¶
Turing-decideable: M accepts a string w if M halts on a final state for the input w, and rejects a string if it halts on a non-final state.Alternative: M accepts a language iff M halts on w iff w∈L.In other words, the machine does not halt if w is not in L.A language is Turing-acceptable if some Turing machine accepts it.
8.2.3. Turing-acceptable Languages (2)¶
Every Turing-decidable language is Turing-acceptable.If we would have printed Y, then halt on an accept state.If we would have printed N, then generate aninfinite loop.
8.2.4. Turing-acceptable Languages (3)¶
Is every Turing-acceptible language Turing decidable?This is the Halting Problem.Of course, if the Turing-acceptable language would halt, we write Y.But if the TA language 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;
