Tese de Church-Turing - Church–Turing thesis

Na teoria da computabilidade , a tese de Church-Turing (também conhecida como tese da computabilidade , a tese de Turing-Church , a conjectura de Church-Turing , a tese de Church , a conjectura de Church e a tese de Turing ) é uma hipótese sobre a natureza das funções computáveis . Afirma que uma função nos números naturais pode ser calculada por um método eficaz se e somente se for computável por uma máquina de Turing . A tese tem o nome do matemático americano Alonzo Church e do matemático britânico Alan Turing . Antes da definição precisa de função computável, os matemáticos costumavam usar o termo informal efetivamente calculável para descrever funções computáveis ​​por métodos de papel e lápis. Na década de 1930, várias tentativas independentes foram feitas para formalizar a noção de computabilidade :

  • Em 1933, Kurt Gödel , com Jacques Herbrand , formalizou a definição da classe de funções recursivas gerais : a menor classe de funções (com muitos argumentos arbitrários) que é fechada sob composição , recursão e minimização , e inclui zero , sucessor e todas as projeções .
  • Em 1936, Alonzo Church criou um método para definir funções chamado de cálculo λ . Dentro do cálculo λ, ele definiu uma codificação dos números naturais chamada de numerais da Igreja . Uma função nos números naturais é chamada de λ-computável se a função correspondente nos números da Igreja puder ser representada por um termo do λ-cálculo.
  • Também em 1936, antes de conhecer o trabalho de Church, Alan Turing criou um modelo teórico para máquinas, agora chamadas de máquinas de Turing, que podiam realizar cálculos a partir de entradas por meio da manipulação de símbolos em uma fita. Dada uma codificação adequada dos números naturais como sequências de símbolos, uma função nos números naturais é chamada de Turing computável se alguma máquina de Turing computar a função correspondente nos números naturais codificados.

Church, Kleene e Turing provaram que essas três classes formalmente definidas de funções computáveis ​​coincidem: uma função é λ-computável se e somente se for Turing computável e se e somente se for recursiva geral . Isso levou matemáticos e cientistas da computação a acreditar que o conceito de computabilidade é caracterizado com precisão por esses três processos equivalentes. Outras tentativas formais de caracterizar a computabilidade posteriormente fortaleceram essa crença (veja abaixo ).

Por outro lado, a tese de Church-Turing afirma que as três classes de funções computáveis ​​formalmente definidas acima coincidem com a noção informal de uma função efetivamente calculável. Embora a tese tenha aceitação quase universal, ela não pode ser formalmente comprovada, pois o conceito de uma calculabilidade efetiva é apenas definido informalmente.

Desde o seu início, surgiram variações na tese original, incluindo declarações sobre o que pode ser fisicamente realizado por um computador em nosso universo ( tese física de Church-Turing ) e o que pode ser computado de forma eficiente ( tese de Church-Turing (teoria da complexidade) ). Essas variações não são devidas a Church ou Turing, mas surgem de trabalhos posteriores em teoria da complexidade e física digital . A tese também tem implicações para a filosofia da mente (veja abaixo ).

Declaração nas palavras de Church e Turing

JB Rosser  ( 1939 ) aborda a noção de "computabilidade efetiva" como segue: "Claramente, a existência de CC e RC (provas de Church e Rosser) pressupõe uma definição precisa de 'efetivo'. 'Método efetivo' é aqui usado de forma bastante especial sentido de um método em que cada etapa é precisamente predeterminada e que certamente produzirá a resposta em um número finito de etapas ". Assim, o adjetivo-advérbio "efetivo" é usado no sentido de "1a: produzindo um efeito decidido, decisivo ou desejado" e "capaz de produzir um resultado".

A seguir, as palavras "efetivamente calculável" significarão "produzido por qualquer meio intuitivamente 'eficaz'" e "efetivamente computável" significará "produzido por uma máquina de Turing ou dispositivo mecânico equivalente". As "definições" de Turing dadas em uma nota de rodapé em seu Ph.D. de 1938. Sistemas de tese de lógica baseados em ordinais , supervisionados por Church, são praticamente os mesmos:

