A prova de Turing - Turing's proof

A prova de Turing é uma prova de Alan Turing , publicada pela primeira vez em janeiro de 1937 com o título " On Computable Numbers, with an Application to the Entscheidungsproblem ." Foi a segunda prova (depois do teorema de Church ) da conjectura de que algumas perguntas puramente matemáticas do tipo sim-não nunca podem ser respondidas por computação; mais tecnicamente, que alguns problemas de decisão são " indecidíveis " no sentido de que não há um único algoritmo que infalivelmente dê uma resposta correta "sim" ou "não" para cada instância do problema. Nas próprias palavras de Turing: "... o que provarei é bastante diferente dos resultados bem conhecidos de Gödel ... agora mostrarei que não há nenhum método geral que diga se uma dada fórmula U é demonstrável em K [ Principia Mathematica ] ... "( Indecidível , p. 145).

Turing seguiu essa prova com outras duas. O segundo e o terceiro dependem do primeiro. Todos dependem de seu desenvolvimento de "máquinas de computação" semelhantes a uma máquina de escrever que obedecem a um conjunto simples de regras e seu subsequente desenvolvimento de uma "máquina de computação universal".

Resumo das provas

Em sua prova de que o Entscheidungsproblem não pode ter solução, Turing partiu de duas provas que conduziriam à sua prova final. Seu primeiro teorema é mais relevante para o problema da parada , o segundo é mais relevante para o teorema de Rice .

Primeira prova : que não existe nenhuma "máquina de computação" que possa decidir se uma "máquina de computação" arbitrária (representada por um inteiro 1, 2, 3,...) É "livre de círculos" (ou seja, continua imprimindo seu número em binário ad infinitum): "... não temos um processo geral para fazer isso em um número finito de etapas" (p. 132, ibid .). A prova de Turing, embora pareça usar o "processo diagonal", na verdade mostra que sua máquina (chamada H) não pode calcular seu próprio número, muito menos o número diagonal inteiro ( argumento diagonal de Cantor ): "A falácia do argumento reside em a suposição de que B [o número diagonal] é computável "( Indecidível , p. 132). A prova não requer muita matemática.

Segunda prova : esta é talvez mais familiar aos leitores como o teorema de Rice : "Podemos mostrar ainda que não pode haver nenhuma máquina E que, quando fornecida com o SD [" programa "] de uma máquina M arbitrária, determinará se M alguma vez imprime um determinado símbolo (0 digamos) "(itálico dele, Indecidível , p. 134).

Terceira prova : "Correspondendo a cada máquina de computação M, construímos uma fórmula Un (M) e mostramos que, se existe um método geral para determinar se Un (M) é demonstrável, então existe um método geral para determinar se M alguma vez imprime 0 "( Indecidível , p. 145).

A terceira prova requer o uso de lógica formal para provar um primeiro lema, seguido por uma breve prova de palavras do segundo:

Lema 1: Se S1 [símbolo "0"] aparecer na fita em alguma configuração completa de M, então Un (M) é demonstrável. ( Indecidível , p. 147)
Lema 2: [O inverso] Se Un (M) for demonstrável, então S1 [símbolo "0"] aparece na fita em alguma configuração completa de M. ( Indecidível , p. 148)

Finalmente, em apenas 64 palavras e símbolos, Turing prova por reductio ad absurdum que "o Hilbert Entscheidungsproblem não pode ter solução" ( Undecidable , p. 145).

Resumo da primeira prova

Turing criou um emaranhado de abreviações. Consulte o glossário no final do artigo para obter as definições.

Alguns esclarecimentos importantes:

A máquina H de Turing está tentando imprimir um número diagonal de 0s e 1s.
Este número diagonal é criado quando H realmente "simula" cada máquina "bem-sucedida" sob avaliação e imprime o R-ésimo "número" (1 ou 0) da R-ésima máquina "bem-sucedida".

Turing gastou grande parte de seu trabalho na verdade "construindo" suas máquinas para nos convencer de sua verdade. Isso foi exigido por seu uso da forma de prova reductio ad absurdum . Devemos enfatizar a natureza "construtiva" dessa prova. Turing descreve o que poderia ser uma máquina real, realmente edificável. O único elemento questionável é a existência da máquina D, que esta prova acabará por mostrar ser impossível.

Turing começa a prova com a afirmação da existência de uma máquina de "decisão / determinação" D. Quando alimentado com qualquer SD (sequência de símbolos A, C, D, L, R, N, ponto e vírgula ";"), ele determinará se isso SD (string de símbolos) representa uma "máquina de computação" que é "circular" - e, portanto, "u insatisfatório" - ou "livre de círculos" - e, portanto, "s satisfatório".

Turing já havia demonstrado em seu comentário que todas as "máquinas de computação - máquinas que calculam um número como 1s e 0s para sempre - podem ser gravadas como um SD na fita da" máquina universal "U. A maior parte de seu trabalho conduziu à sua primeira prova é gasta demonstrando que uma máquina universal realmente existe, ou seja,
 Existe realmente uma máquina universal U
Para cada número N, existe realmente um SD único,
Cada máquina de Turing tem um SD
Cada SD na fita de U pode ser “executado” por U e produzirá a mesma “saída” (figuras 1, 0) que a máquina original.

