Galeria das máquinas 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.

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

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

“ Nós não estamos interessados com a mecânica ou eletrônica do assunto. Talvez a forma mais simples de imaginá-la seja bastante simples: dentro da caixa há um homem, que executa toda leitura e escrita, além de apagar e movimentar. (A caixa não tem fundo: o pobre homem apenas anda ao longo dos trilhos, puxando a caixa com ele.) O homem tem uma lista m de instruções escritas num pedaço de papel. Ele está num estado qi quando está executando uma instrução i... ”

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:

“ Deixe-nos adotar o ponto de vista que o computador é um robô que iremos executar qualquer tarefa que possa ser descrita numa sequência de instruções. ”

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:

“ A evidência aparenta indicar que todo algoritmo pra qualquer dispositivo computacional tem um algoritmo da máquina de Turing equivalente... se a Tese de Church for verdade, é notável que máquinas de Turing, com suas operações extremamente primitivas, são capazes de executar qualquer computação que algum outro dispositivo possa executar, independente de quão complexo ele seja. ”

Ver também

• Teoria da computação