8.1. Decideability vs. Acceptability¶
8.1.1. Turing-decidable Languages¶
A language \(L \subset \Sigma_0^*\) is Turing-decidable iff function \(\chi_L: \Sigma^*_0 \rightarrow \{\fbox{Y}, \fbox{N}\}\) is Turing-computable, where for each \(w \in \Sigma^*_0\),\(\chi_L(w) = \left\{ \begin{array}{ll} \fbox{Y} & \mbox{if $w \in L$}\\ \fbox{N} & \mbox{otherwise} \end{array} \right.\)Example: Let \(\Sigma_0 = \{a\}\), and let \(L = \{w \in \Sigma^*_0: |w|\ \mbox{is even}\}\).
\(M\) erases the marks from right to left, with current parity encode by state. Once the string is finished, mark \(\fbox{Y}\) or \(\fbox{N}\) as appropriate.
8.1.2. 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 \(w \in 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.1.3. Turing-acceptable Languages (2)¶
Every Turing-decidable language is Turing-acceptable.If we would have printed \(\fbox{Y}\), then halt on an accept state.If we would have printed \(\fbox{N}\), then do not halt on an accept state.
8.1.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 \(\fbox{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 \(\fbox{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;