Turing não faz comentários sobre como a máquina D realiza seu trabalho. Para fins de argumentação, supomos que D primeiro olharia para ver se a sequência de símbolos é "bem formada" (ou seja, na forma de um algoritmo e não apenas uma mistura de símbolos) e, se não, então a descartaria. Em seguida, iria “caçar um círculo”. Para fazer isso talvez ele usasse “heurísticas” (truques: ensinado ou aprendido). Para efeito de prova, esses detalhes não são importantes.

Turing então descreve (um tanto vagamente) o algoritmo (método) a ser seguido por uma máquina que ele chama de H. A máquina H contém em si a máquina de decisão D (portanto, D é uma “sub-rotina” de H). O algoritmo da máquina H é expresso na tabela de instruções de H, ou talvez na descrição padrão de H na fita e unida à máquina universal U; Turing não especifica isso.

No decorrer da descrição da máquina universal U, Turing demonstrou que o SD (sequência de letras semelhante a um “programa”) de uma máquina pode ser convertido em um número inteiro (base 8) e vice-versa. Qualquer número N (na base 8) pode ser convertido em um SD com as seguintes substituições: 1 por A, 2 por C, 3 por D, 4 por L, 5 por R, 6 por N, 7 por ponto e vírgula ";".

Acontece que o número exclusivo (DN) da máquina H é o número "K". Podemos inferir que K é um número imensamente longo, talvez com dezenas de milhares de dígitos. Mas isso não é importante para o que se segue.

A máquina H é responsável por converter qualquer número N em uma string de símbolo SD equivalente para a submáquina D testar. (Em linguagem de programação: H passa um "SD" arbitrário para D e D retorna "satisfatório" ou "insatisfatório".) A máquina H também é responsável por manter uma contagem R ("Registro"?) De números bem-sucedidos (supomos que o número de S.Ds “bem-sucedidos”, ou seja, R, é muito menor do que o número de SDs testados, ou seja, N). Finalmente, H imprime em uma seção de sua fita um número diagonal “beta-primed” B '. H cria este B 'por "simular" (no sentido do computador) os "movimentos" de cada máquina / número "satisfatório"; eventualmente, esta máquina / número em teste chegará ao seu R-ésimo "número" (1 ou 0), e H irá imprimi-lo. H então é responsável por “limpar a bagunça” deixada pela simulação, incrementar N e prosseguir com seus testes, ad infinitum .

Nota: Todas essas máquinas que H está procurando são o que Turing chamou de "máquinas de computação". Estes computam números decimais binários em um fluxo infinito do que Turing chamou de "figuras": apenas os símbolos 1 e 0.

Um exemplo para ilustrar a primeira prova

Um exemplo: suponha que a máquina H testou 13.472 números e produziu 5 números satisfatórios, ou seja, H converteu os números de 1 a 13472 em SDs (cadeias de símbolos) e os passou para D para teste. Como consequência, H calculou 5 números satisfatórios e correu o primeiro para o seu 1 ° "dígito", o segundo para o seu 2 ° dígito, o terceiro para o seu 3 ° dígito, o quarto para o seu 4 ° dígito e o quinto para o seu 5 ° dígito. A contagem agora está em N = 13472, R = 5 e B '= ".10011" (por exemplo). H limpa a bagunça em sua fita e prossegue:

