O problema de parada é computável para entradas / suposições específicas

Pelo meu entendimento da prova de que o problema de parada não é computável, esse problema não é computável porque, se tivermos um programa P (x) que calcula se o programa x pára ou não, temos um paradoxo ao fornecer P como entrada para o mesmo P, tendo: P (P), tentando decidir se P pára ou não usando P em si.

Portanto, minha pergunta é: o problema de parada é computável pelo programa P para todos os outros programas usados ​​como entrada, exceto pelo próprio P? Em outras palavras: o problema da parada não é computável apenas neste caso especial ou a prova é mais geral e estou perdendo alguma coisa?

Se é alguma função computável, então g , definido como$f$$g$

também é computável, para qualquer escolha de .$k,v$

Basicamente, se você tem um programa que calcula g ( n ) para todos os n ' s, exceto n = k , você pode "consertar" esse caso (por exemplo, usando a ) e obter outro programa P que calcula g ( n ) para tudo n .$P'$$g(n)$$n$$n=k$if then else$P$$g(n)$$n$

Portanto, se você pudesse calcular a função de parada "exceto em um caso", também poderia calcular a função de parada (sem exceções). A partir disso, você pode obter uma contradição como de costume.

Conclusão: não, você não pode decidir o problema da parada "exceto um caso" (nem "exceto casos finitos").

o problema de parada é computável pelo programa P para todos os outros programas usados ​​como entrada, exceto pelo próprio P?

Não. Considere a sequência infinita de programas de , onde P i é "mover a cabeça de i  quadrados para a direita, em seguida, i  quadrados para a esquerda, em seguida, fazer exatamente o P faria." Cada um desses programas produz exatamente a mesma saída que  P para cada entrada (incluindo loop permanente se P repetir para  sempre), mas todos são programas diferentes.$P_1, P_2, \dots$$P_i$$i$$i$$P$$P$$P$

E você não pode contornar isso exigindo apenas que o trabalhe em programas que não são funcionalmente equivalentes a si próprio, pois essa propriedade também é indecidível. Talvez o problema seja decidível quando restrito a essas instâncias (embora eu suspeite que não), mas o conjunto de instâncias é indecidível, portanto você não pode realmente executar a restrição.$P$

Existem algoritmos para mostrar que certas classes de programas são interrompidas ou não. Por exemplo,

• É possível determinar algoritmicamente se um programa que modela uma máquina de estado finito é interrompido.
• É possível determinar aritmeticamente se uma máquina de turing de limite linear pára
• Se você souber em qual classe de complexidade um programa está, você saberá que o programa é interrompido para entradas finitas.

Embora não haja algoritmo para determinar se um programa arbitrário é interrompido, a maioria do código foi projetada para parar (como a maioria das sub-rotinas) ou não (como um loop infinito para manipular eventos), e é possível determinar por algoritmo qual é qual. Em outras palavras, você pode ter um algoritmo que responda "pára", "não pára" ou "não sei", e esse algoritmo pode ser projetado para cobrir programas suficientes que seriam úteis.

As provas por contradição não precisam ser exaustivas , basta um único contra-exemplo. A prova de que o problema de parada é indecidível fornece um exemplo de P para o qual a propriedade de parada não pode ser decidida. Essa prova não afirma que P é o único programa desse tipo; de fato, podem existir provas independentes construindo classes completamente diferentes de P.

A prova é realmente mais geral: o problema da parada é um caso especial do teorema de Rice , que afirma

$\Phi$

$A$$B$$\Phi(A)$$\Phi(B)$

$x$$x$

Você pode obter alguns resultados restringindo o espaço dos programas com os quais deseja trabalhar, embora essas restrições tenham que ser bastante drásticas. Por exemplo, se você tem a garantia de que o programa que você recebe pára em 100 etapas ou é executado para sempre, decidir se é interrompido fica fácil.

$N$$k$$BB(k)$

Seja R qualquer conjunto recursivamente enumerável, mas não recursivo. Existem infinitamente muitos desses conjuntos. Seja T uma máquina de Turing que pare na entrada k se e somente se k estiver em R. Esse T existe para qualquer conjunto recursivamente enumerável. É impossível escrever um programa que possa resolver o problema de parada para esse T. Isso ocorre porque qualquer algoritmo para determinar se T pára produz um algoritmo para determinar a associação em R, o que é impossível se R não é recursivo. Como existem R infinitos, cada um dos quais fornece máquinas de Turing diferentes, existem infinitas máquinas de Turing nas quais qualquer tentativa de interromper o programa P falharia.