[Math] Why is showing a language is Turing recognizable trickier than showing Turing decidable

formal-languagesturing-machines

I have written a proof to show that a Turing Decidable languages are closed under union (amongst other things). Later, I have written a proof to show that Turing Recognizable languages are closed under union.

I am supposed to identify why closing a Turing Recognizable language under some operation is trickier to prove than when dealing with Turing Decidable languages. However, the proofs are extremely similar and I am not sure what makes the proofs trickier other than the obvious, that Turing Recognizable may never halt.

I appreciate any suggestions on identifying what it is that make proving Turing Recognizable languages are closed under some operation is trickier than when dealing with Turing Decidable.

Best Answer

To decide whether a string is in the union of two recursive (= Turing decidable) languages $A$ and $B$, you (or an algorithm) can first check whether it's in $A$ and then, if necessary, check whether it's in $B$. In the case of recursively enumerable (= Turing recognizable) languages, that won't work, because, if your string isn't in $A$, then the "check whether it's in $A$" part will run forever and you'll never get around to checking whether it's in $B$.

Related Solutions

[Math] Is the union of undecidable languages not Turing-recognizable

Your construction for $L_2$ assumes that you can decide in finite time whether or not $U$ accepts $t$, such that you can accept if $U$ does not accept $t$.

But you can't do that. That would require you to solve the halting problem for an arbitrary $U$, which is well known to be impossible. You even said yourself that $N$ will not halt (and thus will reject) if $U$ does not halt.

Is this language recognizable (Turing machines)

1) R = "On input <M>
2) for s = 1 to infinity
3)    for each string w of length 3
4)        run M on w for s steps
5)        if M accepts w within s steps then
6)            accept

You are using a "dove tailing" technique.
Note that there are only 8 possible strings of length 3.
So, the loop in line 3 is guaranteed to terminate.
In addition, if M accepts w, it must do so in a finite number of steps s.
So, the loop in line 1 is also guaranteed to terminate if M accepts w.

However, M may possibly loop if it does not accept any string of length 3.

Best Answer

Related Solutions

[Math] Is the union of undecidable languages not Turing-recognizable

Is this language recognizable (Turing machines)

Related Question