8.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 left to right, with current parity encode by state. Once the string is finished, mark $\fbox{Y}$ or $\fbox{N}$ as appropriate.

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.

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 generate an

infinite loop.

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;