Indecidibilidade de saber se um programa retorna verdadeiro ou falso

7

Considere o problema de pegar uma máquina de Turing de entrada e determinar se a célula final é uma 0ou após o término da computação. Nos casos em que ele escreve algo mais ou não pára, você pode dar qualquer resposta (mas você precisa parar e dar alguma resposta em todas as entradas).1

Esse problema é indecidível? Meu intestino diz que deveria ser, mas não consigo encontrar uma redução no problema da parada. Dada uma máquina de Turing que pode ou não parar, podemos configurá-la para terminar com no caso de parar, mas não podemos terminar com nada no caso sem interrupção, de modo que o oráculo poderia simplesmente dizer neste caso, sem ter que descobrir se de fato a máquina para.00

Observe que uma redução na outra direção é simples; se você puder resolver o problema de parada, com uma TM que termine com ou , substituiremos a etapa de escrita por um loop infinito para criar uma nova TM. Se a nova TM parar, dizemos "ele escreve um " e, se não pára, dizemos "ele escreve um ". É garantido que esta resposta esteja correta desde que a MT pare com ou , para que possamos resolver o problema original.0110101

Mario Carneiro
fonte

Respostas:

8

Suponha que você tenha uma função como a que você descreveu:

def haltify(f):
    # Never fails to halt.
    # If 'f' halts, returns f().
    # If 'f' doesn't halt, anything could be returned.
    ... magic ...

Mas então alguém aparece e faz o seguinte:

def evil():
    return not haltify(evil)

Vê o problema?

  1. Se haltify(f)é garantido que ele será interrompido para todos f, eviltambém será garantido que ele será interrompido porque apenas chama haltifyum específico fe inverte a saída.
  2. Desde que para evil, haltify(evil)deve avaliar a mesma coisa que evil().
  3. Então, not haltify(evil)simplifica not evil()e é isso que evil()retorna.
  4. Isso é um problema, porque não há xsatisfação x == not x. O resultado do mal é contraditório.
  5. Portanto, uma das suposições que usamos está errada: ou haltifynão é garantido que ele pare ou que não retorne f()quando houver uma interrupção f.

Exercício de bônus: por que a função não def good(): return haltify(good)causa problemas para interromper, apesar de aparentemente simplificar para o loop infinito def good(): return good()?

Craig Gidney
fonte
Muito agradável. Isso é isomórfico para a resposta de Yuval, mas um pouco menos conciso. Re: Bonus, haltifyescolherá o resultado good()e, em ambos os casos, será auto-consistente, mas ainda assim retornará porque (por magia vodu) haltify(good)pára, por isso não é realmente um loop infinito, mas uma restrição sobre o responda. (Na realidade, a maneira de implementar haltifyé apenas para executar o argumento, caso em que tanto goode evilsão salvos de contradição por divergentes, mas então é claro que somos obrigados a permitir haltifya divergir, o que frustra o ponto.)
Mario Carneiro
Outra questão interessante é se é possível escrever um "compilador otimizador" que recebe uma entrada TM T e gera alguns Tque calcula o mesmo resultado, mas mais rápido. A resposta depende muito dos detalhes das máquinas e é uma área ativa de pesquisa. Este resultado mostra que, para qualquer compilador, existem pelo menos algumas computações infinitas que não podem ser "aceleradas" para serem executadas em tempo finito (que é uma espécie de versão infinita do teorema da incompressibilidade para esquemas de codificação).
Mario Carneiro
@MarioCarneiro, a versão finita também se aplica aqui: existem pelo menos algumas máquinas de turing que sempre executam em tempo finito, mas não podem ser aceleradas.
John Dvorak
Não IEEE 754 NaNsatisfazem x == !x?
cat
@tac Em python, not float('nan')avalia como false. noté também um dos operadores que você não pode sobrecarregar; sempre retorna um bool. (Você pode definir uma conversão personalizada para bool, mas o intérprete verifica se você realmente retornou um bool). Mesmo se houver uma maneira hacky de construir um xem python que satisfaça x == not x, o exemplo foi planejado apenas para ser pedagogicamente correto e não pedanticamente correto.
Craig Gidney
6

Suponha que Mé uma máquina que resolve esse problema; Eu assumo issoMaceita uma máquina de Turing e uma entrada, mas você pode organizar que ela aceite apenas uma máquina de Turing, se preferir. Construímos uma máquina diferenteTisso funciona da seguinte maneira. Na entradax, corre M na máquina x e entrada x, registra a saída como be escreve 1bna célula inicial. Agora corraT em si mesmo para chegar a uma contradição.

Yuval Filmus
fonte
11
Não funciona. Substitua a seguinte restrição no problema original; a máquina de entrada Turing é garantida para parar. De fato, essa redução é errada também para o problema da parada, mas por razões bastante óbvias.
Joshua
Eu não vejo o problema. Talvez você possa explicar isso?
Yuval Filmus 23/03
11
Se a entrada for garantida para interromper, a máquina deve apenas executá-la para encontrar a resposta e, portanto, não poderá deixar de fazê-lo.
Joshua
11
Cada um na sua.
Yuval Filmus 23/03
@ Josué: Você está dizendo que todas as máquinas de Turing de entrada são interrompidas ou que uma máquina de Turing de entrada específica é interrompida? Não há garantia de que todos os insumos sejam interrompidos e, porMpara "apenas executar" a entrada exigiria a identificação das entradas interrompidas.
User2357112 suporta Monica
-3

Sua redução ao problema da parada é direta e lógica. Se sua máquina parar, ela deve parar em algum tempo T com base na construção primitiva de sua entrada. Se o problema da parada for insolúvel, a construção deve ser com perdas; portanto, existe uma máquina para a qual ela adivinha erradamente e para sem ser totalmente avaliada, e uma longa cadeia de XOR força a avaliação completa a alcançar a resposta certa. Portanto, existe uma máquina para a qual ela produz a resposta errada.

De fato, qualquer problema não trivial que não exclua máquinas sem interrupção, pois a entrada se reduz ao problema de interrupção dessa maneira. Ref: https://en.wikipedia.org/wiki/Rice's_theorem

Joshua
fonte
2
Sua resposta não faz muito sentido, infelizmente.
Yuval Filmus 23/03
Não faço ideia do que seu último parágrafo deve significar. A maioria dos problemas não se reduz ao problema de parada; por exemplo, o conjunto de máquinas de Turing que param em cada entrada não é redutível ao problema da parada, mas sim de complexidade estritamente maior(0>T0).
Noah Schweber
@NoahSchweber: É um teorema profundo da ciência da computação. Você não pode provar propriedades não triviais de todas as funções recursivas não tipadas porque não pode resolver o problema de parada. Você precisa restringir o domínio do problema a funções recursivas que são interrompidas.
21718 Joshua Joshua
O teorema de Joshua Rice não é um "teorema profundo da ciência da computação", é um teorema muito básico da teoria da computabilidade. E isso não significa o que você acha que significa - o problema da parada representa um nível muito fraco de indecidibilidade. (O teorema de Rice afirma o oposto do que você escreveu, na verdade: ele diz que o problema de parada é redutível a - isto é, é de complexidade igual ou menor que - qualquer "propriedade não trivial de funções computáveis ​​parciais".) vale a pena reexaminar o básico; Você conhece, por exemplo, o fato de eu ter mencionado acima ( )? 0>T0
Noah Schweber