Funções Computáveis e a Tese de Church-Turing

Funções computáveis são aquelas que um procedimento mecânico pode avaliar, e a tese de Church-Turing identifica esta noção informal com vários modelos matemáticos precisos que definem todos a mesma classe.

Definition

Uma função é computável se alguma máquina de Turing, ou equivalentemente alguma definição recursiva parcial, produzir a sua saída em cada entrada onde está definida; a tese de Church-Turing afirma que esta classe matematicamente precisa coincide com a classe intuitiva de funções efetivamente calculáveis.

Scope

Este tópico abrange as máquinas de Turing, as funções recursivas parciais construídas a partir de funções básicas por composição, recursão primitiva e minimização, o cálculo lambda e as máquinas de registo, as provas de que estes modelos são equivalentes, as máquinas universais e a tese de Church-Turing de que capturam toda a computação efetiva.

Core questions

• O que é uma máquina de Turing e como ela define uma computação?
• Como as funções recursivas parciais são geradas a partir de operações básicas?
• Por que todos os modelos razoáveis de computação definem as mesmas funções?
• Qual é o status e a significância da tese de Church-Turing?

Key theories

Modelo de máquina de Turing

Uma máquina de Turing é um dispositivo de estados finitos que opera numa fita ilimitada, e as funções que ela computa formalizam a noção de algoritmo em termos de manipulação elementar de símbolos.

Equivalência de modelos

Máquinas de Turing, as funções recursivas parciais, o cálculo lambda e as máquinas de registo computam exatamente a mesma classe de funções, demonstrando a robustez da noção de computabilidade.

Máquina universal e enumeração

Existe uma máquina de Turing universal que simula qualquer máquina dado o seu código, de modo que as funções computáveis podem ser efetivamente enumeradas e tratadas como dados, a base dos resultados de autorreferência.

Clinical relevance

A noção de função computável é o fundamento da ciência da computação teórica: a máquina universal prefigura o computador de programa armazenado, a equivalência de modelos justifica uma única definição robusta de algoritmo, e a estrutura fornece o ambiente preciso no qual a indecidibilidade e a complexidade são estudadas.

History

Em 1936, Church definiu a calculabilidade efetiva através do cálculo lambda e Turing através das suas máquinas, e as duas noções foram rapidamente provadas equivalentes às funções recursivas de Kleene. A tese de Church-Turing resultante tornou-se a definição aceita de algoritmo, e a máquina universal de Turing tornou-se um ancestral conceptual do computador de uso geral.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Algumas funções não são computáveis?

Sim. Como os programas podem ser enumerados, mas as funções não, um argumento de contagem mostra que a maioria das funções não é computável, e exemplos específicos, como a função de parada, são comprovadamente incomputáveis. A computabilidade é uma restrição genuína sobre quais funções os algoritmos podem avaliar.

A tese de Church-Turing limita o que os computadores podem fazer?

Ela afirma que nenhum modelo de computação efetiva estende a classe de funções computáveis para além das máquinas de Turing. Hardware mais rápido ou arquiteturas diferentes alteram a eficiência, não o limite do que é computável em princípio, portanto a tese estabelece um limite absoluto para a solucionabilidade algorítmica.