A tese de Church-Turing refere-se ao conceito de um método eficiente, sistemático ou mecânico em lógica, matemática e ciência da computação. Ela é formulada como uma descrição do conceito intuitivo de computabilidade e, em relação às funções recursivas gerais, é mais frequentemente chamada de tese de Church. Também se refere à teoria das funções computáveis por computador. A tese surgiu na década de 1930, quando os próprios computadores ainda não existiam. Mais tarde, foi nomeado após o matemático americano Alonso Church e seu colega britânico Alan Turing.
Eficiência do método para alcançar o resultado
O primeiro dispositivo que se assemelhava a um computador moderno foi o Bombie, uma máquina criada pelo matemático inglês Alan Turing. Foi usado para decifrar mensagens alemãs durante a Segunda Guerra Mundial. Mas para sua tese e formalização do conceito de algoritmo, ele usou máquinas abstratas, mais tarde chamadas de máquinas de Turing. Tese apresentainteresse para matemáticos e programadores, pois essa ideia inspirou os criadores dos primeiros computadores.
Na teoria da computabilidade, a tese de Church-Turing também é conhecida como a conjectura sobre a natureza das funções computáveis. Ele afirma que para qualquer função algoritmicamente computável em números naturais, existe uma máquina de Turing capaz de computá-la. Ou, em outras palavras, existe um algoritmo adequado para isso. Um exemplo bem conhecido da eficácia deste método é o teste da tabela-verdade para testar a tautologia.
Uma maneira de alcançar qualquer resultado desejado é chamada de "eficaz", "sistemática" ou "mecânica" se:
- O método é especificado em termos de um número finito de instruções exatas, cada instrução é expressa usando um número finito de caracteres.
- Será executado sem erros, produzirá o resultado desejado em um certo número de etapas.
- O método pode ser realizado por um humano sem ajuda com qualquer equipamento que não seja papel e lápis
- Não requer compreensão, intuição ou engenhosidade por parte da pessoa que executa a ação
No início da matemática, o termo informal "efetivamente computável" era usado para se referir a funções que podem ser calculadas com lápis e papel. Mas a própria noção de computabilidade algorítmica era mais intuitiva do que qualquer coisa concreta. Agora foi caracterizado por uma função com um argumento natural, para o qual existe um algoritmo de cálculo. Uma das conquistas de Alan Turing foirepresentação de um predicado formalmente exato, com a ajuda do qual seria possível substituir o informal, se for utilizada a condição de eficiência do método. Church fez a mesma descoberta.
Conceitos básicos de funções recursivas
A mudança de predicados de Turing, à primeira vista, parecia diferente da proposta por seu colega. Mas, como resultado, eles se tornaram equivalentes, no sentido de que cada um deles seleciona o mesmo conjunto de funções matemáticas. A tese de Church-Turing é a afirmação de que este conjunto contém todas as funções cujos valores podem ser obtidos por um método que satisfaça as condições de eficiência. Havia outra diferença entre as duas descobertas. Foi que Church considerou apenas exemplos de inteiros positivos, enquanto Turing descreveu seu trabalho como cobrindo funções computáveis com uma variável integral ou real.
Funções recursivas comuns
A formulação original de Church afirma que o cálculo pode ser feito usando o λ-cálculo. Isso é equivalente a usar funções recursivas genéricas. A tese de Church-Turing abrange mais tipos de computação do que se pensava originalmente. Por exemplo, relacionado a autômatos celulares, combinadores, máquinas de registro e sistemas de substituição. Em 1933, os matemáticos Kurt Gödel e Jacques Herbrand criaram uma definição formal de uma classe chamada funções recursivas gerais. Ele usa funções onde mais de um argumento é possível.
Criando um métodoλ-cálculo
Em 1936, Alonso Church criou um método de determinação chamado λ-cálculo. Ele foi associado com números naturais. Dentro do cálculo λ, o cientista determinou sua codificação. Como resultado, eles são chamados de números da Igreja. Uma função baseada em números naturais foi chamada de λ-computável. Havia outra definição. A função da tese de Church é chamada de λ-computável sob duas condições. O primeiro soava assim: se fosse calculado sobre elementos da Igreja, e a segunda condição era a possibilidade de ser representado por um membro do λ-cálculo.
Também em 1936, antes de estudar o trabalho de seu colega, Turing criou um modelo teórico para as máquinas abstratas que agora levam seu nome. Eles poderiam realizar cálculos manipulando os caracteres na fita. Isso também se aplica a outras atividades matemáticas encontradas na ciência da computação teórica, como a computação probabilística quântica. A função da tese de Church só mais tarde foi comprovada usando uma máquina de Turing. Inicialmente, eles contavam com λ-cálculo.
Computabilidade da função
Quando os números naturais são codificados apropriadamente como sequências de caracteres, uma função em números naturais é considerada Turing-computável se a máquina abstrata encontrar o algoritmo necessário e imprimir essa função na fita. Tal dispositivo, que não existia na década de 1930, seria no futuro considerado um computador. A máquina de Turing abstrata e a tese de Church anunciaram uma era de desenvolvimentodispositivos de computação. Ficou provado que as classes de funções formalmente definidas por ambos os cientistas coincidem. Portanto, como resultado, ambas as declarações foram combinadas em uma. As funções computacionais e a tese de Church também tiveram forte influência no conceito de computabilidade. Eles também se tornaram uma ferramenta importante para a lógica matemática e a teoria da prova.
Justificação e problemas do método
Existem pontos de vista conflitantes sobre a tese. Numerosas evidências foram coletadas para a "hipótese de trabalho" proposta por Church e Turing em 1936. Mas todos os métodos ou operações conhecidas para descobrir novas funções efetivamente computáveis a partir de determinadas funções estavam conectadas com métodos de construção de máquinas, que não existiam na época. Para provar a tese de Church-Turing, parte-se do fato de que todo modelo realista de computação é equivalente.
Devido à variedade de análises diferentes, isso geralmente é considerado uma evidência particularmente forte. Todas as tentativas de definir com mais precisão a noção intuitiva de uma função efetivamente computável se mostraram equivalentes. Todas as análises que foram propostas provaram destacar a mesma classe de funções, ou seja, aquelas que são computáveis por máquinas de Turing. Mas alguns modelos computacionais se mostraram mais eficientes em termos de uso de tempo e memória para diferentes tarefas. Mais tarde notou-se que os conceitos básicos de funções recursivas e a tese de Church são bastante hipotéticos.
Tese M
É importante distinguir entre a tese de Turing e a afirmação de que qualquer coisa que possa ser calculada por um dispositivo de computação pode ser calculada por sua máquina. A segunda opção tem sua própria definição. Gandhi chama a segunda frase de "Tese M". É assim: “Tudo o que pode ser computado por um dispositivo pode ser computado por uma máquina de Turing”. No sentido estrito da tese, é uma proposição empírica cujo valor de verdade é desconhecido. A Tese de Turing e a "Tese M" às vezes são confundidas. A segunda versão está amplamente incorreta. Várias máquinas condicionais foram descritas que podem calcular funções que não são computáveis por Turing. É importante notar que a primeira tese não implica a segunda, mas é consistente com sua falsidade.
Implicação reversa da tese
Na teoria da computabilidade, a tese de Church é usada como uma descrição da noção de computabilidade por uma classe de funções recursivas gerais. O americano Stephen Kleene deu uma formulação mais geral. Ele chamou de parcialmente recursivas todas as funções parciais computáveis por algoritmos.
A implicação reversa é comumente referida como a tese inversa de Church. Está no fato de que toda função recursiva de inteiros positivos é avaliada eficientemente. Em sentido estrito, uma tese simplesmente denota tal possibilidade. E em um sentido mais amplo, abstrai-se da questão de saber se essa máquina condicional pode existir nele.
Computadores quânticos
Os conceitos de funções computáveis e a tese de Church se tornaram uma importante descoberta para a matemática, teoria de máquinas e muitas outras ciências. Mas a tecnologia mudou muito e continua a melhorar. Supõe-se que os computadores quânticos podem executar muitas tarefas comuns com menos tempo do que os modernos. Mas as questões permanecem, como o problema de parada. Um computador quântico não pode respondê-la. E, de acordo com a tese de Church-Turing, nenhum outro dispositivo de computação também.
