Existe uma prova mais intuitiva da indecidibilidade do problema de parada do que a diagonalização?

30

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 )MHM;xMxDMMH(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 DDMD

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 DD(M)MM;MD

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".

user118967
fonte
3
Considere a possibilidade de que qualquer prova da existência de conjuntos incontáveis ​​tenha que ser um pouco contra-intuitiva, mesmo se nos acostumarmos ao fato de que eles estão corretos . Considere também a possibilidade de que esta pergunta (se reformulada corretamente) pertença a math.stackexchange.com .
André Souza Lemos
4
Cantor encontrou o argumento da diagonalização, e agora não podemos desaprendê-lo: Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können .
Hendrik Jan
1
Após uma reflexão mais aprofundada, tenho que perguntar por que você acha que isso é tão diferente do paradoxo de Russell. O paradoxo de Russell parece o mesmo se usarmos a notação para significar (isto é, pensar em conjuntos como sendo funções cujos valores são ou ). Então, o paradoxo de Russell é definir e considerar . X SS(X)XStruefalseD(M) = not M(M)D(D)
1
A diagonalização é uma técnica padrão . Claro que houve um tempo em que não se sabia, mas já é padrão há muito tempo, então seu argumento é simplesmente devido à sua ignorância (não quero ser rude, é um fato: você não sabia todas as outras provas que usam essa técnica e, portanto, acham estranho a primeira vez que a veem. Quando você a vê 50 vezes, provavelmente será capaz de entender como ela pode ser aplicada em uma nova situação).
Bakuriu
1
Talvez você leia minha troca de comentários com Luke Mathieson (seguindo sua resposta). Sua resposta explica historicamente por que Turing usou a autoaplicação (uma coisa que você pede na sua pergunta). Parece ser assim que os matemáticos percebiam os problemas na época. Minha própria resposta tenta fornecer uma prova muito simples que não a utiliza (ou pelo menos mostra que não é essencial), o que é outra coisa que você solicita, bem diferente. Possivelmente, posso torná-lo ainda mais simples do que na minha resposta. Por que os professores ainda usam a prova de Turing é uma questão sociológica e pedagógica (?!). cc @HendrikJan
babou 23/05

Respostas:

18

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 DD(M)MM;MD

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 DMHDMMD

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 HMDxMMMH

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. DxMD

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 = DDD(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 DDD(M)M(D)M(M)DMHDMHDD

Ilmari Karonen
fonte
1
Uau, você realmente grocou na minha pergunta! Esse é exatamente o tipo de história que eu estava procurando! Ainda estou lendo tudo, mas parece que essa seria a resposta aceita. Obrigado!
User118967 21/04
18

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, é '

Luke Mathieson
fonte
2
Sim, parece que o objetivo de Turing era recriar a circularidade (da qual vem a diagonalização) usando máquinas, com o objetivo de introduzir uma idéia abstrata de tempo , com a qual falar sobre finitude de uma nova maneira.
André Souza Lemos
Talvez você possa me esclarecer, pois não estou familiarizado com algumas dessas provas. Entendo que essas provas podem ser cunhadas usando auto-referência. Eu posso até acreditar (embora possa precisar de uma prova) que sempre há alguma referência a ser encontrada em qualquer estrutura que seja construída para esse fim. Mas não vejo a necessidade de usá-lo explicitamente para conduzir a prova a sua conclusão. Você pode reformular o argumento de Cantor dessa maneira, mas não precisa. E não vejo por que você precisa fazê-lo pelo problema da parada. Eu posso ter perdido um passo, mas qual?
babou
Para tornar minha observação anterior mais clara, a pergunta original é : " Existe uma prova mais intuitiva da indecidibilidade do problema de parada ... ". Estou omitindo o fim, pois sinto que o OP se queixa principalmente da falta de intuição. Eu acredito que há de fato uma prova mais intuitiva, não usando a auto-referência. Você pode pensar que usar essa prova é pedagogicamente imprudente (como não relacionado ao trabalho de Russell e Gödel), mas se responder à pergunta, qual é o sentido de rejeitá-la? Você parece negar a pergunta em vez de respondê-la.
babou 22/05
@babou Acho que o problema aqui é que estamos respondendo a perguntas diferentes. O OP não foi bem formulado a esse respeito, eu acho. A pergunta repetida no corpo do OP parece-me "como alguém pensou no argumento da diagonalização para provar ..." (parafraseado, é claro), e que "as construções parecem ter sido tiradas de um chapéu mágico" .
Luke Mathieson
@babou, também para elaborar um pouco, com um teclado adequado, não acho que de uma forma ou de outra seja necessariamente pedagogicamente útil (isso dependeria muito do contexto). De fato, para a maioria dos cursos de CS modernos, provavelmente é melhor fazê-lo sem o argumento da diagonalização, a maioria dos estudantes de CS não está matematicamente mais inclinada o suficiente para conhecer os antecedentes que facilitariam a compreensão, mas eu definitivamente estava respondendo à pergunta. pergunta que encerrou o texto original do corpo: ...
Luke Mathieson
9

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.LHL

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.LDL

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 HHLLLHH

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 1L01

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)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 0SjCj(i)1iSj0

Isso pode ser visto como uma tabela , de modo queT [ i , j ] = C j ( i )TT[i,j]=Cj(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 ]DD(i)=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 .NDN

É 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.MjHj(i)1Mji0

Isso pode ser visto como uma tabela , de modo que T [ i , j ] = H j ( i )TT[i,j]=Hj(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.DD(i)=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

THj

HH(i,j)Hj(i)

HLDLHL(i)H(i,i)H(i,i)1L(i)

LHDLH

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.

DTTLDL(i)HH(i,i)

Comparação com a "outra" prova

LD

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).

LjLL=MjLL(jL)T[jL,jL]=H(jL,jL)=1L(jL)L(jL)T[jL,jL]=H(jL,jL)=0L(jL)LL 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.

babou
fonte
Muito bom, obrigado! Parece que, de alguma maneira, você conseguiu contornar as construções auto-aplicáveis ​​que eu achei problemáticas. Agora eu me pergunto por que as pessoas as acharam necessárias em primeiro lugar.
User118967
@ user118967 Tentei enfatizar que o uso da diagonal não é realmente importante. Tudo o que você deseja é definir uma função de parada característica diferente de todas as listadas na tabela e que seja computável das listadas, desde que tenhamos um oráculo de parada. Existem infinitamente muitas dessas funções de parada características. Agora, isso não parece tão visível na prova usual, e pode ser que algumas construções dessa prova pareçam arbitrárias simplesmente porque são, como escolher a diagonal na prova acima. É apenas simples, não essencial.
babou 21/05
@ user118967 Adicionei uma introdução que resume a análise das várias provas. Complementa a comparação entre provas (com e sem auto-aplicação) que são dadas no final. Não sei se eliminei a diagonalização conforme solicitado :) (acho que seria injusto dizer isso), mas insisto em como acabar com a diagonal óbvia. E a prova não usa a autoaplicação, o que parece um truque desnecessário, mas de aparência esperta, ocultando o que pode parecer uma questão mais importante, o comportamento de interrupção.
Babou
@ user118967 Para responder seu primeiro comentário, e depois de ler a resposta mais votada, parece que a principal motivação é o vínculo com o trabalho de Russell e Gödel. Agora não tenho idéia se é realmente essencial para esse fim, e a variante de construção autoaplicável certamente pode ser estudada para esse fim, mas não vejo o sentido de impor isso a todos. Além disso, a prova mais direta parece mais intuitiva e fornece a ferramenta para analisar melhor a versão autoaplicável. Porquê então?
Babou
Sim, eu tendem a concordar com você sobre isso.
User118967 22/05
8

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

