Galeria das máquinas de Turing

Uma representação artística da máquina de Turing.

A galeria das máquinas de Turing é um artigo suplementar ao artigo máquina de Turing. Abaixo serão retratadas interpretações alternativas da máquina de Turing de modo a explicar o funcionamento intuitivamente. A primeira delas mostra a máquina de Turing como um dispositivo mecânico, a segunda mostra a máquina como um homem dentro de uma caixa, puxando-a sobre trilhos e a terceira mostra a máquina como um robô que executa instruções.

Máquina de Turing por Hodges

A máquina de Turing exibida consiste em uma fita de papel especial que pode ser apagada tão bem quanto escrita com um marcador. Talvez a TABELA seja feita de algo semelhante a um leitor de fita de papel (somente leitura), ou talvez leia cartões perfurados. Andrew Hodges, o biógrafo de Alan Turing, escreveu que Turing gostava de máquinas de escrever quando era criança.[1] Uma "'máquina milagrosa' – um processo mecânico que poderia executar o problema de decisão de Hilbert"[nota 1] tinha sido sugerido por G. H. Hardy, um dos professores de Turing. Mesmo assim, "a máquina dele não possuía um modelo óbvio a nada que existisse em 1936, exceto aos termos gerais da nova indústria elétrica, com teleimpressoras, televisores e PABX. Essa foi a única invenção dele."

Davis[2] disse que Turing construiu um multiplicador binário de relés eletromecânicos[nota 2]. Como observado em uma parte da história do algoritmo, a fita de papel impressa ou perfurada e o cartão perfurado estavam num lugar comum na década de 1930.

Boolos e Jeffrey observaram que "estar em um estado ou outro pode ser uma questão de ter uma ou outra engrenagem de um mecanismo superior...".[3][nota 3]

Máquina de Turing por Boolos e Jeffrey

Essa descrição é próxima a "'Formulação 1" de Emil Post para um "processo finito de combinatória": um homem, equipado e seguindo um "conjunto fixo e inalterável de instruções", movendo-se para esquerda ou direita por "uma sequência infinita de espaços ou caixas" e ao mesmo tempo em uma caixa que imprime em um pedaço de papel um simples "traço vertical" ou apaga-o[nota 4]. A formulação de Emil Post foi a primeira dessas a ser publicada; é precedida de Alan Turing em alguns meses.

As descrições – de Post, Boolos e Jeffrey – usam simples 4-tuplas em vez de 5-tuplas para definir as "m configurações" (instruções) do processo.

Máquina de Turing por Stone

Esse é um modelo sugerido por Stone[4]:

Stone usou o robô para desenvolver uma noção própria de algoritmo. Essa por sua vez, leva a uma descrição da máquina de Turing e sua declaração:

Notas

  1. ↑ Página 98 do livro de Hodges[1]
  2. ↑ Página 170 do livro de Hodges[1]
  3. ↑ Página 21 do livro de Boolos e Jeffrey[3]
  4. ↑ Publicado por Post em 1936 e republicado na página 21 do livro de Davis[2]
  5. ↑ Página 3 do livro de Stone[4]
  6. ↑ Página 13 do livro de Stone[4]

Referências

  1. ↑ a b c Hodges, A. (1983). Alan Turing: The Enigma. Inglaterra: Lynx EdicionsBurnett Books Ltd. ISBN 0-52-100758-5 
  2. ↑ a b Davis, M. (2000). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Inglaterra: Dover Ed. ISBN 0-48-643228-9 
  3. ↑ a b c Boolos, George S.; Jeffrey, Richard C.; Burgess, John P. (2002). Computability and Logic. Inglaterra: Cambridge University Press. ISBN 0-09-911641-3 
  4. ↑ a b c Stone, Charles J.; Hoel, Paul G.; Port, Sidney C. (1972). Introduction to Probability Theory. Inglaterra: Brooks Cole. ISBN 0-39-504636-X 

Ver também