Problema de parada da máquina de Turing

Input - Uma máquina de Turing e uma string de entrada w.

Problem - A máquina de Turing termina o cálculo da coluna wem um número finito de etapas? A resposta deve ser sim ou não.

Proof- A princípio, vamos supor que tal máquina de Turing existe para resolver esse problema e depois mostraremos que ela se contradiz. Chamaremos esta máquina de Turing como umHalting machineque produz um 'sim' ou 'não' em uma quantidade finita de tempo. Se a máquina de parada terminar em um período de tempo finito, a saída virá como 'sim', caso contrário, como 'não'. A seguir está o diagrama de blocos de uma máquina de parada -

Agora vamos projetar um inverted halting machine (HM)’ como -

• E se H retorna YES e, em seguida, faz um loop para sempre.

• E se H retorna NÃO e depois pára.

A seguir está o diagrama de blocos de uma 'máquina de parada invertida' -

Além disso, uma máquina (HM)₂ cuja entrada em si é construída da seguinte forma -

• Se (HM) ₂ parar na entrada, loop para sempre.
• Senão, pare.

Aqui, temos uma contradição. Portanto, o problema da parada éundecidable.