Indecidibilidade de saber se um programa retorna verdadeiro ou falso

Considere o problema de pegar uma máquina de Turing de entrada e determinar se a célula final é uma $0$ ou 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. $0$ $0$

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. $0$ $1$ $1$ $0$ $1$ $0$ $1$

undecidability decision-problem halting-problem Mario Carneiro
fonte

Respostas:

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?

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.
Desde que para evil, haltify(evil)deve avaliar a mesma coisa que evil().
Então, not haltify(evil)simplifica not evil()e é isso que evil()retorna.
Isso é um problema, porque não há xsatisfação x == not x. O resultado do mal é contraditório.
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

$T$ e gera alguns

T^{'}

$T'$ que 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

Suponha que $M$ é uma máquina que resolve esse problema; Eu assumo isso $M$ aceita 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 diferente $T$ isso funciona da seguinte maneira. Na entrada $x$ , corre $M$ na máquina $x$ e entrada $x$ , registra a saída como $b$ e escreve $1-b$ na célula inicial. Agora corra $T$ em si mesmo para chegar a uma contradição.

Yuval Filmus
fonte

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

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

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, por

M

$M$ para "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

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^{″} >_{T} 0^{'})

$(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^{″} >_{T} 0^{'}

$0''>_T0'$

Noah Schweber