Usaremos a expressão "função computável" para significar uma função calculável por uma máquina, e deixar "efetivamente calculável" referir-se à ideia intuitiva sem identificação particular com qualquer uma dessas definições.

A tese pode ser declarada como: Cada função efetivamente calculável é uma função computável . Church também afirmou que "Nenhum procedimento computacional será considerado um algoritmo a menos que possa ser representado como uma Máquina de Turing". Turing afirmou isso da seguinte maneira:

Foi declarado ... que "uma função é efetivamente calculável se seus valores podem ser encontrados por algum processo puramente mecânico". Podemos interpretar isso literalmente, entendendo que por um processo puramente mecânico, que pode ser executado por uma máquina. O desenvolvimento ... leva a ... uma identificação de computabilidade com calculabilidade efetiva. [ é a nota de rodapé citada acima.]

História

Um dos problemas importantes para os lógicos na década de 1930 foi o Entscheidungsproblem de David Hilbert e Wilhelm Ackermann , que perguntou se havia um procedimento mecânico para separar verdades matemáticas de falsidades matemáticas. Essa busca exigia que a noção de "algoritmo" ou "calculabilidade efetiva" fosse definida, pelo menos bem o suficiente para que a busca começasse. Mas desde o início as tentativas de Alonzo Church começaram com um debate que continua até hoje. Seria a noção de "calculabilidade efetiva" (i) um "axioma ou axiomas" em um sistema axiomático, (ii) meramente uma definição que "identificava" duas ou mais proposições, (iii) uma hipótese empírica a ser verificada por observação de eventos naturais, ou (iv) apenas uma proposta para fins de argumentação (ou seja, uma "tese").

Por volta de 1930–1952

No decorrer do estudo do problema, Church e seu aluno Stephen Kleene introduziram a noção de funções definíveis por λ e foram capazes de provar que várias classes grandes de funções freqüentemente encontradas na teoria dos números eram definíveis por λ. O debate começou quando Church propôs a Gödel que se deveria definir as funções "efetivamente computáveis" como as funções λ-definíveis. Gödel, no entanto, não ficou convencido e chamou a proposta de "totalmente insatisfatória". Em vez disso, em correspondência com Church (c. 1934–35), Gödel propôs axiomatizar a noção de "calculabilidade efetiva"; na verdade, em uma carta de 1935 para Kleene, Church relatou que:

Sua única ideia [de Gödel] na época era que poderia ser possível, em termos de calculabilidade efetiva como uma noção indefinida, declarar um conjunto de axiomas que incorporariam as propriedades geralmente aceitas dessa noção e fazer algo com base nisso .

Mas Gödel não ofereceu nenhuma orientação adicional. Eventualmente, ele sugeriria sua recursão, modificada pela sugestão de Herbrand, que Gödel havia detalhado em suas palestras de 1934 em Princeton NJ (Kleene e Rosser transcreveram as notas). Mas ele não acha que as duas idéias poderiam ser identificadas de forma satisfatória "exceto heuristicamente".

Em seguida, foi necessário identificar e comprovar a equivalência de duas noções de calculabilidade efetiva. Equipado com o cálculo λ e a recursão "geral", Stephen Kleene, com a ajuda de Church e J. Barkley Rosser, produziu provas (1933,1935) para mostrar que os dois cálculos são equivalentes. Church subsequentemente modificou seus métodos para incluir o uso da recursão de Herbrand – Gödel e então provou (1936) que o Entscheidungsproblem é insolúvel: não há algoritmo que pode determinar se uma fórmula bem formada tem uma "forma normal".

