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

19

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?

Alessio Martorana
fonte
Acho que você está entendendo mal a prova de que o problema da parada não é computável. P (P) simplesmente retorna true, porque P sempre determina se um programa é interrompido em tempo finito. Você precisa fazer uma construção um pouco mais complicada para chegar a uma contradição.
Dan Staley
Acho que você obteria respostas melhores e talvez praticamente mais relevantes se perguntasse se existem muitos programas para os quais o problema da parada é solucionável. Afinal, muitos programas são até formalmente verificáveis , o que certamente inclui uma determinação de se eles param com determinadas entradas. Suponho firmemente que esse grupo não possa ser determinado (porque isso equivaleria a resolver ..., você sabe), mas que, para a grande maioria dos programas do mundo real, não há obstáculos para dizer se eles são interrompidos ou não, para insumos relevantes.
Peter - Restabelece Monica

Respostas:

10

Se é alguma função computável, então g , definido comofg

g(n)={f(n)E se nkvde outra forma

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 .Pg(n)nn=kif then elsePg(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").

chi
fonte
1
Ok, acho que entendi matematicamente ... Mas eu estava pensando: se tentaria escrever um programa que calculasse a HP, quais problemas concretos eu enfrentaria? Por que e como, em algum momento, eu entenderia que não posso escrever esse programa?
Alessio Martorana
@AlessioMartorana Depende: como você abordaria esse problema? Uma questão principal é que sempre deve parar, mesmo quando sua entrada é um programa sem interrupção - para que você não possa simplesmente tentar simular o programa de entrada. P
chi
E supondo que possamos ver o código do programa de entrada? Não podemos, pelo código, ver se o programa é interrompido?
Alessio Martorana
2
@AlessioMartorana Podemos realmente ver o código, mas se houver, por exemplo, um loop while, não podemos dizer muito em geral. Um loop while pode verificar todas as provas possíveis de uma conjectura matemática arbitrária e parar apenas se uma prova for encontrada. Decidir se esse loop é interrompido significa decidir se a conjectura é comprovável. A solução da HP nos daria uma máquina que responderia Sim (comprovável) / Não (não comprovável) a qualquer pergunta matemática formal. Isso seria irrealisticamente poderoso.
chi
1
@AlessioMartorana Se você pensou que tinha escrito um programa que resolve o HP, o seu programa falharia de duas maneiras: para alguns programas, ele pode retornar o resultado errado (dizer algo pára quando não diz ou diz algo não '' pare quando isso acontecer) e / ou seu próprio programa decisório não interromperá muitas entradas com você incapaz de saber se realmente não vai parar ou se precisa de mais tempo para calcular a resposta.
Shufflepants 9/03/19
21

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.P1,P2,...PEuEuEuPPP

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

David Richerby
fonte
15
Suspeito que sua última frase provavelmente seja verdadeira, mas não acho que, porque uma propriedade seja indecidível, restringir o conjunto de entradas com base nessa propriedade deixará o problema indecidível. Como um exemplo idiota, se você restringisse o conjunto de entradas para encerrar programas (uma propriedade indecidível), o problema seria decidido (por um programa que sempre retornava verdadeiro).
Owen
3
@ Owen Quando a restrição em si é indecidível, você não pode impor a restrição para que ela não possa comprar nada na realidade.
David Richerby
5

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.

Antonio Perez
fonte
O que isso tem a ver com goto? Não podemos ter um programa que use goto e ainda decida se é interrompido, desde que modele uma máquina de estados finitos?
Bergi 08/0318
Eu ia escrever sobre parada em termos de para-loops, e em seguida, mudou-lo apenas para falar sobre máquinas de estados finitos e outros enfeites
Antonio Perez
4

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.

Dmitry Grigoryev
fonte
3

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

Φ

UMABΦ(UMA)Φ(B)

xx

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.

NkBB(k)

Anton Golov
fonte
1
N
1
O último parágrafo se assemelha a Busy Beaver.
Mal
Com relação às restrições "bastante drásticas": total de linguagens de programação é uma coisa. Eles tendem a exigir um grau relativamente alto de sofisticação, então talvez você considere isso drástico, mas é possível resolver problemas reais em um espaço de programas que provadamente são interrompidos.
quer
Incluir um link para en.wikipedia.org/wiki/Rice%27s_theorem faria sentido na IMO.
Dmitry Grigoryev
Obrigado, atualizei a resposta. @BenMillwood Certamente, mas como a solução é "fazer tudo parar", não tenho certeza de que é realmente o que Alessio está procurando. Um caso em que o comportamento de parada é decidível, mas não trivial, seria interessante: talvez os tipos co-indutivos Agda +?
Anton Golov 9/0318
0

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.

John Coleman
fonte