[Math] How to prove whether a language is decidable and/or semi-decidable (or neither) using reduction

formal-languageslogicturing-machines

I think I understand the basics of reduction, however I'm far from confident with using the techniques.

I have a couple of examples that I'm struggling with:

L1 = {< M > | M accepts an infinite amount of strings that end in a}

L2 = {< M > | L(M) ∈ SD}

Here is what I have tried for the first one:
By reduction of ¬H = {: Turing Machine M does not halt on w} to L.

R (< M, w >) =
1. Construct < M# >, where M# operates as follows:
1.1 Save it's input on a second tape
1.2 Erase the tape
1.3 Write w
1.4 Run M on w for n steps, or until it halts
1.5 If M has halted, then intentionally loop
1.6 Else accept
2. Return < M# >

If < M# > exists and semi-decides L, then R semi-decides ¬H.

However, I'm assuming no machine can semi-decide ¬H, thus the language is not in SD or D? But I'm not really sure why, or how…

Any help is appreciated, thank you!

Best Answer

I can't follow your reduction, although there is indeed a (many-one) reduction of $\neg H$ to $L_1$; so, if $L_1$ is semidecidable, $\neg H$ is semidecidable.

You're also right that $\neg H$ is not, in fact, semidecidable; and that therefore $L_1$ is not semidecidable.

To see that $\neg H$ is not semidecidable:

Is $H$ semidecidable?
What do you know about a language, such that it and its complement are semidecidable?

As to the other question: I suspect you are thinking too hard about this one. When is the language accepted by some Turing machine a semidecidable language? (HINT: what does "semidecidable" mean?)

Related Solutions

[Math] Understanding Turing Machines: Recognizable and Decidable langauges

A language $L$ is said to be recursively enumerable if there exists a Turing Machine $M$ satisfying the following conditions:
-For every $\omega \in L$, simulating $M$ on $\omega$ (which we denote $M(\omega)$) results in $M$ halting and accepting $\omega$. -For every $\omega \in \Sigma^{*} \setminus L$, $M$ does not accept $\omega$.

Note that for a recursively enumerable language, any TM accepting $L$ need not halt on inputs outside of the language.

If $L$ is decidable, there must exist some TM that halts on all inputs in addition to the conditions for $L$ being recursively enumerable.

What about languages that aren't recognizable?

No such decider or recognizer would exist. Consider the following language: $L_{NOT-HALT} = \{ \langle M_{i} \rangle, \omega_{i} : M_{i}$ is the $i$th TM and $\omega_{i}$ is the $i$th string in $\Sigma^{*}$ and $M_{i}$ does not halt on $\omega_{i} \}$.

The language $L_{NOT-HALT}$ is not recursively enumerable. No TM can accept every string in $M_{i}$. For some TMs in $L_{NOT-HALT}$, it may be possible to recognize an infinite loop by checking the states and transition function. However, there is no general procedure to do this for all TMs in $L_{NOT-HALT}$. A Cantor diagonal argument proves this. See the undecidability of the halting problem.

Does this clear things up?

Functions corresponding to Turing machines that might not halt but consume bounded tape

Firstly, bounded memory use is not an artifact of Turing machine mechanics. You can ask the same question for any Turing-complete programming language, where it corresponds to whether or not the program uses unbounded memory (defined as appropriate) on a run. For example, if the language supports integer and string variables, then bounded memory means that the integer variables have bounded value and the string variables have values with bounded length.

Secondly, a bounded-memory program must on every input either halt or eventually cycle. I doubt there is a nicer characterization. Note that it is not known whether even the following simple non-halting program f uses bounded memory on every positive integer input or not:

def f(n):
  while n>0:
    if n%2==0: n=n*3+1;
    n=n/2;

Also, it is easy to prove that there is no program that can decide whether a given input is a bounded memory program or not. In fact, via a simple generalization of f, one can show that this decision problem is not only undecidable but actually $Π_2$-complete, implying that it cannot be solved even by a program that has access to the halting oracle (see here).

Best Answer

Related Solutions

[Math] Understanding Turing Machines: Recognizable and Decidable langauges

Functions corresponding to Turing machines that might not halt but consume bounded tape

Related Question