Entendo a prova da indecidibilidade do problema da parada (dada, por exemplo, no livro de Papadimitriou), com base na diagonalização.

Embora a prova seja convincente (eu entendo cada etapa dela), não é intuitivo para mim no sentido de que não vejo como alguém a derivaria, partindo apenas do problema.

No livro, a prova é assim: "suponha que resolva o problema de parada em uma entrada , isto é, decida se a máquina de Turing pára na entrada . Construa uma máquina de Turing que use uma máquina de Turing como entrada , executa e reverte a saída. " Depois, ele mostra que não pode produzir uma saída satisfatória. M ; x M x D M M H ( M ; M ) D ( D $M_H$$M;x$$M$$x$$D$$M$$M_H(M;M)$$D(D)$

É a construção aparentemente arbitrária de , particularmente a idéia de alimentar para si mesma e depois para si mesma, para a qual eu gostaria de ter uma intuição. O que levou as pessoas a definir essas construções e etapas em primeiro lugar?M $D$$M$$D$

Alguém tem uma explicação sobre como alguém entraria no argumento da diagonalização (ou alguma outra prova), se não conhecesse esse tipo de argumento para começar?

Adendo dada a primeira rodada de respostas:

Portanto, as primeiras respostas apontam que provar a indecidibilidade do problema de parada foi algo baseado no trabalho anterior de Cantor e Russell e no desenvolvimento do problema de diagonalização, e que começar do zero significaria simplesmente ter que redescobrir esse argumento.

Justo. No entanto, mesmo se aceitarmos o argumento da diagonalização como um dado bem compreendido, ainda acho que existe uma "lacuna de intuição" dele para o problema de parada. Prova de Cantor da incontabilidade dos números reais, na verdade, acho bastante intuitiva; O paradoxo de Russell ainda mais.

O que eu ainda não vejo o que poderia motivar alguém para definir com base em 'auto-aplicação' 's , e depois aplicar novamente para si. Isso parece estar menos relacionado à diagonalização (no sentido de que o argumento de Cantor não tinha algo parecido), embora obviamente funcione bem com a diagonalização depois que você as define.M M ; M $D(M)$$M$$M;M$$D$

PS

O @babou resumiu o que estava me incomodando melhor do que eu: "O problema com muitas versões da prova é que as construções parecem ser arrancadas de um chapéu mágico".

Na sua edição, você escreve:

O que eu ainda não vejo o que poderia motivar alguém para definir com base em 'auto-aplicação' 's , e depois aplicar novamente para si. Isso parece estar menos relacionado à diagonalização (no sentido de que o argumento de Cantor não tinha algo parecido), embora obviamente funcione bem com a diagonalização depois que você as define.M M ; M $D(M)$$M$$M;M$$D$

Um resumo "popular" comum da prova de Turing é mais ou menos assim:

"Se tivéssemos uma máquina que poderia decidir se mais de Turing máquina pára ou não, poderíamos usar isso para construir outra máquina que, dada uma máquina de Turing , pararia se e somente se fez não parar. Mas então poderíamos passar como entrada para si mesmo e, assim, obter um paradoxo: esta máquina pararia se e somente se não parasse! " D M M $M_H$$D$$M$$M$$D$

Agora, é fácil ver que a sumarização acima encobre um detalhe importante - a parada da máquina de Turing também depende de sua entrada, que não especificamos! Mas esse problema pode ser resolvido com bastante facilidade: precisamos apenas que escolha alguma entrada adequada para cada máquina de entrada , antes de passá-las para .D x M M M $M$$D$$x_M$$M$$M_H$

Qual é uma escolha adequada para , já que queremos derivar uma contradição? Bem, uma escolha natural é sugerida diretamente pela prova "ondulada à mão" acima, onde finalmente obtemos a contradição executando a máquina em si mesma.$x_M$$D$

Assim, para que o comportamento de seja realmente paradoxal neste caso, ou seja, quando invocado como , o que queremos é que a interrupção de dependa do comportamento de quando invocado como . Desta forma, vamos obter a contradição queremos definindo .D ( D ) D ( H ) H H ( H ) M = $D$$D(D)$$D(M)$$M$ $M(M)$$M = D$

Veja bem, essa não é a única escolha; também poderíamos ter derivado a mesma contradição, digamos, construindo uma máquina modo que pare se e somente se (em vez de ) não parar. Mas, embora esteja claro que a máquina pode duplicar facilmente sua entrada antes de passá-la para , não é tão óbvio como construir uma máquina que chamaria com seu próprio código como entrada. Assim, o uso desse vez de complicaria desnecessariamente a prova e a tornaria menos intuitiva.D ′ ( M ) M ( D ′ ) M ( M ) D M H D ′ M H D ′$D'$$D'(M)$$M(D')$$M(M)$$D$$M_H$$D'$$M_H$$D'$$D$

Pode ser simplesmente um erro pensar que alguém raciocinaria nesse argumento sem apresentar um argumento semelhante em algum momento anterior, em um contexto "mais simples".

Lembre-se de que Turing conhecia a prova de diagonalização de Cantor da incontabilidade dos reais. Além disso, seu trabalho faz parte de uma história da matemática que inclui o paradoxo de Russell (que usa um argumento de diagonalização) e o primeiro teorema da incompletude de Gödel (que usa um argumento de diagonalização). De fato, o resultado de Gödel está profundamente relacionado à prova de indecidibilidade do Problema da Parada (e, portanto, a resposta negativa ao problema de Entscheidungs ​​de Hilbert).

Portanto, meu argumento é que sua pergunta está, de certo modo, mal fundamentada e que você não pode alcançar o Problema da Parada sem passar pelo resto (ou algo extraordinariamente semelhante) primeiro. Enquanto mostramos essas coisas para os alunos sem passar pela história, se você era um matemático que trabalha, parece improvável que você vá do nada para a Turing Machines sem nada no meio - o objetivo principal era formalizar a computação, um problema que muitas pessoas tinham trabalha há décadas nesse ponto.

Cantor nem usou a diagonalização em sua primeira prova da incontabilidade dos reais. Se considerarmos as datas de publicação como uma aproximação de quando ele pensou na ideia (nem sempre uma coisa confiável), levou cerca de 17 anos para já saber. que os reais eram incontáveis, para elaborar o argumento da diagonalização.

Em referência à "auto-aplicação" na prova que você menciona, isso também é parte integrante do paradoxo de Russell (que depende inteiramente da auto-referência), e o primeiro teorema da incompletude de Gödel é como a versão poderosa do paradoxo de Russell . A prova da indecidibilidade do problema da parada é tão fortemente informada pelo trabalho de Gödel que é difícil imaginar chegar lá sem ela; portanto, a idéia de "autoaplicação" já faz parte do conhecimento básico que você precisa para chegar ao problema da parada . Da mesma forma, o trabalho de Gödel é uma reformulação do paradoxo de Russell, para que você não chegue lá sem o outro (observe que Russell não foi o primeiro a observar um paradoxo como esse, portanto, protótipos do argumento da diagonalização existem na lógica formal desde cerca de 600 aC). Tanto o trabalho de Turing quanto de Gödel (os bits de que estamos falando aqui) podem ser vistos como demonstrações cada vez mais poderosas dos problemas com a auto-referência e como ele está incorporado na matemática. Então, mais uma vez, é muito difícil sugerir que essas idéias no nível que Turing estava lidando com elas vierama priori , eles foram o culminar do trabalho de milênios em partes da filosofia, matemática e lógica.

Essa auto-referência também faz parte do argumento de Cantor, simplesmente não é apresentada em uma linguagem não natural como a obra mais fundamentalmente lógica de Turing. A diagonalização de Cantor pode ser reformulada como uma seleção de elementos do conjunto de potência de um conjunto (essencialmente parte do Teorema de Cantor). Se considerarmos o conjunto de reais (positivos) como subconjuntos dos naturais (observe que realmente não precisamos que os dígitos sejam ordenados para que isso funcione, basta fazer uma apresentação mais simples) e alegar que há uma exceção dos naturais para os reais, então podemos produzir um elemento do conjunto de potências (isto é, um real) que não está na imagem da rejeição (e, portanto, derivar uma contradição), considerando esse elemento como o conjunto de naturais que não são por si só imagem sob a exceção. Depois que a expressamos dessa maneira, é '

A auto-aplicação não é um ingrediente necessário da prova

Em poucas palavras

Se existe uma máquina de Turing que resolve o problema de parada, a partir dessa máquina podemos construir outra máquina de Turing com um comportamento de parada (função característica de parada) que não pode ser o comportamento de parada de qualquer máquina de Turing.$H$$L$

O paradoxo construído sobre a função auto-aplicada (chamada nesta resposta - desculpe pelas inconsistências da notação) não é um ingrediente necessário da prova, mas um dispositivo utilizável na construção de uma contradição específica, ocultando o que parece ser o "real". finalidade "da construção. Provavelmente é por isso que não é intuitivo.$D$$L$

Parece mais direto mostrar que há apenas um número inumerável de comportamentos de parada (não mais que as máquinas de Turing), que podem ser definidos como funções de parada características associadas a cada máquina de Turing. Pode-se definir construtivamente uma função de parada característica que não está na lista e construir a partir dela e de uma máquina que resolve o problema de parada, uma máquina que possui essa nova função de parada característica. Mas como, por construção, não é a função de parada característica de uma máquina de Turing, não pode ser uma. Como é construído a partir de usando técnicas de construção de máquinas de Turing, não pode ser uma máquina de Turing.L L L H $H$$L$$L$$L$$H$$H$

A auto-aplicação de para si mesma, usada em muitas provas, é uma maneira de mostrar a contradição. Mas funciona apenas quando a função de parada característica impossível é construída a partir da diagonal da lista de funções de parada característica permitidas por Turing, invertendo essa diagonal (trocando e ). Mas existem infinitamente muitas outras maneiras de construir uma nova função de parada característica. Então o não-Turing-ness não pode mais ser evidenciado com um paradoxo do mentiroso (pelo menos não simplesmente). A construção de autoaplicação não é intuitiva porque não é essencial, mas parece lisa quando puxada para fora do chapéu mágico.0 $L$$0$$1$

Basicamente, não é uma máquina de Turing porque foi projetada desde o início para ter um comportamento de parada que não é o de uma máquina de Turing e que pode ser mostrado mais diretamente, portanto, de maneira mais intuitiva.$L$

Nota : Pode ser que, para qualquer escolha construtiva da função de parada característica impossível, haja um reordenamento computável da enumeração da máquina de Turing, de forma que ela se torne a diagonal (não sei). Mas, imho, isso não altera o fato de que a autoaplicação é uma técnica de prova indireta que esconde um fato mais intuitivo e interessante.

Análise detalhada das provas

Eu não vou ser histórico (mas graças a quem é, eu gosto), mas estou apenas tentando trabalhar do lado intuitivo.

Eu acho que a apresentação dada ao @vzn , que eu encontrei há muito tempo (eu tinha esquecido), é realmente bastante intuitiva e até explica a diagonalização do nome. Estou repetindo em detalhes apenas porque sinto que o @vzn não enfatizou suficientemente sua simplicidade.

Meu objetivo é ter uma maneira intuitiva de recuperar a prova, conhecendo a Cantor. O problema com muitas versões da prova é que as construções parecem ser retiradas de um chapéu mágico.

A prova que dou não é exatamente a mesma da pergunta, mas está correta, tanto quanto posso ver. Se eu não cometer um erro, é intuitivo o suficiente, pois eu poderia recuperá-lo depois de mais anos do que gostaria de contar, trabalhando em questões muito diferentes.

O caso dos subconjuntos de (Cantor)$\mathbb N$

A prova de Cantor assume (é apenas uma hipótese) que existe uma enumeração dos subconjuntos dos números inteiros, de modo que todo esse subconjunto possa ser descrito por sua função característica que é se e é caso contrário.C j ( i ) 1 i ∈ S j$S_j$$C_j(i)$$1$$i\in S_j$$0$

Isso pode ser visto como uma tabela , de modo queT [ i , j ] = C j ( i $T$$T[i,j]=C_j(i)$

Então, considerando a diagonal, construímos uma função característica tal que , ou seja, é idêntica à diagonal da tabela, com cada bit invertido para o outro valor.D ( i ) = ¯ t [ i , i $D$$D(i)=\overline{T[i,i]}$

Não há nada de especial na diagonal, exceto que é uma maneira fácil de obter uma função característica diferente de todas as outras, e é isso que precisamos.$D$

Portanto, o subconjunto caracterizado por não pode estar na enumeração. Desde que seria verdade de qualquer enumeração, não pode haver uma enumeração que enumera todos os subconjuntos de .$D$$\mathbb N$

É certo que, de acordo com a pergunta inicial, é bastante intuitivo. Podemos tornar a prova do problema de parada tão intuitiva?

O caso do problema da parada (Turing)

Assumimos que temos uma enumeração de máquinas de Turing (que sabemos que é possível). O comportamento de parada de uma máquina de Turing pode ser descrito por função travar a sua característica H j ( i ) que é um se M j paradas na entrada i e é 0 de outra forma.$M_j$$H_j(i)$$1$$M_j$$i$$0$

Isso pode ser visto como uma tabela , de modo que T [ i , j ] = H j ( i $T$$T[i,j]=H_j(i)$

Então, considerando a diagonal, construímos uma função de parada característica tal que D ( i ) = ¯ T [ i , i ] , ou seja, é idêntica à diagonal da tabela, com cada bit invertido para o outro valor.$D$$D(i)=\overline{T[i,i]}$

Não há nada de especial na diagonal, exceto que é uma maneira fácil de obter uma função de parada diferente de todas as outras, e é tudo o que precisamos (veja a nota na parte inferior).$D$

Portanto, o comportamento de parada caracterizado por não pode ser o de uma máquina de Turing na enumeração. Como enumeramos todos eles, concluímos que não existe uma máquina de Turing com esse comportamento.$D$

$T$$H_j$

$H$$H(i,j)$$H_j(i)$

$H$$L$$D$$L$$H$$L(i)$$H(i,i)$$H(i,i)$$1$$L(i)$

$L$$H$$D$$L$$H$

_{Eu deliberadamente imitei a primeira prova e entrei em pequenos detalhes}

Meu sentimento é que os passos ocorrem naturalmente dessa maneira, principalmente quando consideramos a prova de Cantor razoavelmente intuitiva.

Um primeiro enumera as construções litigiosas. Então, toma-se e modifica-se a diagonal como uma maneira conveniente de tocar em todos eles para obter um comportamento não contabilizado, e obtém-se uma contradição exibindo um objeto que não tem o comportamento contabilizado ... se alguma hipótese fosse verdadeira: existência de a enumeração para Cantor e a existência de um oráculo de parada computável para Turing.

$D$$T$$T$$L$$D$$L(i)$$H$$H(i,i)$

Comparação com a "outra" prova

$L$$D$

Nós apenas o construímos de tal maneira que ele possui uma função de parada característica que não corresponde a nenhuma máquina de Turing, e obtemos diretamente uma contradição a partir disso. Isso nos dá a liberdade de não usar a diagonal (pelo que vale a pena).

$L$$j_L$$L=M_{j_L}$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=1$$L(j_L)$$L(j_L)$$T[j_L,j_L]=H(j_L,j_L)=0$$L(j_L)$$L$$L$ não pode ser uma máquina de Turing porque foi construída para ter uma função de parada característica que não é a de uma máquina de Turing.

Um aspecto secundário é que essa prova usual seria muito mais dolorosa se não escolhéssemos a diagonal, enquanto a abordagem direta usada acima não tem nenhum problema. Se isso pode ser útil, eu não sei.

Há também uma prova desse fato que usa um paradoxo diferente, o paradoxo de Berry, que ouvi de Ran Raz.

$B(n)$$n$$S(n)$$n$$B(n)$$S(n)$

Considere o seguinte programa:

1. $n$

2. $L$

3. $L$

$B(n)$$n$$O(\log n)$$n$$O(\log n)$$C\log n$$N$$C\log N \leq N$$N$$B(N)$$B(N)$

A mesma idéia pode ser usada para provar os teoremas da incompletude de Gödel, como mostra Kritchman e Raz .

Há uma idéia mais geral envolvida aqui, chamada "teorema da recursão", que pode ser mais intuitiva: as máquinas de Turing podem usar sua própria descrição (e, portanto, executar-se). Mais precisamente, existe um teorema:

Para qualquer máquina de Turing T, existe uma máquina de Turing Rque calcula R(x) = T(R;x).

Se tivéssemos uma máquina de Turing capaz de resolver o problema de parada, usando a ideia descrita acima, poderíamos facilmente construir uma variedade de máquinas de mentirosa "mentirosas": por exemplo, em notação semelhante a python,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

O argumento mais complicado é essencialmente apenas tentar fazer isso diretamente, sem apelar para o teorema da recursão. Ou seja, está repetindo uma receita para a construção de funções "auto-referenciais". por exemplo, dada uma máquina de Turing T, aqui está uma dessas receitas para construir uma Rsolução satisfatória

R(x) = T(R; x)

Primeiro, defina

S(M; x) = T(M(M; -); x)

onde M(M; -), o que realmente quero dizer é que computamos (usando a descrição de M) e inserimos uma descrição de uma máquina de Turing que, na entrada y, avalia M(M; y).

Agora, observamos que se nos conectarmos Sa si mesmos

S(S; x) = T(S(S; -); x)

nós obtemos a duplicação que queremos. Então, se definirmos

R = S(S; -)

então nós temos

R(x) = T(R; x)

como desejado.

a prova de Turing é bastante semelhante à prova de Cantors de que a cardinalidade dos reais ("incontável") é maior que a cardinalidade dos racionais ("contável") porque eles não podem ser colocados em 1-1 correspondências, mas isso não é observado / enfatizado em muitas referências (alguém conhece alguma?). (iirc) um professor de CS mostrou uma vez isso anos atrás na sala de aula (não sabe onde ele conseguiu isso). na prova Cantors pode-se imaginar uma grade com dimensão horizontal do n ^º dígito do número e da dimensão vertical do n ^º número do conjunto.

a construção à prova de Turing suspensão é muito semelhante, excepto que o conteúdo da tabela são Halt / Nonhalt para 1/0 em vez disso, e o eixo horizontal é n ^th de entrada, e o eixo vertical é n ^th programa de computador. em outras palavras, a combinação de programas e entradas de computador é contável, mas a tabela / matriz infinita é incontável com base na construção de um simulador de máquina universal que pode "virar" uma parada para um caso não-asfaltado, assumindo que existe uma máquina detectora de parada (daí reductio ad absurdam ) .

alguma evidência de que Turing teve a construção de Cantors parcialmente em mente é que seu mesmo artigo com a prova de parada fala sobre números computáveis ​​como (ao longo das linhas de) números reais com dígitos computáveis.

Nesse ponto, vale a pena observar o trabalho de Emil Post, que é (justamente) creditado como co-descobridor dos resultados básicos da computabilidade, embora, infelizmente, tenha sido publicado tarde demais para ser considerado co-descobridor da solução do problema de Entscheidung . Ele certamente participou da elaboração da chamada tese de Church-Turing .

O cargo foi motivado por considerações muito filosóficas, a saber, as limitações teóricas da capacidade humana de calcular ou até obter respostas precisas de maneira consistente . Ele criou um sistema, agora chamado de sistemas canônicos dos correios , cujos detalhes não são importantes, que, segundo ele, poderiam ser usados ​​para resolver qualquer problema que pudesse ser resolvido com facilidade pela manipulação de símbolos . Curiosamente, ele considerou explicitamente os estados mentais como parte da "memória" explicitamente, por isso é provável que ele ao menos considerasse seu modelo de computação um modelo de pensamento humano em sua totalidade.

O Entscheidungsproblem considera a possibilidade de usar tais meios de computação para determinar a teorema de qualquer proposição expressável no sistema dos Principia Mathematica . Mas o PM era um sistema explicitamente projetado para poder representar todo o raciocínio matemático e, por extensão (pelo menos na época, quando o Logicismo ainda estava em voga) todo o raciocínio humano!

Portanto, é muito surpreendente, então, voltar a atenção desse sistema para os próprios sistemas canônicos do Post, assim como a mente humana, através das obras de Frege, Russel e lógicos da virada do século, voltou sua atenção para a faculdade de raciocínio. da própria mente humana.

Portanto, é claro neste momento que a auto-referência, ou a capacidade dos sistemas de se descreverem, era um assunto bastante natural no início dos anos 30. De fato, David Hilbert esperava "iniciar" o próprio raciocínio matemático, fornecendo uma descrição formal de toda a matemática humana, que poderia ser matematicamente comprovada como consistente em si mesma!

Uma vez obtida a etapa de usar um sistema formal para raciocinar sobre si mesma, é um salto e um salto para os paradoxos auto-referenciais usuais (que têm uma história bastante antiga ).

Como todas as afirmações em Principia são consideradas "verdadeiras" em algum sentido metafísico, os Principia podem expressar

programa pretorna resultado truena entradan

se existe um programa para decidir todos os teoremas desse sistema, é bastante simples expressar diretamente o paradoxo do mentiroso:

esse programa sempre mente.

pode ser expresso por

O programa psempre retorna o oposto do que os principia mathematica dizem pque retornará.

A dificuldade está na construção do programa p. Mas, neste ponto, é bastante natural considerar a frase mais geral

O programa psempre retorna o oposto do que o PM diz qque retornará.

para alguns arbitrários q. Mas é fácil construir p(q)para qualquer dado q! Apenas calcule o que o PM prevê que será exibido e retorne a resposta oposta. No entanto, não podemos simplesmente substituir qpor pneste momento, pois ele precebe qcomo entrada e qnão (não requer entrada). Vamos mudar nossa frase para que p seja necessário:

O programa pretorna o oposto do que o PM diz q(r)que retornará.

Arg! Agora, porém, são pnecessárias duas partes de entrada: qe r, considerando qapenas a primeira. Mas espere: queremos pnos dois lugares de qualquer maneira, portanto, rnão é uma nova informação, mas apenas a mesma informação, a saber q! Esta é a observação crítica.

Então finalmente chegamos

O programa pretorna o oposto do que o PM diz q(q)que retornará.

Vamos esquecer esse negócio bobo de "PM diz", e temos

O programa p(q)retorna o oposto do que q(q)retornará.

Este é um programa legítimo, desde que tenhamos um programa que sempre nos diz o que q(q)retorna . Mas agora que temos o nosso programa p(q), podemos substituir qpor pe obter o paradoxo de nosso mentiroso.