How to show a language is Partially Decidable?

I am trying to solve some questions on partial decidability of languages and I am getting confused in how to construct proper arguments through the idea of Universal Turing Machine.

I am not posting my questions here, so I would like some examples showing a certain language is partially decidable with a proof.

1 Answer

A language $$L$$ is partially decidable if there is a turing machine $$M$$ such that

• $$M$$ accepts on input $$w$$ if $$w \in L$$
• $$M$$ rejects or runs forever on input $$w$$ if $$w \not\in L$$.

For example, the language $$L = \{\mathrm{enc}(T) : \mathrm{enc}(T) \text{ is the encoding of a TM } T \text{ that halts on } \epsilon \}$$ is partially decidable, since one could define a TM $$M$$ as follows:

 def M(w):
if w == enc(T):
while True:
simulate T(epsilon) for one step
if T has halted:
accept
else:
reject


one would then make a case distinction for every word $$w$$, so if

• $$w \in L$$, then $$w = \mathrm{enc}(T)$$ for a TM $$T$$ that halts on $$\epsilon$$. Therefore, if started with $$w$$, $$M$$ enters the if-part. Since $$T$$ accepts $$\epsilon$$ after a finite number of steps, the $$T$$ will halt eventually and $$M$$ will accept as well.
• $$w \not\in L$$. If $$w$$ is not a valid encoding of a TM, then $$M$$ will reject after the first step. On the other hand, if $$w = \mathrm{enc}(T)$$, then $$T$$ must be a TM that doesn't halt on $$\epsilon$$. In this case, it is easy to see that the while loop never stops and $$M$$ will run forever.