Muitos anos depois, em uma carta a Davis (c. 1965), Gödel disse que "ele não estava, na época dessas [1934] palestras, absolutamente convencido de que seu conceito de recursão abrangia todas as recursões possíveis". Em 1963-64, Gödel rejeitaria a recursão de Herbrand-Gödel e o cálculo λ em favor da máquina de Turing como a definição de "algoritmo" ou "procedimento mecânico" ou "sistema formal".

Uma hipótese que leva a uma lei natural? : No final de 1936, o artigo de Alan Turing (também provando que o Entscheidungsproblem é insolúvel) foi entregue oralmente, mas ainda não havia sido publicado. Por outro lado, o artigo de Emil Post de 1936 apareceu e foi certificado independentemente do trabalho de Turing. Post discordou fortemente com a "identificação" de Church de computabilidade efetiva com o cálculo λ e recursão, afirmando:

Na verdade, o trabalho já feito por Church e outros carrega essa identificação consideravelmente além do estágio de hipótese de trabalho. Mas mascarar essa identificação sob uma definição ... nos cega para a necessidade de sua verificação contínua.

Em vez disso, ele considerou a noção de "calculabilidade efetiva" meramente como uma "hipótese de trabalho" que poderia levar pelo raciocínio indutivo a uma " lei natural " em vez de por "uma definição ou um axioma". Essa ideia foi "duramente" criticada por Church.

Assim, Post em seu artigo de 1936 também estava descartando a sugestão de Kurt Gödel a Church em 1934-35 de que a tese poderia ser expressa como um axioma ou conjunto de axiomas.

Turing adiciona outra definição, Rosser iguala as três : em pouco tempo, o artigo de Turing de 1936-37 "On Computable Numbers, with an Application to the Entscheidungsproblem" apareceu. Nele, ele afirmou outra noção de "computabilidade efetiva" com a introdução de suas a-máquinas (agora conhecidas como o modelo computacional abstrato da máquina de Turing ). E em um esboço de prova adicionado como um "apêndice" ao seu artigo de 1936-37, Turing mostrou que as classes de funções definidas pelo cálculo λ e pelas máquinas de Turing coincidiam. Church foi rápido em reconhecer o quão convincente era a análise de Turing. Em sua revisão do artigo de Turing, ele deixou claro que a noção de Turing tornava "a identificação com eficácia no sentido comum (não explicitamente definido) imediatamente evidente".

Em alguns anos (1939), Turing iria propor, como Church e Kleene antes dele, que sua definição formal de agente de computação mecânica era a correta. Assim, em 1939, tanto Church (1934) quanto Turing (1939) haviam proposto individualmente que seus "sistemas formais" deveriam ser definições de "calculabilidade efetiva"; nenhum deles enquadrou suas declarações como teses .

Rosser (1939) identificou formalmente as três noções-como-definições:

Todas as três definições são equivalentes, então não importa qual é usada.

Kleene propõe a Tese I : Isso deixou a expressão aberta de uma "tese" para Kleene. Em 1943, Kleene propôs sua "TESE I":

Este fato heurístico [funções recursivas gerais são efetivamente calculáveis] ... levou Church a apresentar a seguinte tese. A mesma tese está implícita na descrição de Turing das máquinas de computação.

TESE I. Cada função efetivamente calculável (predicado efetivamente decidível) é recursiva geral [itálico de Kleene]

Uma vez que uma definição matemática precisa do termo efetivamente calculável (efetivamente decidível) tem sido necessária, podemos tomar esta tese ... como uma definição dela ...

... a tese tem o caráter de uma hipótese - um ponto enfatizado por Post e por Church. Se considerarmos a tese e seu inverso como definição, então a hipótese é uma hipótese sobre a aplicação da teoria matemática desenvolvida a partir da definição. Para a aceitação da hipótese, existem, como sugerimos, fundamentos bastante convincentes.