H incrementa N = 13473 e converte "13473" na sequência de símbolos ADRLD. Se a submáquina D considerar ADLRD insatisfatório, então H deixa o registro de contagem R em 5. H aumentará o número N para 13474 e continuará em frente. Por outro lado, se D considerar ADRLD satisfatório, então H irá incrementar R para 6. H irá converter N (novamente) em ADLRD [este é apenas um exemplo, ADLRD é provavelmente inútil] e "executá-lo" usando a máquina universal U até esta máquina em teste (U "executando" ADRLD) imprime seu 6º “dígito”, ou seja, 1 ou 0. H imprimirá este 6º número (por exemplo, “0”) na região de “saída” de sua fita (por exemplo, B '= “.100110”).

H limpa a bagunça e, em seguida, incrementa o número N para 13474.

Todo o processo se desfaz quando H chega ao seu próprio número K. Continuaremos com nosso exemplo. Suponha que a contagem / registro bem-sucedido R esteja em 12. H finalmente chega ao seu próprio número menos 1, ou seja, N = K-1 = 4335 ... 321 4 , e esse número não é bem-sucedido. Então H incrementa N para produzir K = 4355 ... 321 5 , ou seja, seu próprio número. H converte isso para "LDDR ... DCAR" e passa para a máquina de decisão D. A máquina de decisão D deve retornar "satisfatório" (isto é: H deve, por definição, continuar testando, ad infinitum , porque é " livre de círculos "). Portanto, H agora incrementa o valor R de 12 para 13 e, em seguida, converte novamente o número sob teste K em seu SD e usa U para simulá-lo. Mas isso significa que H estará simulando seus próprios movimentos. Qual é a primeira coisa que a simulação fará? Esta simulação K-aka-H cria um novo N ou "redefine" o "antigo" N para 1. Este "K-aka-H" cria um novo R ou "redefine" o "antigo" R para 0. Antigo -H “executa” o novo “K-aka-H” até chegar ao seu 12º dígito.

Mas nunca chega ao 13º dígito; K-aka-H eventualmente chega a 4355 ... 321 5 , novamente, e K-aka-H deve repetir o teste. K-aka-H nunca alcançará a 13ª figura. A máquina H provavelmente apenas imprime cópias de si mesma ad infinitum em uma fita em branco. Mas isso contradiz a premissa de que H é uma máquina de computação satisfatória e não circular que imprime os números 1 e 0 da diagonal para sempre. (Veremos a mesma coisa se N for reiniciado para 1 e R for reiniciado para 0.)

Se o leitor não acreditar nisso, ele pode escrever um "esboço" para a máquina de decisão D (o esboço "D" retornará "satisfatório") e então ver por si mesmos o que acontece no instante em que a máquina H encontra seu próprio número.

Resumo da segunda prova

Com menos de uma página, a passagem das premissas à conclusão é obscura.

Turing procede por reductio ad absurdum . Ele afirma a existência de uma máquina E, que quando dada a SD (Descrição Padrão, isto é, "programa") de uma máquina M arbitrária, determinará se M alguma vez imprimirá um dado símbolo (0 digamos). Ele não afirma que este M é uma "máquina de computação".

Dada a existência da máquina E, Turing procede da seguinte forma:

  1. Se a máquina E existe, então existe uma máquina G que determina se M imprime 0 infinitamente frequentemente, E
  2. Se E existe, então existe outro processo [podemos chamar o processo / máquina G 'para referência] que determina se M imprime 1 infinitamente frequentemente, PORTANTO
  3. Quando combinamos G com G ', temos um processo que determina se M imprime uma infinidade de figuras, E
  4. SE o processo "G com G '" determina que M imprime uma infinidade de algarismos, ENTÃO "G com G'" determinou que M não tem círculo, MAS
  5. Este processo "G com G '" que determina se M é livre de círculos, pela prova 1, não pode existir, PORTANTO
  6. A máquina E não existe.

Detalhes da segunda prova

A dificuldade na prova é o passo 1. O leitor será ajudado ao perceber que Turing não está explicando seu trabalho manual sutil. (Resumindo: ele está usando certas equivalências entre os "operadores existenciais" e "universais" junto com suas expressões equivalentes escritas com operadores lógicos.)

Aqui está um exemplo: suponha que vejamos diante de nós um estacionamento cheio de centenas de carros. Decidimos percorrer todo o lote à procura de: “Carros com pneus furados”. Depois de mais ou menos uma hora, encontramos dois “carros com pneus ruins”. Podemos agora dizer com certeza que “Alguns carros têm pneus ruins”. Ou poderíamos dizer: “Não é verdade que 'Todos os carros têm pneus bons'”. Ou: “É verdade que: 'nem todos os carros têm pneus bons”. Vamos para outro lote. Aqui descobrimos que “Todos os carros têm pneus bons”. Podemos dizer: “Não há um único caso de um carro com um pneu estragado”. Assim, vemos que, se podemos dizer algo sobre cada carro separadamente, podemos dizer algo sobre TODOS eles coletivamente.

Isto é o que Turing faz: a partir de M ele cria uma coleção de máquinas { M 1, M 2, M 3, M 4, ..., Mn } e sobre cada uma ele escreve uma frase: “ X imprime pelo menos um 0” e permite apenas dois “ valores verdade ”, Verdadeiro = em branco ou Falso =: 0 :. Um por um, ele determina o valor de verdade da frase para cada máquina e cria uma sequência de espaços em branco ou: 0 :, ou alguma combinação dos dois. Podemos obter algo como: “ M 1 imprime um 0” = Verdadeiro AND “ M 2 imprime um 0” = Verdadeiro AND “ M 3 imprime um 0” = Verdadeiro AND “ M 4 imprime um 0” = Falso, ... AND “ Mn imprime um 0” = Falso. Ele pega a corda

BBB: 0 :: 0 :: 0: ...: 0: ... ad infinitum

se houver um número infinito de máquinas Mn . Se, por outro lado, se todas as máquinas tivessem produzido um "Verdadeiro", a expressão na fita seria

BBBBB .... BBBB ... ad infinitum

Assim, Turing converteu declarações sobre cada máquina considerada separadamente em uma única "declaração" (string) sobre todas elas. Dada a máquina (ele a chama de G) que criou esta expressão, ele pode testá-la com sua máquina E e determinar se ela alguma vez produz um 0. Em nosso primeiro exemplo acima, vemos que de fato produz, então sabemos que nem todos os M's em nossa seqüência imprima 0s. Mas o segundo exemplo mostra que, como a string está em branco, cada Mn em nossa sequência produziu um 0.

Tudo o que resta a Turing fazer é criar um processo para criar a sequência de Mn's a partir de um único M.

Suponha que M imprima este padrão:

M => ... AB01AB0010AB…

Turing cria outra máquina F que pega M e produz uma sequência de Mn que converte sucessivamente os primeiros n 0 em "0-bar" ( 0 ):

Ele afirma, sem mostrar detalhes, que esta máquina F é realmente construível. Podemos ver que algumas coisas podem acontecer. F pode ficar sem máquinas com zeros , ou pode ter que continuar criando máquinas ad infinitum para “cancelar os zeros”.

Turing agora combina as máquinas E e F em uma máquina composta G. G começa com o M original, então usa F para criar todas as máquinas sucessoras M1, M2 ,. . ., Mn. Em seguida, G usa E para testar cada máquina começando com M. Se E detecta que uma máquina nunca imprime um zero, G imprime: 0: para essa máquina. Se E detecta que uma máquina imprime um 0 (presumimos, Turing não diz), então G imprime :: ou simplesmente pula esta entrada, deixando os quadrados em branco. Podemos ver que algumas coisas podem acontecer.

G não imprimirá zeros, nunca, se todos os Mn imprimem zeros, OR,
G imprimirá ad infinitum 0 se todos os M imprimirão zeros, OR,
G imprimirá zeros por um tempo e então parará.

Agora, o que acontece quando aplicamos E ao próprio G?

Se E (G) determina que G nunca imprime um 0, então sabemos que todos os Mn imprimiram 0s. E isso significa que, como todo o Mn veio de M, o próprio M imprime 0's ad infinitum , OU
Se E (G) determina que G imprime 0, então sabemos que nem todos os Mn imprimem 0's; portanto, M não imprime 0's ad infinitum .

Como podemos aplicar o mesmo processo para determinar se M imprime 1 com frequência infinita. Quando combinamos esses processos, podemos determinar que M continua, ou não, imprimindo 1's e 0's ad infinitum . Portanto, temos um método para determinar se M é livre de círculos. Pela Prova 1, isso é impossível. Portanto, a primeira afirmação de que E existe está errada: E não existe.

Resumo da terceira prova

Aqui, Turing prova "que o problema de Hilbert Entscheidungs ​​não pode ter solução" ( Undecidable , p. 145). Aqui ele

… Mostram que não pode haver um processo geral para determinar se uma dada fórmula U do cálculo funcional K é demonstrável. ( ibid .)

Ambos os Lemas # 1 e # 2 são necessários para formar o necessário "SE E SOMENTE SE" (ou seja, equivalência lógica ) exigido pela prova:

Um conjunto E é computavelmente decidível se e somente se E e seu complemento são computavelmente enumeráveis ​​(Franzén, p. 67)

Turing demonstra a existência de uma fórmula Un (M) que diz, com efeito, que "em alguma configuração completa de M, 0 aparece na fita" (p. 146). Essa fórmula é VERDADEIRA, ou seja, é "construtível", e ele mostra como fazer isso.

Em seguida, Turing prova dois Lemas, o primeiro exigindo todo o trabalho duro. (O segundo é o oposto do primeiro.) Então ele usa reductio ad absurdum para provar seu resultado final:

  1. Existe uma fórmula Un (M). Esta fórmula é VERDADEIRA E
  2. Se o Entscheidungsproblem pode ser resolvido ENTÃO existe um processo mecânico para determinar se Un (M) é demonstrável (derivável), E
  3. Pelos Lemas 1 e 2: Un (M) é provável SE E SOMENTE SE 0 aparecer em alguma "configuração completa" de M, E
  4. SE 0 aparece em alguma "configuração completa" de M ENTÃO existe um processo mecânico que determinará se M arbitrário sempre imprime 0 , E
  5. Pela Prova 2, não existe nenhum processo mecânico que determine se M arbitrário imprime 0 , PORTANTO
  6. Un (M) não é demonstrável (é VERDADEIRO, mas não demonstrável ), o que significa que o Entscheidungsproblem é insolúvel.

Detalhes da terceira prova

[Se os leitores pretendem estudar a prova em detalhes, eles devem corrigir suas cópias das páginas da terceira prova com as correções que Turing forneceu. Os leitores também devem vir equipados com uma sólida formação em (i) lógica (ii) o artigo de Kurt Gödel : " On Formally Undecidable Propositions of Principia Mathematica and Related Systems " (reimpresso em Undecidable , p. 5). Para obter ajuda com o artigo de Gödel, eles devem consultar, por exemplo, Ernest Nagel e James R. Newman , Prova de Gödel , New York University Press, 1958.]

Para acompanhar os detalhes técnicos, o leitor precisará entender a definição de "provável" e estar ciente de "pistas" importantes.

"Provável" significa, no sentido de Gödel, que (i) o próprio sistema de axioma é poderoso o suficiente para produzir (expressar) a frase "Esta frase é provável", e (ii) que em qualquer prova arbitrária "bem formada" os símbolos levam por axiomas, definições e substituição aos símbolos da conclusão.

Primeira dica: "Vamos colocar a descrição de M na primeira forma padrão de §6". A seção 6 descreve a "codificação" muito específica da máquina M na fita de uma "máquina universal" U. Isso requer que o leitor conheça algumas idiossincrasias da máquina universal U de Turing e o esquema de codificação.

(i) A máquina universal é um conjunto de instruções "universais" que residem em uma "tabela de instruções". Separado disso, na fita de U, uma "máquina de computação" M residirá como "código M". A tabela universal de instruções pode imprimir na fita os símbolos A, C, D, 0, 1, u, v, w, x, y, z,: . As várias máquinas M podem imprimir esses símbolos apenas indiretamente, comandando U para imprimi-los.

(ii) O "código de máquina" de M consiste em apenas algumas letras e o ponto-e-vírgula, ou seja , D, C, A, R, L, N,; . Em nenhum lugar dentro do "código" de M os "algarismos" (símbolos) 1 e 0 aparecerão. Se M deseja que U imprima um símbolo do espaço em branco da coleção , 0, 1, então ele usa um dos seguintes códigos para dizer a U para imprimi-los. Para tornar as coisas mais confusas, Turing chama esses símbolos de S0, S1 e S2, ou seja,

em branco = S0 = D
0 = S1 = DC
1 = S2 = DCC

(iii) Uma "máquina de computação", seja ela construída diretamente em uma mesa (como seus primeiros exemplos mostram), ou como código de máquina M na fita da máquina universal U, imprime seu número em uma fita em branco (à direita de M -Code, se houver) como 1 s e 0 s sempre prosseguir para a direita.

(iv) Se uma "máquina de computação" for U + "código M", então "código M" aparecerá primeiro na fita; a fita tem uma extremidade esquerda e o "código M" começa aí e prossegue para a direita em quadrados alternados. Quando o M-código chega ao fim (e deve, por causa da suposição de que estas M-códigos são algoritmos finitos), as "figuras" começará a 1 s e 0 s em quadrados alternados, procedendo à direita para sempre. Turing usa os quadrados alternativos (em branco) (chamados "E" - "apagáveis" - quadrados) para ajudar U + "código M" a acompanhar onde estão os cálculos, tanto no código M quanto nas "figuras" que o a máquina está imprimindo.

(v) Uma "configuração completa" é uma impressão de todos os símbolos na fita, incluindo o código M e "figuras" até aquele ponto, juntamente com a figura que está sendo digitalizada (com um caractere indicador impresso à esquerda do símbolo digitalizado?). Se interpretamos o significado de Turing corretamente, este será um conjunto de símbolos imensamente longo. Mas se todo o código M deve ser repetido não está claro; apenas uma impressão da instrução do código M atual é necessária mais a impressão de todas as figuras com um marcador de figura).

(vi) Turing reduziu o vasto número possível de instruções em "código M" (novamente: o código de M aparecendo na fita) a um pequeno conjunto canônico, um de três semelhantes a este: {qi Sj Sk R ql} Por exemplo, se a máquina estiver executando a instrução #qi e o símbolo Sj estiver no quadrado que está sendo digitalizado, então imprima o símbolo Sk e vá para a direita e vá para a instrução ql : As outras instruções são semelhantes, codificando para "Esquerda" L e "Sem movimento" N .É este conjunto que é codificado pela cadeia de símbolos qi = DA ... A, Sj = DC ... C, Sk = DC ... C, R, ql = DA .... A. Cada instrução é separada de outra por ponto e vírgula. Por exemplo, {q5, S1 S0 L q3} significa: Instrução # 5: se o símbolo digitalizado for 0 , imprima em branco , vá para a esquerda e vá para a instrução # 3. É codificado da seguinte forma

; DAAAAADCDLDAAA

Segunda pista: Turing está usando ideias introduzidas no artigo de Gödel, ou seja, a "Gödelização" de (pelo menos parte da) fórmula para Un (M). Esta pista aparece apenas como uma nota de rodapé na página 138 ( Indecidível ): "Uma sequência de r primos é denotada por ^ (r)" ( ibid .) [Aqui, r entre parênteses está "elevado".] Esta "sequência de primos" aparece em uma fórmula chamada F ^ (n).

Terceira pista: Isso reforça a segunda pista. A tentativa original de Turing na prova usa a expressão:

(Eu) N (u) e (x) (... etc. ...) ( Indecidível , p. 146)

No início do artigo, Turing havia usado essa expressão (pág. 138) e definido N (u) para significar "u é um número inteiro não negativo" ( ibid .) ( Isto é, um número de Gödel). Mas, com as correções de Bernays, Turing abandonou essa abordagem (ou seja, o uso de N (u)) e o único lugar onde "o número de Gödel" aparece explicitamente é onde ele usa F ^ (n).

O que isso significa para a prova? A primeira pista significa que um simples exame do código M na fita não revelará se um símbolo 0 já foi impresso por U + "código M". Uma máquina de teste pode procurar a aparência de DC em uma das cadeias de símbolos que representam uma instrução. Mas essa instrução algum dia será "executada"? Algo precisa "executar o código" para descobrir. Esse algo pode ser uma máquina ou podem ser linhas em uma prova formal, ou seja, Lema # 1.

A segunda e a terceira pistas significam que, como seu fundamento é o artigo de Gödel, a prova é difícil.

No exemplo abaixo, iremos construir um "teorema" simples - um pequeno programa de máquina Post-Turing para "executá-lo". Veremos o quão mecânico pode ser um teorema projetado corretamente. Uma prova, veremos, é apenas isso, um "teste" do teorema que fazemos inserindo um "exemplo de prova" no início e ver o que aparece no final.

Ambos os Lemas # 1 e # 2 são necessários para formar o necessário "SE E SOMENTE SE" (ou seja, equivalência lógica) exigido pela prova:

Um conjunto E é computavelmente decidível se e somente se E e seu complemento são computáveis ​​enumeráveis. (Franzén, p. 67)

Para citar Franzén:

Uma sentença A é considerada decidível em um sistema formal S se A ou sua negação for demonstrável em S. (Franzén, p. 65)

Franzén definiu "provável" anteriormente em seu livro:

Um sistema formal é um sistema de axiomas (expressos em alguma linguagem formalmente definida) e regras de raciocínio (também chamadas de regras de inferência), usados ​​para derivar os teoremas do sistema. Um teorema é qualquer afirmação na linguagem do sistema que pode ser obtida por uma série de aplicações das regras de raciocínio, a partir dos axiomas. Uma prova é uma sequência finita de tais aplicações, levando a um teorema como sua conclusão. ( ibid. p. 17)

Assim, uma "sentença" é uma cadeia de símbolos e um teorema é uma cadeia de cadeias de símbolos.

Turing é confrontado com a seguinte tarefa:

para converter um "programa" da máquina de Turing Universal e os símbolos numéricos na fita (as "figuras" de Turing, símbolos "1" e "0"), em um "teorema" - isto é, uma sequência (monstruosamente longa) de frases que definem as ações sucessivas da máquina, (todas) as figuras da fita e a localização da "cabeça da fita".

Assim, a "sequência de frases" será uma sequência de sequências de símbolos. Os únicos símbolos individuais permitidos virão dos símbolos de Gödel definidos em seu artigo. (No exemplo a seguir, usamos "<" e ">" ao redor de uma "figura" para indicar que a "figura" é o símbolo que está sendo lido pela máquina )

Um exemplo para ilustrar a terceira prova

A seguir, temos que nos lembrar que cada uma das “máquinas de computação” de Turing é um gerador / criador de números binários que começa a trabalhar em uma “fita em branco”. Construído corretamente, ele sempre funciona ad infinitum, mas suas instruções são sempre finitas. Nas provas de Turing, a fita de Turing tinha uma “extremidade esquerda”, mas se estendia para a direita ad infinitum. A título de exemplo a seguir, assumiremos que a “máquina” não é uma máquina universal, mas sim a “máquina dedicada” mais simples com as instruções na Tabela.

Nosso exemplo é baseado em um modelo de máquina Post-Turing modificado de uma Máquina de Turing. Este modelo imprime apenas os símbolos 0 e 1. A fita em branco é considerada toda b's. Nosso modelo modificado exige que adicionemos mais duas instruções às 7 instruções Post – Turing. As abreviações que usaremos são:

R, DIREITA: olhe para a direita e mova a fita para a esquerda, ou mova a cabeça da fita para a direita
L, ESQUERDA: olhe para a esquerda e para mover a fita para a direita, ou mova a cabeça da fita para a esquerda
E, APAGUE o quadrado digitalizado (por exemplo, deixe o quadrado em branco)
P0 ,: IMPRIMIR 0 no quadrado varrido
P1 ,: IMPRIMIR 1 no quadrado varrido
Jb_n, JUMP-IF-branco-para-instrução_ # n,
J0_n, JUMP-IF-0-para-instrução_ # n,
J1_n, JUMP-IF-1 -to-instrucntion_ # n,
HALT.

Nos casos de R, L, E, P0 e P1 após realizar sua tarefa, a máquina continua para a próxima instrução em seqüência numérica; idem para os saltos se seus testes falharem.

Mas, para resumir, nossos exemplos usarão apenas três quadrados. E eles sempre começarão como espaços em branco com o quadrado digitalizado à esquerda: ou seja, bbb. Com dois símbolos 1, 0 e em branco, podemos ter 27 configurações distintas:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

Devemos ter cuidado aqui, porque é bem possível que um algoritmo deixe (temporariamente) espaços em branco entre as figuras e, em seguida, volte e preencha algo. Mais provavelmente, um algoritmo pode fazer isso intencionalmente. Na verdade, a máquina de Turing faz isso - imprime em quadrados alternados, deixando espaços em branco entre as figuras para que possa imprimir símbolos localizadores.

Turing sempre deixava quadrados alternados em branco para que sua máquina pudesse colocar um símbolo à esquerda de uma figura (ou uma letra se a máquina for a máquina universal e o quadrado escaneado estiver realmente no “programa”). Em nosso pequeno exemplo, vamos ignorar isso e apenas colocar símbolos () em torno do símbolo digitalizado, da seguinte maneira:

b (b) 0 significa que "a fita está em branco à esquerda da esquerda em branco, mas deixada em branco está 'em jogo', o quadrado digitalizado está em branco, '0', em branco à direita"
1 (0) 1 significa, "A fita está em branco à esquerda, então 1, o quadrado digitalizado é '0'"

Deixe-nos escrever um programa simples:

início: P1, R, P1, R, P1, H

Lembre-se de que sempre começamos com uma fita em branco. A configuração completa imprime os símbolos na fita seguidos pela próxima instrução:

iniciar configuração: (b) P1,
configuração nº 1: (1) R,
configuração nº 2: 1 (b) P1,
configuração nº 3: 1 (1) R,
configuração nº 4: 11 (b) P1,
configuração nº 5 : 11 (1) H

Vamos adicionar “salto” na fórmula. Quando fazemos isso, descobrimos por que a configuração completa deve incluir os símbolos de fita. (Na verdade, vemos isso melhor abaixo.) Este pequeno programa imprime três “1” s à direita, inverte a direção e move os zeros para a esquerda até atingir um espaço em branco. Iremos imprimir todos os símbolos que nossa máquina usa:

início: P1, R, P1, R, P1, P0, L, J1_7, H
(b) bb P1,
(1) bb R,
1 (b) b P1,
1 (1) b R,
11 (b) P1 ,
11 (1) P0,
11 (0) L,
1 (1) 0 J1_7
1 (1) 0 L
(1) 10 J0_7
(1) 10 L
(b) 110 J0_7
(b) 110 H

Aqui, no final, descobrimos que um espaço em branco à esquerda “entrou em jogo”, então o deixamos como parte da configuração total.

Dado que fizemos nosso trabalho corretamente, adicionamos as condições iniciais e vemos “para onde vai o teorema”. A configuração resultante - o número 110 - é a PROVA.

  • A primeira tarefa de Turing teve que escrever uma expressão generalizada usando símbolos lógicos para expressar exatamente o que seu Un (M) faria.
  • A segunda tarefa de Turing é "Gödelize" esta cadeia de símbolos imensamente longa usando a técnica de Gödel de atribuir primos aos símbolos e elevar os primos a poderes primos, de acordo com o método de Gödel.

Complicações

A prova de Turing é complicada por um grande número de definições e confundida com o que Martin Davis chamou de "detalhes técnicos mesquinhos" e "... detalhes técnicos [que] estão incorretos conforme dados" (comentário de Davis em Undecidable , p. 115). O próprio Turing publicou "A Correction" em 1938: "O autor está em dívida com P. Bernays por apontar esses erros" ( Undecidable , p. 152).

Especificamente, em sua forma original, a terceira prova está gravemente marcada por erros técnicos. E mesmo depois das sugestões de Bernays e das correções de Turing, erros permaneceram na descrição da máquina universal . E confuso, uma vez que Turing foi incapaz de corrigir seu artigo original, algum texto dentro do corpo remete ao primeiro esforço defeituoso de Turing.

As correções de Bernays podem ser encontradas em Undecidable , pp. 152-154; o original deve ser encontrado como "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction," Proceedings of the London Mathematical Society (2), 43 (1938), 544-546.

A versão on-line do artigo de Turing contém essas correções em um adendo; no entanto, as correções para a Máquina Universal devem ser encontradas em uma análise fornecida por Emil Post .

No início, o único matemático a prestar muita atenção aos detalhes da prova foi Post (cf. Hodges p. 125) - principalmente porque ele havia chegado simultaneamente a uma redução semelhante de "algoritmo" para ações de máquina primitivas, então ele interessou-se pessoalmente pela prova. Estranhamente (talvez tenha ocorrido a Segunda Guerra Mundial), Post levou cerca de dez anos para dissecá-lo no Apêndice de seu artigo Recursive Unsolvability of a Problem of Thue , 1947 (reimpresso em Undecidable , p. 293).

Outros problemas se apresentam: em seu Apêndice Post comentou indiretamente sobre a dificuldade do artigo e diretamente sobre sua "natureza de contorno" (Post in Undecidable , p. 299) e "forma intuitiva" das provas ( ibid .). Post teve que inferir vários pontos:

Se nossa crítica estiver correta, uma máquina é considerada livre de círculos se for uma máquina de computação de Turing ... que imprime um número infinito de 0s e 1s. E os dois teoremas de Turing em questão são realmente os seguintes. Não há máquina de Turing ... que, quando fornecida com um número inteiro positivo arbitrário n, determinará se n é o DN de uma máquina de computação de Turing ... que é livre de círculos. [Em segundo lugar], não há máquina de convenção de Turing que, quando fornecida com um inteiro positivo arbitrário n, determinará se n é o DN de uma máquina de computação de Turing ... que sempre imprime um determinado símbolo (0 digamos). (Post in Undecidable , p. 300)

Qualquer pessoa que já tentou ler o jornal entenderá a reclamação de Hodges:

O jornal começou de maneira atraente, mas logo mergulhou (na típica maneira de Turing) em um matagal de obscuros tipos góticos alemães, a fim de desenvolver sua mesa de instruções para a máquina universal. As últimas pessoas a dar uma olhada seriam os matemáticos aplicados que tiveram que recorrer à computação prática ... (Hodges p. 124)

Glossário de termos usados ​​por Turing

1 número computável - um número cujo decimal é computável por uma máquina (ou seja, por meios finitos, como um algoritmo)

2 M - uma máquina com uma mesa de instrução finita e uma cabeça de digitalização / impressão. M move uma fita infinita dividida em quadrados, cada um “capaz de conter um símbolo”. As instruções da máquina são apenas as seguintes: mova um quadrado para a esquerda, mova um quadrado para a direita, no símbolo de impressão do quadrado digitalizado p, apague o quadrado digitalizado, se o símbolo for p então faça a instrução aaa, se o símbolo digitalizado não for p, então faça a instrução aaa, se o símbolo varrido for nenhum, então faça a instrução aaa, se o símbolo varrido for qualquer, faça a instrução aaa [onde “aaa” é um identificador de instrução].

3 máquina de computação - um M que imprime dois tipos de símbolos, os símbolos do primeiro tipo são chamados de “figuras” e são apenas os símbolos binários 1 e 0; os símbolos do segundo tipo são quaisquer outros símbolos.

4 figuras - símbolos 1 e 0 , também conhecidos como “símbolos do primeiro tipo”

Configuração 5 m - o identificador de instrução, seja um símbolo na tabela de instruções, ou uma sequência de símbolos que representam o número da instrução na fita da máquina universal (por exemplo, "DAAAAA = # 5")

6 símbolos do segundo tipo - quaisquer símbolos diferentes de 1 e 0

7 circular - uma máquina de computação malsucedida. Ele não consegue imprimir, ad infinitum, os números 0 ou 1 que representam em binário o número que ele calcula

8 circle-free - uma máquina de computação de sucesso. Ele imprime, ad infinitum, os números 0 ou 1 que representam em binário o número que ele calcula

9 sequência - como em "sequência calculada pela máquina": símbolos do primeiro tipo também conhecidos como figuras, também conhecidos como símbolos 0 e 1.

10 sequência computável - pode ser calculada por uma máquina sem círculo

11 SD - Descrição Padrão: uma sequência de símbolos A, C, D, L, R, N, “;” em uma fita da máquina de Turing

12 DN - Número Descrição: um SD convertido em um número: 1 = A, 2 = C, 3 = D, 4 = L, 5 = R, 6 = N, 7 =;

13 M (n) - uma máquina cujo DN é o número “n”

14 satisfatório - um SD ou DN que representa uma máquina sem círculo

15 U - uma máquina equipada com uma tabela de instruções “universal”. Se U for "fornecido com uma fita no início da qual está escrito o SD de alguma máquina de computação M, U calculará a mesma sequência que M."

16 β ' - “beta-primed”: Um chamado “número diagonal” composto pela enésima figura (ou seja, 0 ou 1) da enésima sequência computável [também: o número computável de H, veja abaixo ]

17 u - insatisfatório, ou seja, circular, SD

18 s - satisfatório, ou seja, SD sem círculo

19 D - uma máquina contida em H (veja abaixo). Quando fornecido com o SD de qualquer máquina de computação M, D testará o SD de M e se for circular, marcará com "u" e se estiver livre de um círculo, marcará com "s"

20 H - uma máquina de computação. H calcula B ', mantém R e N. H contém D e U e uma máquina não especificada (ou processo) que mantém N e R e fornece D com o SD equivalente de N. E também calcula as figuras de B' e monta as figuras de B '.

21 R - um registro, ou contagem, da quantidade de SD bem-sucedido (sem círculo) testado por D

22 N - um número, começando com 1, a ser convertido em SD pela máquina E. E mantém N.

23 K - um número. O DN de H.

Requerido para a Prova # 3

5 m-configuration - o identificador de instrução, ou um símbolo na tabela de instruções, ou uma seqüência de símbolos representando o número da instrução na fita da máquina universal (por exemplo, "DAAAAA = instrução # 5"). No SD de Turing, a configuração-m aparece duas vezes em cada instrução, a string mais à esquerda é a "instrução atual"; a string mais à direita é a próxima instrução.

24 configuração completa - o número (figura 1 ou 0 ) do quadrado varrido, a sequência completa de todos os símbolos na fita e a configuração m (o identificador de instrução, um símbolo ou uma sequência de símbolos que representam um número, por exemplo, "instrução DAAAA = # 5")

25 RSi (x, y) - "na configuração completa x de M o símbolo no quadrado y é Si;" configuração completa "é a definição # 5

26 I (x, y) - "na configuração completa x de M, o quadrado y é varrido"

27 Kqm (x) - "na configuração completa x de M a configuração da máquina (número da instrução) é qm"

28 F (x, y) - "y é o sucessor imediato de x" (segue o uso de Gödel de "f" como função sucessora).

29 G (x, y) - "x precede y", não necessariamente imediatamente

30 Inst {qi, Sj Sk L ql} é uma abreviatura, assim como Inst {qi, Sj Sk R ql} e Inst {qi, Sj Sk N ql} . Veja abaixo.

Turing reduz seu conjunto de instruções a três “formas canônicas” - uma para esquerda, direita e sem movimento. Si e Sk são símbolos na fita.

fita Final
m-config Símbolo Operações m-config
qi Si PSk, L qm
qi Si PSk, R qm
qi Si PSk, N qm

Por exemplo, as operações na primeira linha são PSk = PRINT símbolo Sk da coleção A, C, D, 0, 1, u, v, w, x, y, z ,: e mova a fita PARA A ESQUERDA.

Estes ele ainda abreviou como: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

Na Prova # 3, ele chama o primeiro desses "Inst {qi Sj Sk L ql}" e mostra como escrever a máquina inteira SD como a conjunção lógica (OR lógico): esta string é chamada de "Des (M)" , como em “Descrição-de-M”. ou seja, se a máquina imprimir 0, então 1 e 0 em quadrados alternados à direita ad infinitum, ela pode ter a mesa (um exemplo semelhante aparece na página 119):

q1, branco, P0, R, q2
q2, branco, P-branco, R, q3
q3, branco, P1, R, q4
q4, branco, P-branco, R, q1

(Isso foi reduzido à forma canônica com as instruções "p-blank", por isso difere um pouco do exemplo de Turing.) Se colocá-los na "forma Inst ()", as instruções serão as seguintes (lembrando: S0 está em branco, S1 = 0, S2 = 1):

Inst {q1 S0 S1 R q2}
Inst {q2 S0 S0 R q3}
Inst {q3 S0 S2 R q4}
Inst {q4 S0 S0 R q1}

A redução para a Descrição Padrão (SD) será:

; DADDCRDAA; DAADDRDAAA; DAAADDCCRDAAAA; DAAAADDRDA;

Isso está de acordo com seu exemplo no livro (haverá um espaço em branco entre cada letra e número). A máquina universal U usa os quadrados em branco alternados como locais para colocar "ponteiros".

Referências

  • Turing, AM (1937), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society , 2, 42 (1), pp. 230-65, doi : 10.1112 / plms / s2-42.1. 230
  • Turing, AM (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction", Proceedings of the London Mathematical Society , 2, 43 (6), pp. 544-6, doi : 10.1112 / plms / s2 -43.6.544) ( Versão online .) Este é o artigo da época em que Turing define as máquinas de Turing , mostra que o Entscheidungsproblem é insolúvel.
  • Hans Reichenbach (1947), Elements of Symbolic Logic , Dover Publications, Inc., Nova York.
  • Martin Davis (1965), The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, New York. Os dois artigos do Post referenciados acima estão incluídos neste volume. Outros documentos incluem os de Gödel, Church, Rosser e Kleene.
  • Andrew Hodges (1983), Alan Turing: The Enigma , Simon and Schuster , New York. Cf. Capítulo "O Espírito da Verdade" para uma história que conduz a, e uma discussão de, sua prova.
  • Torkel Franzén (2005), Teorema de Gödel: Um Guia Incompleto para seu Uso e Abuso . AK Peters.