質問

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.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top