A Tese de Church – Turing : Stephen Kleene, em Introdução à Metamatemática , finalmente passa a denominar formalmente "Tese de Church" e "Tese de Turing", usando sua teoria da realizabilidade recursiva. Kleene tendo mudado de apresentar seu trabalho na terminologia da definibilidade lambda de Church-Kleene, para a recursividade de Gödel-Kleene (funções recursivas parciais). Nesta transição, Kleene modificou as funções recursivas gerais de Gödel para permitir provas da insolubilidade de problemas no Intuicionismo de EJ Brouwer. Em seu livro de pós-graduação em lógica, a "tese de Church" é introduzida e os resultados matemáticos básicos são demonstrados como irrealizáveis. Em seguida, Kleene passa a apresentar a "tese de Turing", onde os resultados se mostram incomputáveis, usando sua derivação simplificada de uma máquina de Turing baseada no trabalho de Emil Post. Ambas as teses são comprovadamente equivalentes pelo uso do "Teorema XXX".

Tese I. Toda função efetivamente calculável (predicado efetivamente decidível) é recursiva geral .

Teorema XXX: As seguintes classes de funções parciais são coextensivas, ou seja, têm os mesmos membros: (a) as funções recursivas parciais, (b) as funções computáveis ​​...

Tese de Turing: a tese de Turing de que toda função que seria naturalmente considerada computável é computável sob sua definição, isto é, por uma de suas máquinas, é equivalente à tese de Church pelo Teorema XXX.

Kleene, por fim, usa pela primeira vez o termo "tese de Church-Turing" em uma seção na qual ajuda a dar esclarecimentos aos conceitos do artigo de Alan Turing "O problema da palavra em semigrupos com cancelamento", conforme exigido em um crítica de William Boone.

Desenvolvimentos posteriores

Uma tentativa de compreender melhor a noção de "computabilidade efetiva" levou Robin Gandy (aluno e amigo de Turing) em 1980 a analisar a computação da máquina (em oposição à computação humana realizada por uma máquina de Turing). A curiosidade de Gandy sobre, e a análise de autômatos celulares (incluindo o jogo da vida de Conway ), paralelismo e autômatos cristalinos, levaram-no a propor quatro "princípios (ou restrições) ... que, argumenta-se, qualquer máquina deve satisfazer". Seu quarto mais importante, "o princípio da causalidade" é baseado na "velocidade finita de propagação de efeitos e sinais; a física contemporânea rejeita a possibilidade de ação instantânea à distância". A partir desses princípios e algumas restrições adicionais - (1a) um limite inferior nas dimensões lineares de qualquer uma das partes, (1b) um limite superior na velocidade de propagação (a velocidade da luz), (2) progresso discreto da máquina, e (3) comportamento determinístico - ele produz um teorema de que "O que pode ser calculado por um dispositivo que satisfaça os princípios I-IV é computável."

No final dos anos 1990, Wilfried Sieg analisou as noções de Turing e Gandy de "calculabilidade efetiva" com a intenção de "aguçar a noção informal, formulando suas características gerais axiomaticamente e investigando a estrutura axiomática". Em seu trabalho de 1997 e 2002, Sieg apresenta uma série de restrições ao comportamento de um computador - "um agente de computação humano que procede mecanicamente". Essas restrições se reduzem a:

  • "(B.1) (Limite) Há um limite fixo no número de configurações simbólicas que um computador pode reconhecer imediatamente.
  • "(B.2) (Limite) Há um limite fixo no número de estados internos em que um computador pode estar.
  • "(L.1) (Localidade) Um computador pode alterar apenas os elementos de uma configuração simbólica observada.
  • "(L.2) (Localidade) Um computador pode desviar a atenção de uma configuração simbólica para outra, mas as novas configurações observadas devem estar dentro de uma distância limitada da configuração imediatamente observada anteriormente.
  • "(D) (Determinação) A configuração imediatamente reconhecível (sub) determina exclusivamente a próxima etapa de computação (e id [descrição instantânea])"; afirmou de outra forma: "O estado interno de um computador junto com a configuração observada corrige exclusivamente a próxima etapa de computação e o próximo estado interno."

