7.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.

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$.

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 \(\fbox{Y}\).
Otherwise, print \(\fbox{N}\).
Need to “clean up” either way.

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.

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 $\fbox{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 $\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;