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)2 cuja entrada em si é construída da seguinte forma -
- Se (HM) 2 parar na entrada, loop para sempre.
- Senão, pare.
Aqui, temos uma contradição. Portanto, o problema da parada éundecidable.