O assunto permanece em discussão ativa na comunidade acadêmica.

A tese como definição

A tese pode ser vista como nada mais que uma definição matemática comum. Comentários de Gödel sobre o assunto sugerem esta visão, por exemplo, "a definição correta de computabilidade mecânica foi estabelecida sem qualquer dúvida por Turing". O caso para ver a tese como nada mais do que uma definição é feito explicitamente por Robert I. Soare , onde também é argumentado que a definição de computabilidade de Turing não é menos provável de ser correta do que a definição épsilon-delta de uma função contínua .

Sucesso da tese

Outros formalismos (além da recursão, o λ-cálculo e a máquina de Turing ) foram propostos para descrever calculabilidade / computabilidade efetiva. Stephen Kleene (1952) adiciona à lista as funções " reconhecíveis no sistema S 1 " de Kurt Gödel 1936, e Emil Post ( 1943,1946 ) " sistemas canônicos [também chamados normais ] ". Na década de 1950, Hao Wang e Martin Davis simplificaram muito o modelo da máquina de Turing de uma fita (consulte a máquina de Post – Turing ). Marvin Minsky expandiu o modelo para duas ou mais fitas e simplificou muito as fitas em "contadores up-down", que Melzak e Lambek desenvolveram no que agora é conhecido como o modelo da máquina contador . No final dos anos 1960 e no início dos anos 1970, os pesquisadores expandiram o modelo da contra-máquina para a máquina de registro , uma prima próxima da noção moderna de computador . Outros modelos incluem lógica combinatória e algoritmos de Markov . Gurevich acrescenta o modelo de máquina de ponteiro de Kolmogorov e Uspensky (1953, 1958): "... eles só queriam ... se convencer de que não há como estender a noção de função computável."

Todas essas contribuições envolvem provas de que os modelos são computacionalmente equivalentes à máquina de Turing; tais modelos são considerados Turing completos . Como todas essas diferentes tentativas de formalizar o conceito de "calculabilidade / computabilidade efetiva" produziram resultados equivalentes, agora é geralmente assumido que a tese de Church-Turing está correta. Na verdade, Gödel (1936) propôs algo mais forte do que isso; ele observou que havia algo "absoluto" sobre o conceito de "contável em S 1 ":

Também pode ser mostrado que uma função que é computável ['reconhecível'] em um dos sistemas S i , ou mesmo em um sistema do tipo transfinito, já é computável [computável] em S 1 . Assim, o conceito 'computável' ['calculável'] é, em certo sentido definido, 'absoluto', enquanto praticamente todos os outros conceitos metamatemáticos familiares (por exemplo, demonstrável, definível, etc.) dependem essencialmente do sistema para o qual são definidos. .

Uso informal em provas

As provas na teoria da computabilidade freqüentemente invocam a tese de Church-Turing de uma maneira informal para estabelecer a computabilidade das funções, evitando os detalhes (freqüentemente muito longos) que estariam envolvidos em uma prova formal e rigorosa. Para estabelecer que uma função é computável por máquina de Turing, geralmente é considerado suficiente dar uma descrição informal em inglês de como a função pode ser efetivamente computada e, em seguida, concluir "pela tese de Church-Turing" que a função é computável por Turing (equivalentemente , recursiva parcial).

Dirk van Dalen dá o seguinte exemplo com o propósito de ilustrar este uso informal da tese de Church – Turing:

EXEMPLO: Cada conjunto RE infinito contém um conjunto recursivo infinito .

Prova: Seja A infinito RE. Listamos os elementos de A efetivamente, n 0 , n 1 , n 2 , n 3 , ...

Desta lista extraímos uma sublista crescente: coloque m 0 = n 0 , após finitamente muitos passos encontramos um n k tal que n k > m 0 , coloque m 1 = n k . Repetimos este procedimento para encontrar m 2 > m 1 , etc. isso resulta em uma listagem efetiva do subconjunto B = {m 0 , m 1 , m 2 , ...} de A, com a propriedade m i <m i + 1 .

