Tese de Church–Turing

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, Tese de Church, Conjectura de Church e Tese de Turing >) é uma tese sobre a natureza das funções computáveis. Ele 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 leva 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 que são 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 arbitrariamente muitos argumentos) que é fechada sob composição, recursão e minimização, e inclui zero, sucessor e todas as projeções.
• Em 1936, a Igreja de Alonzo criou um método para definir funções chamadas de λ-calculus. Dentro de λ-calculus, ele definiu uma codificação dos números naturais chamados numerais da Igreja. Uma função sobre os números naturais é chamada λ-computável se a função correspondente nos numerais da Igreja pode ser representada por um termo do λ-calculus.
• Também em 1936, antes de aprender o trabalho da Igreja, Alan Turing criou um modelo teórico para máquinas, agora chamadas de máquinas de Turing, que poderia realizar cálculos de entradas manipulando símbolos em uma fita. Dado uma codificação adequada dos números naturais como sequências de símbolos, uma função nos números naturais é chamada Turing computável se alguma máquina de Turing computa a função correspondente em 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 subsequentemente fortaleceram essa crença (veja abaixo).

Por outro lado, a tese de Church-Turing afirma que as três classes formalmente definidas de funções computáveis 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 comprovada formalmente, pois o conceito de calculabilidade efetiva é definido apenas informalmente.

Desde a sua criação, surgiram variações da 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 eficientemente (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 (ver abaixo).

Declaração nas palavras de Church e Turing

J. B. 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 eficaz' é aqui usado no sentido bastante especial de um método em que cada passo é precisamente predeterminado e que certamente produzirá a resposta em um número finito de passos'. Assim, o advérbio-adjetivo "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áveis" significará "produzido por qualquer usuário intuitivamente 'efetivo' significa qualquer coisa" e "efetivamente computável" significará "produzido por uma máquina de Turing ou dispositivo mecânico equivalente". As "definições" dado em uma nota de rodapé em seu Ph.D. de 1938. tese Sistemas de Lógica Baseados em Ordinais, supervisionados por Church, são praticamente os mesmos:

^† Vamos usar 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 enunciada como: Toda função efetivamente calculável é uma função computável. Church também afirmou que "Nenhum procedimento computacional será considerado como um algoritmo a menos que possa ser representado como uma Máquina de Turing". Turing assim se expressou:

Foi afirmado... que "uma função é efetivamente calculável se seus valores podem ser encontrados por algum processo puramente mecânico". Podemos levar isto literalmente, entendendo que por um processo puramente mecânico que poderia ser realizado por uma máquina. O desenvolvimento... leva a... uma identificação de computabilidade^† com cálculo eficaz. Não.^† é 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 questionava se havia um procedimento mecânico para separar as verdades matemáticas das falsidades matemáticas. Essa busca exigia que a noção de "algoritmo" ou "calculabilidade efetiva" ser fixado, pelo menos bem o suficiente para a missão começar. Mas desde o início as tentativas de Alonzo Church começaram com um debate que continua até hoje. Foi a noção de &# 34;calculabilidade efetiva" ser (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 pela observação de eventos naturais, ou (iv) apenas uma proposta para fins de argumentação (isto é, uma & #34;tese").

Cerca de 1930–1952

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

Sua ideia [Gödel] apenas na época era que poderia ser possível, em termos de cálculo eficaz como uma noção indefinida, afirmar um conjunto de axiomas que incorporariam as propriedades geralmente aceitas desta noção, e fazer algo nessa base.

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 achava que as duas ideias pudessem ser identificadas satisfatoriamente "exceto heuristicamente".

Em seguida, foi necessário identificar e provar a equivalência de duas noções de calculabilidade efetiva. Equipado com o λ-calculus e "geral" recursão, 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 posteriormente 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 possa determinar se uma fórmula bem formada tem uma forma beta normal.

Muitos anos depois, em uma carta a Davis (c. 1965), Gödel disse que "ele estava, na época dessas [1934] palestras, nada convencido de que seu conceito de recursão incluía todas as recursões possíveis& #34;. Em 1963-1964, 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 apresentado oralmente, mas ainda não havia sido impresso. Por outro lado, o artigo de Emil Post de 1936 apareceu e foi certificado independente do trabalho de Turing. A postagem discordou veementemente da "identificação" de computabilidade efetiva com o λ-cálculo e recursão, afirmando:

Na verdade, o trabalho já feito pela Igreja e outros carrega esta identificação consideravelmente além da fase de hipótese de trabalho. Mas para mascarar esta identificação sob uma definição... nos cega à necessidade de sua verificação contínua.

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

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

Turing acrescenta outra definição, Rosser iguala todas as três: Em pouco tempo, o artigo de Turing de 1936–1937 "On Computable Numbers, with an Application to the Entscheidungsproblem&# 34; apareceu. Nela, 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" em seu artigo de 1936–1937, 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) evidente imediatamente".

