Considere agora o Problema Lambda, que consiste em decidir se uma máquina de Turing arbitrária M para (halts) quando a sua computação é inicia...

O Problema Lambda é semi-decidível. Isso significa que existe uma máquina de Turing que pode decidir se uma outra máquina de Turing arbitrária M para (halts) quando a sua computação é iniciada com uma fita vazia, mas essa máquina não pode decidir se M não para. A prova de que o Problema Lambda é semi-decidível pode ser feita construindo uma máquina de Turing que simula a execução de M em uma fita vazia. Se M parar, a máquina de Turing de simulação também para e aceita a entrada. Se M não parar, a máquina de Turing de simulação entra em um loop infinito e não aceita a entrada. No entanto, não é possível construir uma máquina de Turing que decida se M não para, pois isso implicaria em resolver o Problema da Parada, que é conhecido por ser indecidível.