Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?

Question

Say language $L$ is recursively enumerable, but not recursive. Say $a$ and $b$ are symbols of the alphabet and $w$ a word. Say we have the following language:

$L' = \{ aw | w \in L \} \cup \{ bw | w \notin L \}$

That is, $L'$ consists of the words that are in $L$ with an $a$ added at the beginning and the words that are not in $L$ with a $b$ at the beginning.

Is $L'$ not recursive? If we had a Turing Machine $TM$ for $L'$, $TM$ would halt for some positive cases ($w \in L$) but for other positive cases ($w \notin L$) it wouldn't halt. Is it therefore not recursive and recursively enumerable?

From what I understand:

• Recursively enumerable: the Turing Machine will always halt if $w \in L$, otherwise it may or not halt.

• Recursive: it always halts.

• Recursively enumerable, but not recursive: it only halts if $w \in L$; otherwise it loops.

• Not recursively enumerable: no Turing Machine exists.

So I don't know how to classify a language whose Turing Machine halts for some of its words.

EDIT: of course, now that I think about it, if the $TM$ doesn't halt and accept for some words then they didn't belong to the language in the first place.

Answer 1

There are two important misunderstandings in your question.

• You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it.

• If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ and rejects every input not in $L$ and, therefore, it halts on every input. It doesn't make sense to talk about a Turing machine deciding a language but not halting on some input, or not accepting some string that's in the language.

With that in mind, a language $L$ is:

• Recursively enumerable if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$. It may loop or reject strings not in $L$.

• Recursive if there is a Turing machine that accepts every string in $L$ and rejects every string not in $L$.

• Recursively enumerable but not recursive if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$, but no TM that accepts everything in $L$ and rejects everything not in. The "but..." part can be rephrased as "every Turing machine that accepts every string in $L$ must either also accept some string not in $L$ or must loop on some string not in $L$."

• Not recursively enumerable if every Turing machine either accepts at least one string not in $L$, or loops or rejects at least one string in $L$.

For your specific language, I'm going to assume that $\Sigma=\{a,b\}$. If not, then the notation gets a little uglier but nothing fundamental changes.

If $L$ is RE but not recursive, then $$L' =\{aw\mid w\in L\} \cup \{bw\mid w\notin L\}$$ is not RE. suppose it is RE and is accepted by some Turing machine $M$. Then we can decide if $w\in L$ by simulating $M(aw)$ and $M(bw)$ in parallel until one of them accepts. If $M$ accepts $aw$, then $w\in L$; if it accepts $bw$, then $w\notin L$, and one of these two things must happen. This contradicts the assumption that $L$ is not recursive.

Answer 2

Turing machines can halt or not halt. Languages cannot. The category of halting does not apply to them.

We say that a language is recursive if there is a Turing machine which always halts, and accepts exactly the words in the language. It is not the language itself which always halts, but rather the Turing machine that decides it.

In your case, the language $L'$ is not recursive, since $L$ reduces to it. More explicitly, if $L'$ were recursive then you could decide $L$: given an input $w$, run the decider for $L'$ on the word $aw$, and output the result. Since $L$ is not recursive, the only conclusion is that $L'$ also isn't.