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.


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: 

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.