Um dos exemplos mais famosos de uma linguagem indecidível é o problema de parada .

O problema de parada:

O problema de interrupção é o problema de determinar, dada a descrição de um programa de computador arbitrário e uma entrada, se o programa terminará de executar ou continuará a ser executado para sempre. Mais formalmente, ele pergunta:

* Entrada: `` onde:
* `P` é uma máquina de Turing (ou uma representação de qualquer programa de computador de uso geral).
* `I` é a entrada para a máquina de Turing` p`.
* saída:
* "Sim" se a máquina de Turing `p` interromper (termina de execução) quando recebida entrada` i`.
* "Não" se a máquina de Turing `p` não parar (loops para sempre) quando recebe a entrada` i`.

Por que é indecidível:

O problema de interrupção é indecidível, o que significa que existe * Máquina de Turing (ou algoritmo) que pode resolver corretamente o problema de parada para * todas as entradas possíveis ``.

A prova é normalmente feita por contradição. Suponha que exista * uma máquina de Turing `h` que resolva o problema de parada. `H` toma` `como entrada e saídas" sim "se` p` interromper `i` e" não "se` p` lotes para sempre em `i`.

Em seguida, podemos construir outra máquina de Turing `d` (frequentemente chamada de" diagonalizador ") que usa` h` como uma sub -rotina:

`` `
Turing Machine D (P):
1. Execute H (P, P) // Run H com P como o programa e a entrada
2. Se h (p, p) retornar "Sim" (P pares na entrada P):
Então faça um loop para sempre.
3. Se h (p, p) retornar "não" (p loops para sempre na entrada p):
Então pare.
`` `

Agora, o que acontece quando executamos `d` por si mesmo como entrada:` d (d) `?

* cenário 1:suponha `d (d)` parada.
- Isso significa que na etapa 1, `h (d, d)` retornou "sim" (porque `d` interrompe se e somente se` h (d, d) `diz que` d 'termina na entrada `d`).
- mas se `h (d, d)` retornar "sim", então `d` foi projetado para fazer um loop para sempre (na etapa 2). Isso contradiz nossa suposição de que `d (d)` interrompe.

* Cenário 2:suponha `d (d)` loops para sempre.
- Isso significa que na etapa 1, `h (d, d)` retornou "não" (porque `d` loops para sempre se e somente se` h (d, d) `diz que` d` loops na entrada `d`).
- mas se `h (d, d)` retornar "não", então `d` foi projetado para parar (na etapa 3). Isso contradiz nossa suposição de que `d (d)` loops para sempre.

Como ambos os cenários levam a uma contradição, nossa suposição inicial de que existe uma máquina de Turing `h` que resolve o problema de interrupção deve ser falsa. Portanto, o problema de parada é indecidível.

em termos mais simples: Você não pode escrever um programa que sempre possa prever de maneira confiável se outro programa acabará por parar ou correr para sempre.

Significado:

A indecidibilidade do problema de interrupção tem implicações profundas para a ciência da computação. Isso mostra que existem limites fundamentais para o que os computadores podem calcular. Também serve como base para provar a indecidibilidade de muitos outros problemas. Se você puder mostrar que resolver outro problema permitiria resolver o problema de parada, esse outro problema também deve ser indecidível.