Razões históricas para a adoção da máquina de Turing como modelo primário de computação.

44

Entendo que o modelo de Turing tenha se tornado o "padrão" ao descrever a computação. Estou interessado em saber por que esse é o caso - ou seja, por que o modelo da MT se tornou mais amplamente utilizado do que outros modelos teoricamente equivalentes (ao meu conhecimento), por exemplo, a μ-Recursion de Kleene ou o Lambda Calculus (eu entendo que o primeiro não apareceu até mais tarde e o último não foi originalmente projetado especificamente como um modelo de computação, mas mostra que existem alternativas desde o início).

Tudo o que consigo pensar é que o modelo da TM representa mais de perto os computadores que realmente temos do que suas alternativas. Essa é a única razão?

Evan
fonte
1
embora não estejam diretamente no mesmo tópico, as perguntas cstheory.stackexchange.com/questions/625/… e cstheory.stackexchange.com/questions/1117/… exploram o relacionamento entre TMs e o -calculus e têm algumas informações históricas elementos. λ
Suresh Venkat
Sim, eu vi aqueles. Entendo muito bem as histórias literais das várias teorias, mas estou mais interessado nos desenvolvimentos ao longo do tempo que levaram às atuais "preferências" no campo, se você preferir.
Evan
2
Na verdade, existem modelos que são (sem dúvida) mais próximos de computadores reais, veja esta pergunta . Geralmente, o melhor modelo depende das necessidades e elas são diferentes de uma área para outra.
Kaveh

Respostas:

46

Isso parece ser verdade no contexto de (algumas áreas da) ciência da computação, mas não geralmente.

Um dos motivos tem a ver com a tese da Igreja. A principal razão é que alguns especialistas como Godel não pensaram que os argumentos de que modelos anteriores / outros modelos de computação capturam exatamente o conceito intuitivo de computação eram convincentes. Existem vários argumentos, Church tinha alguns, mas eles não convenceram Godel. Por outro lado, a análise de Turing foi convincente para Godel, por isso foi aceita como o modelo para uma computação eficaz. As equivalências entre diferentes modelos são comprovadas mais tarde (penso por Kleene).

λμ

μλ. Veja também esses documentos de Viggo Stoltenberg-Hansen e John V. Tucker I , II .)

Alguns recursos para leitura adicional:

Robert I. Soare tem vários artigos sobre a história desses desenvolvimentos, pessoalmente gosto do artigo do Handbook of Computability Theory. você pode encontrar mais verificando as referências nesse documento.

Outro bom recurso é o artigo de computabilidade de Neil Immerman no SEP, veja também o artigo de Tese de Church-Turing de B. Jack Copeland.

As obras coletadas de Godel contêm muitas informações sobre seus pontos de vista. Especialmente introduções aos seus artigos são extremamente bem escritas.

A " Metamatemática " de Kleene é um livro muito bom.

Por fim, se você ainda não estiver satisfeito, verifique os arquivos da lista de correio do FOM e, se não conseguir encontrar uma resposta no arquivo, envie um email para a lista de endereços.

Kaveh
fonte
Entre em contato se tiver algo errado.
Kaveh
1
Uau, esta é uma ótima informação. Obrigado pelos recursos, vou dar uma olhada neles (eu estava planejando ler Metamatemática - vou aumentar a fila).
Evan
De nada, espero que eu não tenha entendido errado. :)
Kaveh
Houve uma recente conversa de Robert Soare no INI. Pelo que entendi, o principal motivo para mudar para o modelo de Turing e a computabilidade de funções recursivas e teoria da recursão para ele é o seguinte: é difícil entender e trabalhar na teoria da recursão a ponto de ninguém entender o que estava acontecendo, exceto alguns, a mudança na computabilidade tornou muito mais fácil entender e reviver a área.
Kaveh
19

