A Tese de Church-Turing

A tese de Church-Turing afirma que toda função computável por qualquer procedimento efetivo é computável por uma máquina de Turing, equiparando a ideia informal de um algoritmo a um modelo matemático preciso.

Definition

A tese de Church-Turing é a afirmação de que as funções intuitivamente computáveis são exatamente as funções computáveis por uma máquina de Turing, equivalentemente pelo cálculo lambda ou pelas funções recursivas gerais; é uma tese em vez de um teorema porque a noção intuitiva não é formalmente definida.

Scope

Este tópico aborda a declaração da tese, a evidência convergente de modelos propostos independentemente, a distinção entre a tese original sobre computabilidade efetiva e variantes mais fortes físicas ou teórico-computacionais, e o papel da tese como uma ponte entre a intuição e a prova formal na teoria da computabilidade.

Core questions

• O que significa identificar a noção informal de algoritmo com um modelo formal?
• Por que a convergência de modelos independentes é considerada uma forte evidência para a tese?
• A tese é um teorema matemático, uma definição ou uma afirmação empírica?
• Como as versões físicas e teórico-computacionais vão além da declaração original?

Key theories

Convergência de modelos de computação

Máquinas de Turing, o cálculo lambda de Church e as funções recursivas de Gödel e Herbrand demonstraram definir exatamente a mesma classe de funções, e este acordo independente é a principal evidência oferecida para a tese.

Status como tese, não teorema

Como a noção intuitiva de procedimento efetivo não é formalizada, a afirmação não pode ser provada; ela é aceita como uma identificação fundamental que permite que argumentos algorítmicos informais substituam construções formais de máquinas de Turing.

Clinical relevance

A tese licencia a prática diária de descrever algoritmos em pseudocódigo de alto nível, em vez de como máquinas de Turing, uma vez que qualquer noção razoável de procedimento efetivo é assumida como sendo Turing-equivalente; ela também enquadra debates sobre se dispositivos físicos ou quânticos poderiam algum dia computar além do Turing-computável.

History

Em 1936, Church propôs identificar a calculabilidade efetiva com a definibilidade lambda, e Turing, independentemente, defendeu seu modelo de máquina, após o que Turing, Kleene e outros provaram a equivalência destes e das funções recursivas. Gödel, inicialmente cético, passou a considerar a análise de Turing como conclusiva, e a afirmação combinada ficou conhecida como a tese de Church-Turing.

Debates

A computação física pode superar o limite de Turing?

A tese original diz respeito a procedimentos efetivos, mas versões físicas mais fortes afirmam que nenhum dispositivo fisicamente realizável pode computar funções não-Turing-computáveis. Propostas para hipercomputação e as implicações da mecânica quântica mantêm esta afirmação estendida contestada, mesmo que a tese clássica permaneça essencialmente inquestionável.

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

Por que é chamada de tese e não de teorema?

Ela conecta um modelo formal à ideia informal de um procedimento efetivo, e essa ideia informal não tem uma definição matemática para provar coisas. A forte evidência é que cada tentativa independente de formalizar a computação produziu a mesma classe de funções, mas este suporte é conceitual em vez de uma prova.

Computadores quânticos refutam a tese de Church-Turing?

Não. Computadores quânticos podem resolver alguns problemas mais rapidamente, mas eles computam exatamente a mesma classe de funções que as máquinas de Turing, então a tese original sobre o que é computável permanece. Eles se referem, em vez disso, à versão mais forte da teoria da complexidade, preocupada com a eficiência e não com a computabilidade.