Como a solução de Turing para o problema da parada não é simplesmente “falha por projeto”?

Estou tendo dificuldade para ver a solução de Turing para o problema da parada como um lógico, e não como um engenheiro.

Aqui está o meu entendimento do problema da parada:

Seja o conjunto de todas as máquinas de Turing. $M$

Deixe ser o conjunto de todas as entradas para todas as máquinas de Turing em . $i$$M$

Seja todo elemento em um elemento em . $M$$i$

Deixe os valores booleanos e serem elementos em . $true$$false$$i$

Seja uma função que retorne: $h(M,i)$

• $true$ se e somente se parar $M(i)$
• $false$ se e somente se não parar $M(i)$

Seja uma máquina de Turing em que:$p(M)$$M$

• chama$h(M,M)$
• pára se e somente se retornar$h(M,M)$$false$
• não pára se e somente se retornar$h(M,M)$$true$

O que acontece quando chamamos passando para si mesmo, ?$p$$p$$p(p)$

A parte com a qual discordo é a implementação de para que não pare quando for . Meu intestino entende essa abordagem da seguinte maneira:$p(M)$$h(M,M)$$true$

Dado um método que funciona e um método projetado para quebrar , quando combinamos esses métodos para construir uma máquina, essa máquina está quebrada.$h()$$p()$$h()$

Entendo que a prova por contradição é uma abordagem válida para a solução de problemas na lógica formal, mas essa aplicação específica da prova por contradição parece falha de alguma forma.

o que estou perdendo?

A seguir, vou distinguir uma máquina $M$ de sua descrição, denotando a descrição de $M$ de $\langle M\rangle$.

Especificação do programa de teste de parada, $H$

$H$ toma como entrada um par $(\langle M\rangle, i)$, Onde $\langle M\rangle$ é a descrição da máquina $M$e $i$ é a entrada requerida por $M$.

$H$pára em qualquer par de entrada$(\langle M\rangle, i)$ e retorna a resposta correta, a saber:

$H(\langle M\rangle, i)$retorna true se e somente se$M$ pára na entrada $i$.

Agora, supondo que exista essa máquina $H$, podemos usar $H$ como uma sub-rotina para construir um programa $P$ do seguinte modo:

Especificação do programa "perverso" $P$

$P$ toma como entrada uma descrição, $\langle M\rangle$de uma máquina $M$.

$P$funciona corretamente em qualquer entrada$\langle M\rangle$, nomeadamente

$P(\langle M\rangle)$ pára se e somente se $M$ não para quando recebe entrada $\langle M\rangle$.

A chave para esse argumento é que, se pudermos definir uma máquina$H$que sature a especificação acima, então podemos construir uma máquina$P$ isso satisfaz a segunda especificação.

Contudo, $P$, quando dado $\langle P\rangle$, exibe comportamento impossível,

$\qquad\qquad\qquad P(\langle P\rangle)$ pára se e somente se $P(\langle P\rangle)$ não para.

assim $P$falha em cumprir seu segundo requisito em pelo menos uma entrada e, consequentemente, deve ser o caso em que$H$ não pode satisfazer sua exigência, portanto, não podemos fazer $H$ como especificado.

Agora $H$ pode muito bem se comportar conforme especificado em muitas entradas $(\langle M\rangle, i)$, mas o ponto é que não é possível criar um testador de interrupção que funcione em todas as entradas possíveis.

Aqui está como um lógico pode abordar o problema:

$h(M,i)$ é a solução geral do caso para o problema de parada por definição.

$(1)$ $h(M, i)$ deve ser capaz de determinar se deve ou não$M$pára para todos $M$(ou seja, um conjunto irrestrito de$M$ )

$p(M)$ é um elemento em $M$.

$(2)$ As seguintes declarações são equivalentes:

• $p(M)$ pára se e somente se $h(M,M)$ retorna $false$
• $p(M)$ pára se e somente se $p(M)$ não para

$(3)$ Além disso, as seguintes instruções são equivalentes:

• $p(M)$ não pára se e somente se $h(M,M)$ retorna $true$
• $p(M)$ não pára se e somente se $p(M)$ pára

Ambos $(2)$ e $(3)$ são contradições.

$h(M,i)$- a solução geral do caso para o problema de parada - não pode determinar adequadamente se deve ou não$p(M)$ pára, contradizendo $(1)$. Portanto, a solução geral de caso para o problema de parada não existe.

