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. Uma "'máquina milagrosa' – um processo mecânico que poderia executar o problema de decisão de Hilbert" 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 disse que Turing construiu um multiplicador binário de relés eletromecânicos. 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...".

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. 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:

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:

Ver também Teoria da computação

Categoria:Máquina de Turing Categoria:Alan Turing Categoria:Métodos formais Categoria:Teoria da computação