A história da tese de Church-Turing ("tese") envolve a história do desenvolvimento do estudo da natureza das funções cujos valores são efetivamente calculáveis; ou, em termos mais modernos, funções cujos valores são algoritmicamente computáveis. É um tópico importante na teoria matemática moderna e ciência da computação, particularmente associada com o trabalho de Alonzo Church e Alan Turing.
O debate e a descoberta do significado de "computação" e "recursividade" tem sido longa e controverso. Este artigo fornece detalhes deste debate e a descoberta dos Axiomas de Peano, em 1889, passando pela recente discussão sobre o significado de "axioma".
Axiomas de Peano Em 1889, Giuseppe Peano apresentou Os princípios da aritmética, apresentados por um novo método, baseado na obra de Dedekind. Soare propõe que a origem da "recursão primitiva" começou com os axiomas de Peano, embora "Bem antes do século XIX os matemáticos usavam o princípio da definição de uma função por indução. Em 1888 Dedekind provou, usando axiomas aceitos, que tal definição define uma única função, e aplicou-o para a definição das funções m+n, m x n, e mn. Com base neste trabalho de Dedekind, Peano em 1889 e 1891, escreveu o familiar cinco [sic] axiomas para os inteiros positivos. Como um companheiro para o seu quinto [sic] axioma, indução matemática, Peano usou definição por indução, o que tem sido chamado de recursão primitiva (desde Péter em 1934 e Kleene em 1936) ... ."Soare 1996:5 Observe que, de fato, os Axiomas de Peano são 9 em número e o axioma 9 é o axioma da recursividade/indução.cf: van Heijenoort 1976:94 "Posteriormente, os 9 axiomas foram reduzidos à 5 como "Axiomas 2, 3, 4 e 5, que tratam de identidade, pertencem à lógica subjacente. Isso deixa os cinco axiomas que tornaram-se universalmente conhecidos como "os Axiomas de Peano ... Peano reconhece (1891b, p. 93) que seus axiomas vêm de Dedekind ... ."van Heijenoort 1976:83
Hilbert e o Entscheidungsproblem No Congresso Internacional de Matemáticos, em 1900, em Paris, o famoso matemático David Hilbert, apresentou um conjunto de problemas – agora conhecido como os Problemas de Hilbert – o seu farol iluminando o caminho para os matemáticos do século XX. Os problemas de Hilbert 2 e 10 introduziram o Entscheidungsproblem (o "problema de decisão"). Em seu 2º problema, ele pediu uma prova de que "aritmética" é "consistente". Kurt Gödel iria provar, em 1931, que, dentro do que ele chamou de "P" (hoje chamados de Aritmética de Peano), "existem sentenças indecidíveis [proposições]".Gödel 1931a in (Davis 1965:6), 1930 in (van Heijenoort 1967:596) Devido a isso, "a consistência de P não é provável em P, desde que P seja consistente".Gödel’s theorem IX, Gödel 1931a in (Davis 1965:36) Enquanto a prova de Gödel apresentava as ferramentas necessárias para Alonzo Church e Alan Turing para resolver o Entscheidungsproblem, ele próprio não o respondeu.
É dentro do décimo problema de Hilbert em que a questão de um "Entscheidungsproblem" na verdade aparece. O cerne da questão foi o seguinte questionamento: "O que queremos dizer quando dizemos que uma função é "efetivamente calculável'"? A resposta seria algo para este efeito: "Quando a função é calculado através de procedimentos mecânicos (processo, método)." Apesar de facilmente afirmado hoje em dia, a pergunta (e resposta) seria passaria sem resposta por quase 30 anos antes de ser construída precisamente.
A descrição original do décimo problema de Hilbert começa da seguinte maneira: "10. Determinação da solubilidade de uma equação Diofantina. Dada uma equação Diofantina com um número qualquer de quantidades desconhecidas e coeficientes racionais integrais: Ache um processo pelo qual é possível determinar em um número finito de operações se a equação tem solução racional em números inteiros.This translation, and the original text in German, appears in (Dershowitz and Gurevich 2007:1-2) Por volta de 1922, a pergunta específica de um "Entscheidungsproblem" aplicada a equações Diofantinas haviam desenvolvido para a questão mais geral sobre um "método de decisão" para qualquer fórmula matemática. Martin Davis explica isso da seguinte maneira: Suponha que temos um "procedimento calculacional" que consiste de (1) um conjunto de axiomas e (2) uma conclusão lógica escrita em lógica de primeira ordem, que é escrito em que Davis chama de "Regras de dedução de Frege" (ou o equivalente moderno da lógica Booleana). A tese de doutorado de GödelGödel 1930 in (van Heijenoort 1967:592ff) provou que as regras de Frege eram completas "... no sentido de que cada fórmula válida era provável".van Heijenoort 1967:582 Dado este fato encorajador, poderia haver um "procedimento calculacional" generalizado que poderia nos dizer se uma conclusão poderia ser derivada a partir de suas premissas? Davis, chama tais procedimentos calculacionais de "algoritmos". O Entscheidungsproblem seria um algoritmo, sendo assim. "Em princípio, um algoritmo para [o] Entscheidungsproblem teria reduzido todo o raciocínio dedutivo humano para cálculos brutos".Davis 2000:146
Em outras palavras: existe um "algoritmo", que pode dizer-nos se qualquer fórmula é "verdadeira" (i.e. um algoritmo que sempre corretamente produz uma decisão "verdade" ou "falsidade"?) "... parecia claro para Hilbert, que com a solução deste problema, o Entscheidungsproblem, que deve ser possível, em princípio, resolver todas as questões matemáticas de uma maneira puramente mecânica. Assim, considerando problemas insolúveis como todos, mesmo em caso de Hilbert estivesse correto, então o próprio Entscheidungsproblem deveria ser insolúvel".Davis 1965:108 De fato: E quanto ao nosso Entscheidungsproblem algoritmo por si só? Pode ele determinar, em um número finito de passos, se ele, ele próprio, é "bem-sucedido" e "verdadeiro" (que é, ele não fica pendurado em uma interminável "ciclo" ou "loop", e ele produz corretamente uma decisão "verdade" ou "falsidade" sobre seu próprio comportamento e resultados)?
Três problemas do 2º e 10º problema de Hilbert Em 1928 no Congresso Internacional de Matemática [em Bolonha, Itália] Hilbert refina a questão com muito cuidado em três partes. O seguinte é o resumo de Stephen Hawking: "1. Para provar que todas as afirmações verdadeiras matemáticas poderiam ser provadas, isto é, a completude da matemática. "2. Para provar que só as verdadeiras afirmações matemáticas poderiam ser provadas, isto é, a consistência da matemática, "3. Para provar a decidibilidade da matemática, isto é, a existência de um processo de decisão para decidir a verdade ou a falsidade de qualquer proposição matemática." Hawking 2005:1121
Simples funções aritméticas irredutíveis à recursão primitiva Gabriel Sudão (1927) e Wilhelm Ackermann (1928) mostram funções recursivas que não são recursões primitivas: "Há recursões que não são redutíveis à recursão primitiva; e, em particular, recursividade pode ser usada para definir uma função que não é recursiva primitiva?
"Esta questão surgiu a partir de uma conjectura de Hilbert em 1926, sobre o problema contínuo, e foi respondida [sim: há recursões que não são recursões primitivas] por Ackermann em 1928."Kleene 1952:271 Nos anos subsequentes Kleenecf. observou que Rózsa Péter (1935) havia simplificado o exemplo de Ackermann (cf. também Hilbert-Bernays, 1934") e Raphael Robinson (1948). Péter expôs um outro exemplo (1935), que empregou o argumento da diagonalização de Cantor. Péter (1950) e Ackermann (1940) também apresentaram o "indução transfinita", e isso levou Kleene a questionar: "... será que podemos caracterizar em qualquer maneira exata a noção de qualquer "recursividade", ou a classe de todas as "funções recursivas."Kleene 1952:273 Kleene conclui que todas as recursões" envolvem: (i) a análise formal, que ele apresenta em seu §54 Cálculos Formais de primitivas de funções recursivas e, (ii) o uso de indução matemática. Ele imediatamente afirma que, de fato, a definição de Gödel-Herbrand, realmente "caracteriza todas as funções recursivas" – veja a citação em 1934, abaixo.
Prova de Gödel Em 1930, os matemáticos se reuniram para uma matemática de reunião e evento de aposentadoria de Hilbert. Como ele teria sorte, "na mesma reunião, um jovem matemático tcheco, Kurt Gödel, anunciou os resultados que tratavam a [opinião de Hilbert de que todas as três respostas foram SIM com] um sério golpe."Hodges 1983:92 Ele anunciou que a resposta para os dois primeiros de Hilbert três perguntas, de 1928, seria NÃO.
Posteriormente, Gödel, em 1931, publicou o seu famoso artigo Sobre Formalmente Indecidíveis, Proposições dos Princípios da Matemática e Sistemas Relacionados I. Em seu prefácio para este artigo científico Martin Davis oferece um cuidado: "O leitor deve ser advertido de que [neste artigo] o que Gödel chama de funções recursivas são agora chamadas de funções recursivas primitivas. (A terminologia revisada foi introduzida por KleeneKleene 1936 in (Davis 1965:237ff))."Davis 1965:4
Expansão de Gödel do "cálculo efetivo" Para citar Kleene (1952), "A caracterização de todas as "funções recursivas" foi realizada na definição geral de função recursiva' por Gödel em 1934, que a construiu sob uma sugestão de Herbrand" (Kleene 1952:274). Gödel proferiu uma série de palestras no Instituto de Estudos Avançados de Princeton, NJ. Em um prefácio escrito por Martin DavisDavis 1965:39–40 Davis observa que "Dr. Gödel afirmou em uma carta que ele foi, na época destas palestras, não estava nem um pouco convencido de que o seu conceito de recursividade compunha todas as possíveis recursões ..."Davis 1965:40 Dawson afirma que essas palestras foram feitas para esclarecer preocupações de que os "teoremas de incompletude foram, de alguma forma, dependente das particularidades da sua formalização":(Dawson 1997:101) "Gödel mencionou o exemplo de Ackermann na seção final de seu artigo de 1934, como uma forma de motivar o conceito de "função geral recursiva" que ele definiu lá, mas, anteriormente, na nota de rodapé 3, ele já tinha conjeturado (como "um princípio heurístico") que todas as funções finitamente computáveis poderiam ser obtidas através de recursões de tipos bem mais gerais.
"A conjectura desde então tem despertado muito comentário. Em particular, quando Martin Davis comprometeu-se a publicar as aulas de 1934 de Gödel [em Davis, 1965:41ff] ele levou-a para ser uma variante da Tese de Church; mas, em uma carta para Davis ...[246: "KG to Martin Davis, 15 February 1965, Quoted in Gödel 1986–, vol. Gödel declarou enfaticamente que "não era verdade", porque no momento de suas palestras ele não estava "convencido de forma alguma" de seu conceito de recursividade composta por "todos os possíveis recursões." Em vez disso, ele disse, "A conjectura apenas se refere à equivalência de 'processos (computação) finitos" e " procedimento recursivo.'" Para esclarecer a questão Gödel adicionou um postscript para as aulas,Gödel 1964 in (Davis 1965:247) also reprinted in (Gödel 1986, vol. , no qual ele disse que o que tinha, finalmente, o convencido, de que funções computáveis intuitivamente, coincidem com aquelas da recursividade geral do trabalho de de Alan Turing .