B(n)nS(n)nB(n)S(n)

Considere o seguinte programa:

  1. n

  2. L

  3. L

B(n)nO(logn)nO(logn)ClognNClogNNNB(N)B(N)

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

Yuval Filmus
fonte
Talvez esteja no artigo que cito, ou na monografia clássica Kolmogorov Complexity, de Li e Vitányi.
Yuval Filmus
A propósito, você acha que esse método fornece um ataque ao problema NP vs CoNP?
Mohammad Al-Turkistany
Não. Tais problemas estão além de nós no momento.
Yuval Filmus
n
nnn
6

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.


fonte
O primeiro parágrafo não corresponde ao teorema que você cita, que eu conheço pelo nome de teorema smn.
Raphael
@Raphael: É chamado de teorema da recursão no meu livro. :( Minha breve tentativa no google falhou em encontrar nomes alternativos.
Não se preocupe; talvez eu entenda que você esteja errado ou que haja nomes diferentes para a mesma coisa. Dito isto, sua frase "Máquinas de Turing podem usar sua própria descrição" não é suportada pelo teorema que você cita. Na verdade, acho errado: se a função que uma TM calcula dependesse de seu índice, como seriam todas as infinitas TMs que calculam a mesma função?
Raphael
TliarTruenot liar()False
TRR(x)=T(R;x)TRR(x)=T(R;x)
5

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.

vzn
fonte
Além disso, existe de fato uma maneira muito "intuitiva" de ver a indecidibilidade, mas exige muita matemática mais alta para compreender (ou seja, a intuição de um neófito é muito diferente da intuição de um especialista). os matemáticos consideram o problema da parada e os godels como provas idênticas através de um teorema de ponto fixo de Lawvere, mas esse é um fato avançado que ainda não é acessível aos estudantes de graduação. veja problemas de interrupção, conjuntos não-computáveis, problemas matemáticos comuns? Theoretical Computer Science & também pós ligado para refs
vzn
3

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.

cody
fonte