Reivindicar . B é decidível. Pois, para testar k em B, devemos verificar se k = m i para algum i. Como a sequência de m i 's está aumentando, temos que produzir no máximo k + 1 elementos da lista e compará-los com k. Se nenhum deles for igual a k, então k não está em B. Uma vez que este teste é eficaz, B é decidível e, pela tese de Church , recursivo.

Para tornar o exemplo acima completamente rigoroso, seria necessário construir cuidadosamente uma máquina de Turing, ou função λ, ou invocar cuidadosamente axiomas de recursão ou, na melhor das hipóteses, invocar habilmente vários teoremas da teoria da computabilidade. Mas porque o teórico da computabilidade acredita que a computabilidade de Turing captura corretamente o que pode ser computado efetivamente, e porque um procedimento eficaz é descrito em inglês para decidir o conjunto B, o teórico da computabilidade aceita isso como prova de que o conjunto é de fato recursivo.

Variações

O sucesso da tese de Church-Turing levou a variações da tese a serem propostas. Por exemplo, a tese física de Church-Turing afirma: "Todas as funções fisicamente computáveis ​​são Turing-computáveis."

A tese de Church-Turing nada diz sobre a eficiência com que um modelo de computação pode simular outro. Foi provado, por exemplo, que uma máquina de Turing universal (multi-fitas) sofre apenas um fator de desaceleração logarítmica ao simular qualquer máquina de Turing.

Uma variação da tese de Church-Turing aborda se um modelo de computação arbitrário, mas "razoável", pode ser simulado com eficiência. Isso é chamado de tese de viabilidade , também conhecida como a tese ( clássica ) da teoria da complexidade de Church-Turing ou a tese estendida de Church-Turing , que não é devida a Church ou Turing, mas foi realizada gradualmente no desenvolvimento da teoria da complexidade . Ele afirma: "Uma máquina de Turing probabilística pode simular com eficiência qualquer modelo realista de computação." A palavra 'eficientemente' aqui significa até reduções de tempo polinomial . Esta tese foi originalmente chamada de tese da teoria da complexidade computacional de Church-Turing por Ethan Bernstein e Umesh Vazirani (1997). A tese de Church-Turing da teoria da complexidade, então, postula que todos os modelos 'razoáveis' de computação produzem a mesma classe de problemas que podem ser computados em tempo polinomial. Assumindo a conjectura de que o tempo polinomial probabilístico ( BPP ) é igual ao tempo polinomial determinístico ( P ), a palavra 'probabilística' é opcional na tese de Church-Turing da teoria da complexidade. Uma tese semelhante, chamada de tese da invariância , foi introduzida por Cees F. Slot e Peter van Emde Boas. Ele afirma: " Máquinas 'razoáveis' podem simular umas às outras dentro de uma sobrecarga polinomialmente limitada no tempo e uma sobrecarga de fator constante no espaço." A tese apareceu originalmente em um artigo na STOC '84, que foi o primeiro artigo a mostrar que a sobrecarga de tempo polinomial e a sobrecarga de espaço constante podiam ser obtidas simultaneamente para uma simulação de uma máquina de acesso aleatório em uma máquina de Turing.

Se BQP for mostrado ser um superconjunto estrito de BPP , isso invalidaria a tese de Church-Turing da teoria da complexidade. Em outras palavras, haveria algoritmos quânticos eficientes que realizam tarefas que não possuem algoritmos probabilísticos eficientes . No entanto, isso não invalidaria a tese original de Church-Turing, uma vez que um computador quântico sempre pode ser simulado por uma máquina de Turing, mas invalidaria a tese clássica de Church-Turing da teoria da complexidade por razões de eficiência. Consequentemente, a tese de Church-Turing da teoria da complexidade quântica afirma: "Uma máquina de Turing quântica pode simular com eficiência qualquer modelo realista de computação."