Em poucos anos (1939) Turing proporia, como Church e Kleene antes dele, que sua definição formal de agente computacional mecânico era a correta. Assim, em 1939, tanto Church (1934) quanto Turing (1939) propuseram individualmente que seus "sistemas formais" devem ser definições de "calculabilidade efetiva"; nenhum dos dois enquadrou suas declarações como teses.

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

Os três. definições são equivalentes, por isso não importa qual é usado.

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

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

Tese I. Cada função efetivamente calculável (predicato efetivamente decidível) é recursiva geral [Kleene's italics]

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

...a tese tem o caráter de uma hipótese - um ponto enfatizado por Post e pela Igreja. Se considerarmos a tese e seu converso 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, há, como sugerimos, motivos bastante convincentes.

The Church–Turing Thesis: Stephen Kleene, em Introduction To Metamathematics, finalmente nomeia formalmente "Church's Thesis" e "Tese de Turing", usando sua teoria de realizabilidade recursiva. Kleene mudou de apresentar seu trabalho na terminologia de 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 E. J. Brouwer. Em seu livro de pós-graduação sobre lógica, "Tese de Church" é introduzido e 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 equivalentes pelo uso do "Teorema XXX".

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

Theorem 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 cada função que seria naturalmente considerada computável é computável sob sua definição, ou seja, por uma de suas máquinas, é equivalente à tese da Igreja por Theorem XXX.

Kleene, finalmente, usa pela primeira vez o termo "Tese de Church-Turing" em uma seção na qual ele ajuda a esclarecer os conceitos do artigo de Alan Turing "The Word Problem in Semi-Groups with Cancellation", conforme exigido em uma crítica de William Boone.

Desenvolvimentos posteriores

Uma tentativa de entender a noção de "computabilidade efetiva" better levou Robin Gandy (aluno e amigo de Turing) em 1980 a analisar a computação de máquina (em oposição à computação humana representada por uma máquina de Turing). A curiosidade de Gandy e a análise de autômatos celulares (incluindo o jogo da vida de Conway), paralelismo e autômatos cristalinos o levaram 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" baseia-se 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 que "O que pode ser calculado por um dispositivo que satisfaça os princípios I–IV é computável."

No final da década de 1990, Wilfried Sieg analisou as noções de Turing e Gandy sobre "calculabilidade efetiva" com a intenção de "afiar a noção informal, formular suas características gerais axiomaticamente e investigar a estrutura axiomática". Em seu trabalho de 1997 e 2002, Sieg apresenta uma série de restrições sobre o comportamento de um computador—"um agente computacional humano que procede mecanicamente". Essas restrições se reduzem a:

• (B.1) Há um limite fixo no número de configurações simbólicas que um computador pode reconhecer imediatamente.
• "(B.2) (Boundedness) Há um limite fixo no número de estados internos que um computador pode estar dentro.
• "(L.1) (Localidade) Um computor pode mudar apenas elementos de uma configuração simbólica observada.
• "(L.2) (Localidade) Um computador pode mudar 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.
• "(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]])"; declarou outra maneira: "O estado interno de um computor juntamente com as correções de configuração observadas de forma única a próxima etapa de computação e o próximo estado interno."

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

A tese como definição

A tese pode ser vista como nada além de uma definição matemática comum. Comentários de Gödel sobre o assunto sugerem essa visão, por ex. "a definição correta de computabilidade mecânica foi estabelecida sem sombra de dúvida por Turing". O argumento 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 Turing de computabilidade não é menos provável de ser correta do que a definição epsilon-delta de um 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 a calculabilidade/computabilidade efetiva. Kleene (1952) acrescenta à lista as funções "reconháveis no sistema S₁" de Kurt Gödel 1936, e Emil Post's (1943, 1946) "canônico [também chamado normal] sistemas& #34;. Na década de 1950, Hao Wang e Martin Davis simplificaram bastante o modelo da máquina de Turing de uma fita (ver máquina 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 modelo de máquina contadora. No final dos anos 1960 e início dos anos 1970, os pesquisadores expandiram o modelo da máquina contadora para a máquina registradora, 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 ditos Turing completos. Porque 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 "reconhecido em S₁":

Também pode ser mostrado que uma função que é computável ['reckonable'] em um dos sistemas S_Eu..., ou mesmo em um sistema de tipo transfinito, já é computável [reckonable] em S₁. Assim, o conceito "computável" ['reckonable'] está em um certo sentido definido 'absoluto', enquanto praticamente todos os outros conceitos metamatemáticos familiares (por exemplo, prováveis, definíveis, etc.) dependem essencialmente do sistema ao qual eles são definidos...

Uso informal em provas

As provas na teoria da computabilidade geralmente invocam a tese de Church-Turing de maneira informal para estabelecer a computabilidade das funções, evitando os detalhes (muitas vezes muito longos) que estariam envolvidos em uma prova formal rigorosa. Para estabelecer que uma função é computável pela máquina de Turing, geralmente é considerado suficiente fornecer 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 é Turing computável (equivalentemente, recursiva parcial).

Dirk van Dalen dá o seguinte exemplo para ilustrar esse uso informal da tese de Church-Turing:

Exemplo: Cada conjunto de RE infinito contém um conjunto recursivo infinito.

Prova: Seja um RE infinito. Listamos os elementos de A efetivamente, n₀,₁,₂,₃,

A partir desta lista extraímos uma sublista crescente: colocar m₀= n₀, depois de finitamente muitos passos encontramos um n_k tal que n_k >₀, put m₁= n_k. Repetimos este procedimento para encontrar m₂ >₁, etc. isso produz uma lista eficaz do subconjunto B={m₀, m₁, m₂,...} de A, com a propriedade m_Eu... <_I+.

Reivindicação. B é decidível. Para, para testar k em B temos que verificar se k = m_Eu... para alguns eu. Desde a sequência de m_Eu...'s está aumentando, temos que produzir na maioria dos elementos k+1 da lista e compará-los com k. Se nenhum deles é igual a k, então k não em B. Uma vez que este teste é eficaz, B é decidível e, pela tese da Igrejarecursiva.

Para tornar o exemplo acima completamente rigoroso, seria preciso 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 efetivo é explicado 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 propostas de variações da tese. 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 não diz nada 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 (multifita) sofre apenas um fator de desaceleração logarítmica na simulação de qualquer máquina de Turing.

Uma variação da tese de Church-Turing aborda se uma decisão arbitrária, mas "razoável" modelo de computação pode ser simulado com eficiência. Isso é chamado de tese de viabilidade, também conhecida como a (clássica) tese de Turing da teoria da complexidade ou a Igreja estendida– Tese de 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 eficientemente qualquer modelo realista de computação." A palavra 'eficientemente' aqui significa até reduções de tempo polinomial. Esta tese foi originalmente chamada de tese de Church-Turing da teoria da complexidade computacional por Ethan Bernstein e Umesh Vazirani (1997). A tese da teoria da complexidade de Church-Turing, então, postula que todo conhecimento 'razoável' modelos 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ístico' é opcional na tese de Church-Turing da teoria da complexidade. Uma tese semelhante, denominada tese da invariância, foi apresentada por Cees F. Slot e Peter van Emde Boas. Ele declara: "'Razoável' as máquinas podem simular umas às outras dentro de um overhead limitado polinomialmente no tempo e um overhead de fator constante no espaço." A tese apareceu originalmente em um artigo no STOC'84, que foi o primeiro artigo a mostrar que o overhead de tempo polinomial e o overhead de espaço constante podem ser simultaneamente alcançados para uma simulação de uma máquina de acesso aleatório em uma máquina de Turing.

Se o BQP for mostrado como um superconjunto estrito do BPP, isso invalidaria a tese de Church-Turing da teoria da complexidade. Em outras palavras, haveria algoritmos quânticos eficientes que executam 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 clássica tese de Church-Turing da teoria da complexidade por razões de eficiência. Conseqüentemente, a tese de Church–Turing da teoria da complexidade quântica declara: "Uma máquina de Turing quântica pode simular eficientemente 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 os algoritmos capturam com precisão o que pode ser calculado é inválida". Eles afirmam que formas de computação não capturadas pela tese são relevantes hoje, termos que eles chamam de computação 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 tais processos estão envolvidos 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, a computação funções não-recursivas é fisicamente impossível. Isso tem sido chamado de forte tese Igreja-Turing, ou Igreja-Turing-Deutsch princípio, e é uma 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 computáveis por Turing), mas eventos físicos incomputáveis não são "harnessable" para a construção de um hipercomputador. Por exemplo, um universo em que a física envolve números reais aleatórios, ao contrário dos reais computáveis, cairia nessa categoria.
3. O universo é um hipercomputador, e é possível construir dispositivos físicos para aproveitar esta propriedade e calcular funções não-recursivas. Por exemplo, é uma pergunta aberta se todos os eventos mecânicos quânticos são computáveis por Turing, embora se saiba que modelos rigorosos como máquinas de Turing quântica são equivalentes a máquinas de Turing determinísticas. (Eles não são necessariamente eficientemente equivalentes; veja acima.) John Lucas e Roger Penrose sugeriram que a mente humana poderia ser o resultado de algum tipo de computação quântica-mecanicamente aprimorada, "não-algoritmática".

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

Aspectos filosóficos da tese, relativos a computadores físicos e biológicos, também são discutidos no livro de Odifreddi de 1989 sobre 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. Esta 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 na função de castor ocupado é equivalente a resolver o problema da parada, um problema conhecido por ser insolúvel pelas máquinas de Turing. Como 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). Estes 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 dentro da comunidade de pesquisa de computabilidade.