Eu gostaria de enfraquecer a afirmação de que as TMs são o modelo primário de computação, ou pelo menos apontam para outra dimensão da questão. Claramente, as TMs são dominantes nas partes mais complexas e orientadas por algoritmos da ciência da computação, mas na teoria e prática da linguagem de programação, elas não são particularmente dominantes. Existem várias razões para isso, mas talvez o mais importante seja que as TMs ou programas executados nas TMs (diferentemente de lambda-calculi ou process-calculi) não sejam construídos de maneira algébrica. Isso dificulta o desenvolvimento de teorias de tipos, que têm sido a base da teoria da linguagem de programação.

Martin Berger
fonte
2
Além disso, os programas de TM, também conhecidos como tabelas de transição, não são realmente legíveis por humanos.
Raphael
13

Uma das coisas boas das máquinas de Turing é que elas trabalham com strings em vez de números naturais ou termos lambda, porque a entrada e a saída de muitos problemas podem ser naturalmente formuladas como strings. Não sei se isso conta como uma razão "histórica" ​​ou não.

Tsuyoshi Ito
fonte
13

Além do fato de as máquinas de Turing serem um modelo convincente de computação com caneta e papel (a “noção intuitiva de computação”), acho que elas possuem uma série de recursos que são frequentemente úteis, principalmente ao provar teoremas sobre elas:

  • são fáceis de descrever formalmente e possuem semântica operacional simples;
  • é fácil fornecer uma definição concreta de sua complexidade de tempo e espaço;
  • modelos mais realistas (e complexos) de computadores eletrônicos, como máquinas de acesso aleatório, podem ser simulados por TMs com uma sobrecarga polinomial e vice-versa.
Antonio E. Porreca
fonte
Às vezes, a facilidade da descrição parece dificultar a utilidade das MTs, pois as descrições podem se transformar rapidamente em explicações simples em inglês se você não for cuidadoso (pelo menos, se eu não for cuidadoso ... É certo que sou novato).
Evan
Seus motivos não excluem máquinas de registro, por exemplo.
Raphael
Bem, isso depende da noção precisa de "máquina de registro" que você considera. Por exemplo, aqueles que possuem apenas operações de incremento, decremento e salto não podem simular TMs em tempo polinomial.
Antonio E. Porreca
1
λλ
Estou do lado do PL, mas o cálculo lambda puro não é um modelo óbvio de computação aritmética (pense na função predecessora). No cálculo lambda, você tem menos na definição, mas é preciso mais esforço para entender as implicações da definição.
Blaisorblade
0

Foi o primeiro a ter impacto e, portanto, foi estabelecido, especialmente na teoria da complexidade. Essa é uma razão fraca, mas as pessoas trabalham dessa maneira. Primeiro, trabalhamos com problemas abertos antigos, em vez de declarar novos.

Rafael
fonte
8
"Trabalhamos primeiro em problemas abertos antigos, em vez de declarar novos." <- Acho que o oposto é verdadeiro, especialmente em um campo em que as perguntas antigas são extremamente difíceis. Há relativamente poucas pessoas trabalhando na complexidade do circuito, por exemplo (embora talvez exista mais agora!). As pessoas precisam trabalhar nos problemas que podem resolver para publicar; isso gera um fluxo constante de problemas solucionáveis ​​recém-declarados.
Aaron Sterling
Eu estava um pouco apressado em minhas palavras lá. Sinto que, muitas vezes, as pessoas preferem seguir um modelo estabelecido do que construir um novo (e provar suas propriedades básicas) se não houver uma razão esmagadora para isso. Esse sentimento pode estar errado, obviamente. Em particular, é claro que existem pessoas que caçam modelos em primeiro lugar.
Raphael
Bem, o cálculo lambda veio primeiro. Mas Turing mostrou que as máquinas de Turing modelam com precisão o básico dos seres humanos que fazem cálculos; isso foi feito apenas para o cálculo lambda ao provar equivalência. Além disso, essa equivalência é verdadeira apenas para computação de primeira ordem: cstheory.stackexchange.com/q/1117/989 - dados de ordem superior realmente não existem no papel. Ele nem existe nas memórias do computador, mas pode ser perfeitamente simulado.
Blaisorblade 24/03