Eugene Eberbach e Peter Wegner afirmam que a tese de Church – Turing às vezes é interpretada de forma muito ampla, afirmando "Embora [...] as máquinas de Turing expressem o comportamento dos algoritmos, a afirmação mais ampla de que algoritmos capturam precisamente o que pode ser calculado é inválida". Eles afirmam que as formas de computação não captadas pela tese são relevantes hoje, termos que eles chamam de computação de super-Turing .

Implicações filosóficas

Os filósofos interpretaram a tese de Church-Turing como tendo implicações para a filosofia da mente . B. Jack Copeland afirma que é uma questão empírica aberta se existem processos físicos determinísticos reais que, a longo prazo, escapam à simulação por uma máquina de Turing; além disso, ele afirma que é uma questão empírica aberta se algum desses processos está envolvido no funcionamento do cérebro humano. Existem também algumas questões importantes em aberto que cobrem a relação entre a tese de Church-Turing e a física, e a possibilidade de hipercomputação . Quando aplicada à física, a tese tem vários significados possíveis:

  1. O universo é equivalente a uma máquina de Turing; assim, computar funções não recursivas é fisicamente impossível. Isso foi denominado tese forte de Church-Turing, ou princípio Church-Turing-Deutsch , e é a base da física digital .
  2. O universo não é equivalente a uma máquina de Turing (ou seja, as leis da física não são Turing-computáveis), mas eventos físicos incomputáveis ​​não são "aproveitáveis" para a construção de um hipercomputador . Por exemplo, um universo no qual a física envolve números reais aleatórios , em oposição a reais computáveis , cairia nesta categoria.
  3. O universo é um hipercomputador e é possível construir dispositivos físicos para aproveitar essa propriedade e calcular funções não recursivas. Por exemplo, é uma questão em aberto se todos os eventos da mecânica quântica são Turing-computáveis, embora seja conhecido que modelos rigorosos como as máquinas de Turing quânticas são equivalentes às máquinas de Turing determinísticas. (Eles não são necessariamente equivalentes de forma eficiente; veja acima.) John Lucas e Roger Penrose sugeriram que a mente humana pode ser o resultado de algum tipo de computação "não algorítmica" aprimorada pela mecânica quântica.

Existem muitas outras possibilidades técnicas que estão fora ou entre essas três categorias, mas servem para ilustrar o alcance do conceito.

Aspectos filosóficos da tese, em relação aos computadores físicos e biológicos, também são discutidos no livro de Odifreddi de 1989 sobre a teoria da recursão.

Funções não computáveis

Pode-se definir formalmente funções que não são computáveis. Um exemplo bem conhecido de tal função é a função Busy Beaver . Essa função recebe uma entrada n e retorna o maior número de símbolos que uma máquina de Turing com n estados pode imprimir antes de parar, quando executada sem entrada. Encontrar um limite superior para a função do castor ocupado é equivalente a resolver o problema da parada , um problema conhecido como insolúvel pelas máquinas de Turing. Visto que a função do castor ocupado não pode ser calculada por máquinas de Turing, a tese de Church-Turing afirma que essa função não pode ser efetivamente calculada por nenhum método.

Vários modelos computacionais permitem o cálculo de funções não computáveis ​​(Church-Turing). Eles são conhecidos como hipercomputadores . Mark Burgin argumenta que algoritmos super-recursivos , como máquinas de Turing indutivas, refutam a tese de Church-Turing. Seu argumento se baseia em uma definição de algoritmo mais ampla do que o comum, de modo que funções não computáveis ​​obtidas de algumas máquinas de Turing indutivas são chamadas de computáveis. Esta interpretação da tese de Church-Turing difere da interpretação comumente aceita na teoria da computabilidade, discutida acima. O argumento de que algoritmos super-recursivos são de fato algoritmos no sentido da tese de Church-Turing não encontrou ampla aceitação na comunidade de pesquisa de computabilidade.

Veja também

Notas de rodapé

Referências

links externos