Você diz:

A parte que eu discordo é a implementação $p(M)$ para que não pare quando $h(M,M)$ é $true$. Meu intestino entende essa abordagem da seguinte maneira:

Dado um método $h()$ que funciona, e um método $p()$ projetado para quebrar $h()$, quando combinamos esses métodos para construir uma máquina, essa máquina está quebrada.

O problema é que $p()$ NÃO foi projetado para quebrar $h()$, foi projetado para usar $h()$- e o uso é válido E funciona! Exceto, ele não funciona quando a entrada é$p()$, o que prova que não funciona para todas as entradas.

O que significa que $h()$ não existe, na melhor das hipóteses $hminus()$existe. Não é importante que$p()$ está quebrado, o importante é que $h()$ não existe.

Se alguém diz que escreveu $h()$ você sabe que eles estão enganados ou mentindo, se eles querem trabalhar para criar $h()$ eles estão desperdiçando seu dinheiro, e assim por diante.

Estabelece limites para o que pode e o que não pode ser decidido e os recursos necessários para isso.

Se alguém fizer a pergunta: podemos determinar se $p()$pára devido a esta entrada? As respostas possíveis para isso são: (a) sim - sim, (b) sim - não (c) sim - mas atualmente não sabemos se sim ou não, e finalmente (d) não - é impossível provar de uma maneira ou de outra.

Ser capaz de determinar rapidamente se a resposta é (c) ou (d) pode ser extremamente útil. Lembre-se de que Halting não diz que não podemos provar uma situação específica.$p()$Halting diz que não podemos ter uma solução geral que funcione para qualquer entrada. Restringir$p()$ ou a entrada e a resposta são frequentes, sim, isso é trivial.

Você não deve pensar nisso em termos de "fragilidade", porque existem muitos programas perfeitamente legítimos, projetados para rodar para sempre, portanto, rodar para sempre não é necessariamente um comportamento "quebrado".

pé o seguinte algoritmo simples, assumindo que já temos uma função h(X,Y)que retorna truese a máquina Xpára com a entrada Ye retorna falsese não.

function p(M)
    if (h(M,M)) then
        while (true) do
        endwhile;
    return;

Há outra prova por contradição que você pode gostar, modelada após o paradoxo de Berry. Para uma máquina de Turing$T$, deixei $N(T)$ser a saída da máquina de Turing quando executada em uma fita vazia, interpretada como um número; possivelmente$N(T)$é indefinido, se a máquina nunca parar. Deixei$X_n$ ser o menor número que não pode ser produzido por uma máquina de Turing com no máximo $n$estados (existe um número assim porque existem muitas dessas máquinas de Turing). Suponha que o problema da parada fosse solucionável. Em seguida, poderíamos construir uma máquina de Turing implementando o seguinte algoritmo:

1. Escreva a codificação binária de $n$ na fita.
2. Revise todas as máquinas de Turing que tenham no máximo $n$ e para cada um deles que parar, calcule o número que eles calculam.
3. Emita o menor número que não aparece na etapa 2, que é $X_n$.

Os dois últimos estágios podem ser implementados usando uma máquina de Turing fixa $C$ estados, e o primeiro usando um extra $\log_2 n$estados. No total, obtemos uma máquina de Turing com$\log_2 n + C$ afirma que calcula $X_n$. Quando$n$ é grande o suficiente, chegamos a uma contradição desde $\log_2 n + C \leq n$: por um lado, $X_n$ não deve ser computável usando uma máquina de Turing $n$estados; por outro lado, a máquina acima calcula usando apenas$\log_2 n + C \leq n$ estados.

Eu ouvi essa prova de Ran Raz .

O ponto do problema de parada é que é impossível decidir com um algoritmo se um determinado algoritmo é interrompido. Claro, você pode fornecer algoritmos que sempre serão interrompidos (para todas as entradas fornecidas). No entanto, você não pode decidir isso para todos os algoritmos (por exemplo,$p$) com um algoritmo, portanto, nenhum algoritmo $h$ pode existir.

Dado $p(p(A)))$, para um determinado algoritmo $A$. E se$h$ diz lhe $A$ pára, então o interior $p$ não vai e o exterior $p$ retornará falso. E se$M$ não interrompe o interior $p$ não vai parar, mas o exterior $p$ retornará falso. Portanto, h não pode decidir se p será interrompido.