Processing math: 100%

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,
χL(w)={Yif wLNotherwise

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 (1)

M accepts a string w if M halts on a final state for the input w.
M accepts a language iff M halts on w iff wL.
A language is Turing-acceptable if some Turing machine accepts it.

Turing-acceptable Languages (2)

Can a Turing acceptable be rewritten to be Turing decidable?
Of course. Instead of just accepting a string in the language, print Y.
Otherwise, print N.
Need to “clean up” either way.
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 do not halt on an accept state.

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;