Por que a perfeição de Turing está correta?

15

Estou usando um computador digital para escrever esta mensagem. Essa máquina possui uma propriedade que, se você pensar bem, é realmente notável: é uma máquina que, se programada adequadamente, pode executar qualquer cálculo possível .

Obviamente, máquinas de calcular de um tipo ou de outro remontam à antiguidade. As pessoas construíram máquinas que para realizar adição e subtração (por exemplo, um ábaco), multiplicação e divisão (por exemplo, a regra de slides) e mais máquinas específicas do domínio, como calculadoras para as posições dos planetas.

O mais impressionante de um computador é que ele pode executar qualquer cálculo. Qualquer cálculo. E tudo sem ter que religar a máquina. Hoje todo mundo toma essa idéia como garantida, mas se você parar e pensar sobre isso, é incrível que esse dispositivo seja possível.

Eu tenho duas perguntas reais :

  1. Quando a humanidade descobriu que tal máquina era possível? Alguma vez houve alguma dúvida séria sobre se isso pode ser feito? Quando isso foi resolvido? (Em particular, foi estabelecido antes ou depois da primeira implementação real?)

  2. Como os matemáticos provaram que uma máquina completa de Turing pode realmente calcular tudo?

Esse segundo é complicado. Todo formalismo parece ter algumas coisas que não podem ser computadas. Atualmente, "função computável" é definida como "qualquer coisa que uma máquina de Turing possa computar". Mas como sabemos que não existe uma máquina um pouco mais poderosa que possa computar mais coisas? Como sabemos que as máquinas de Turing são a abstração correta?

MathematicsOrchid
fonte
7
Computadores (e seus modelos teóricos, como máquinas de Turing) NÃO PODEM computar tudo. Confira, por exemplo, o problema da parada .
2
Resposta à segunda pergunta: não provamos isso; é uma questão de definição; acontece que o que pensamos intuitivamente de "computável" é computável pelas máquinas de Turing (ou qualquer coisa equivalente). Essa alegação é conhecida como tese de Church-Turing .
Sdcvvc
2
Máquinas como o seu PC que possuem memória finita não são equivalentes a Turing. As máquinas de Turing têm uma fita ilimitada, o que significa que, quanto mais tempo a computação continuar, mais memória eles podem potencialmente usar. Os PCs não podem executar cálculos que demoram um tempo finito, mas exigem mais armazenamento do que eles têm disponível.
Mike Samuel
3
@ MikeSamuel, essa é uma distinção pedante e é semelhante a dizer "há um número finito de partículas no universo; portanto, tudo é um estado finito". É uma afirmação verdadeira, mas não útil. Raramente é útil modelar um computador do mundo real como uma máquina de estados finitos.
Artem Kaznatcheev

Respostas:

17

A humanidade formalizou a computação e desenvolveu dois sistemas para ela em 1936 com os documentos seminais da Igreja Alonzo sobre o cálculoλ e Alan Turing (que hoje, em 23 de junho de 2012, completaria 100 anos se não fosse por circunstâncias desprezíveis que levariam ao seu falecimento precoce). o que ficou conhecido como máquinas de Turing. Ambos os matemáticos estavam resolvendo o problema de Entscheidung .

Embora o artigo de Church tenha sido publicado um pouco antes, Turing não o conhecia quando desenvolveu suas idéias, e a abordagem de Turing provou ser mais útil para o design de máquinas do mundo real. Isso porque ele mostrou como projetar uma Máquina Universal de Turing que poderia ser programada para executar qualquer cálculo. Essa máquina universal, com uma arquitetura concreta baseada no trabalho de John von Neumann, é a idéia básica por trás da máquina na qual você está lendo minha resposta.

Como você observou, computável é definido como "computável em uma máquina de Turing" e todos os outros modelos razoáveis ​​de computação provaram ser equivalentes em sua potência. A crença de que todos os modelos razoáveis ​​de computação são equivalentes em que problemas de decisão eles podem resolver é conhecida como a tese de Church-Turing . Na sua forma original, é quase completamente acreditado pela comunidade instruída. De fato , não está completamente claro o que significaria provar / refutar a tese de Church-Turing ; de várias maneiras, torna-se uma questão empírica.

λ computável) a computação quântica ainda é equivalente ao modelo de Turing.

Artem Kaznatcheev
fonte
11
O artigo de Turing de 1936, comparado ao trabalho de Church na época, era muito mais convincente em seu argumento de que qualquer função numérica que possa ser computada algoritmicamente por um humano pode ser computada por uma máquina de Turing. Os formalismos de Church obviamente não tinham essa propriedade e, até hoje, a redução de outros sistemas computacionais para máquinas de Turing é vital por causa da análise original de Turing sobre o que as máquinas de Turing podem calcular.
precisa
11
@CarlMummert Eu definitivamente concordo, mas o trabalho da Igreja deve ser mencionado para ser completo. Além disso, não é nada insignificante, enquanto a maior parte da teoria A é construída em torno das TMs, a teoria B é muito mais amigável ao lambda-calc. Portanto, é também parcialmente uma diferença de culturas.
Artem Kaznatcheev
Espere - então você está dizendo que não foi provado que não existe um sistema computacional mais poderoso? É apenas uma suposição ?
MathematicalOrchid
@MathematicalOrchid todos os modelos razoáveis de computação (razoavelmente significa: ao mesmo tempo, trabalhando apenas em seções finitas de objetos e executando apenas uma das muitas opções finitas) com as quais estou familiarizado, foram mostrados equivalentes às máquinas de Turing.
Artem Kaznatcheev
2
@MathematicsOrchid Para fornecer uma resposta potencialmente mais direta à sua pergunta de acompanhamento: certo, ninguém provou que não existe um modelo razoável de computação mais poderoso que uma TM. "Assunção" é uma palavra para isso; "hipótese" é outra. Poderíamos acordar amanhã e ver um novo e melhor modelo de computação na CNN. É improvável, mas possível.
Patrick87
-2

Há uma razão para ela ser chamada de Máquina de Turing, e é porque foi inventada por Alan Turing. Ele fez um artigo de 1936 sobre o assunto, estabelecendo esses conceitos. Se você quiser saber mais sobre as Máquinas de Turing, verifique o papel. Duvidava seriamente, antes que ele projetasse e construísse um que quebrasse o Enigma, que esse conceito pudesse realmente funcionar. No entanto, os britânicos estavam bastante desesperados e ele era um gênio, por isso confiaram nele e valeu a pena.

No entanto, quando você pensa um pouco mais, realmente não é nada surpreendente. Antes de Turing, sabia-se que toda a matemática podia ser reduzida a algum conjunto de axiomas. Tudo o que você precisa fazer é dar ao conjunto de instruções a capacidade de executar esses axiomas e pronto.

Cachorro
fonte
Turing não projetou nem construiu enigma (embora ele tenha projetado outro computador que nunca foi construído). O seu segundo parágrafo é bem elaborado: muita excitação na época de Turing (e de fato este foi o ponto de seu próprio artigo) relacionado aos limites da computação.
Marcin
Confiamos nele? Somente até que ele fosse provado publicamente ser homossexual, nós o matamos por isso. Também está provado que há um conjunto de problemas que podem ser declarados em qualquer estrutura axiomática que nunca pode ser provada com esses axiomas.
@ TonyHopkinson: Eu sei. No entanto, o trabalho da TM não é calcular tudo , mas apenas o que pode ser calculado. Sua declaração diz apenas que existem alguns cálculos que não podem ser comprovados como corretos. Isso não significa que eles não possam ser feitos.
@ Marcin: Eu nunca impliquei que Turing projetou ou construiu o Enigma. Eu disse que ele desempenhou um papel crítico na máquina que quebrou o Enigma.
7
Esta resposta está errada . Turing não projetou uma TM para quebrar o enigma, ele ajudou a projetar o Bombe, que era uma máquina especializada para atacar a cifra do Enigma e não universal. Além disso, não se sabia que a matemática poderia ser reduzida a algum conjunto de axiomas. De fato, em 1931, Godel provou o contrário e é sobre as idéias dessa prova que o trabalho de Turing foi baseado. Até o comentário inicial sobre a leitura do artigo original de Turing é enganador. Embora o artigo seja ótimo, se você quiser aprender o básico, um manual moderno como o Sipser é melhor.
Artem Kaznatcheev