miniatura|direita|247x247px|Representação artística de uma máquina de Turing

A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936). Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento (memória, estados e transições), e não a sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.

Turing também se envolveu na construção de máquinas físicas para quebrar os códigos secretos das comunicações alemãs durante a Segunda Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo de computador universal.

Definição Descrição informal

Uma máquina de Turing consiste em: Uma fita que é dividida em células, uma adjacente à outra. Cada célula contém um símbolo de algum alfabeto finito. O alfabeto contém um símbolo especial branco (aqui escrito como ¬) e um ou mais símbolos adicionais. Assume-se que a fita é arbitrariamente extensível para a esquerda e para a direita, isto é, a máquina de Turing possui tanta fita quanto é necessário para a computação. Assume-se também que células que ainda não foram escritas estão preenchidas com o símbolo branco. Um cabeçote, que pode ler e escrever símbolos na fita e mover-se para a esquerda ou para a direita. Um registrador de estados, que armazena o estado da máquina de Turing. O número de estados diferentes é sempre finito e há um estado especial denominado estado inicial com o qual o registrador de estado é inicializado. Uma tabela de ação (ou função de transição) que diz à máquina que símbolo escrever, como mover o cabeçote ( para esquerda e para direita) e qual será seu novo estado, dados o símbolo que ele acabou de ler na fita e o estado em que se encontra. Se não houver entrada alguma na tabela para a combinação atual de símbolo e estado então a máquina para.

Note que cada parte da máquina é finita e sua quantidade de fita potencialmente ilimitada dá uma quantidade ilimitada de espaço de memória.

Definição formal Máquina de Turing com uma fita Mais formalmente, uma máquina de Turing (com uma fita) é perfeitamente definida como uma 7-upla , onde

é um conjunto finito de estados é um alfabeto finito de símbolos é o alfabeto da fita (conjunto finito de símbolos) é o estado inicial é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação) é o conjunto dos estados finais ⇒ é uma função parcial chamada função de transição, onde é o movimento para a esquerda e é o movimento para a direita.

Definições na literatura às vezes diferem um pouco, para tornar argumentos ou provas mais fáceis ou mais claras, mas isto é sempre feito de maneira que a máquina resultante tem o mesmo poder computacional. Por exemplo, mudar o conjunto para , onde P permite ao cabeçote permanecer na mesma célula da fita em vez de mover-se para a esquerda ou direita, não aumenta o poder computacional da máquina, pois é possível simular o movimento P com o movimento sequenciado de e o que mantém o cabeçote no mesmo lugar.

Máquina de Turing com k fitas Uma máquina de Turing com k fitas também pode ser descrita como uma 7-upla , onde

é um conjunto finito de estados é um alfabeto finito de símbolos é o alfabeto da fita (conjunto finito de símbolos) é o número de fitas é o estado inicial é o símbolo branco é o conjunto dos estados finais é uma função parcial chamada função de transição, onde é o movimento para a esquerda e é o movimento para a direita. Observe que uma máquina de Turing com "k" fitas também não é mais poderosa que uma máquina de Turing tradicional de uma única fita, pois podemos organizar linearmente as "k" fitas e em uma única fita com um único cabeçote e registrar a posição dos "cabeçotes virtuais" por algum símbolo ou marcação nessa fita única, assim como funciona os ponteiros em uma memória linear.

Detalhes adicionais requeridos para visualizar ou implementar máquinas de Turing

Nas palavras de Van Emde Boas (1990) p. 6: "O objeto do conjunto teórico [sua descrição formal sete-tupla similar ao acima] fornece apenas informação parcial sobre como a máquina agirá e com o que suas computações se parecerão."

Por exemplo, Serão necessárias muitas decisões sobre com o que os símbolos realmente se parecem e uma forma de contraprovar símbolos de escrita e leitura indefinidamente. As operações shift left e shift right podem deslocar a cabeça da fita sobre a fita, mas quando realmente construir uma máquina de Turing, isso é mais prático para fazer a fita deslizar para frente e para trás sob a cabeça em vez disso. A fita pode ser finita, e automaticamente estendida com espaços em branco, conforme necessário (o qual é o mais próximo da definição matemática), mas isso é mais comum para pensar sobre isso como infinitamente alongado em ambos os lados e sendo preenchida com espaços em branco, exceto sobre o fragmento finito dado explicitamente onde a cabeça da fita está. (Isto não é, claro, implementável na prática.) A fita não pode ser fixada em comprimento, pois não corresponderia à definição dada e limitaria seriamente o alcance das computações que a máquina pode realizar àquelas do autômato linearmente limitado.

Definições alternativas Para tornar as provas e argumentos mais fáceis ou mais claras, encontramos na literatura definições levemente diferentes, mas isso sempre é feito de tal maneira que a máquina resultante tenha o mesmo poder computacional. Por exemplo, modificando o conjunto para , onde N ("Nada" ou "Sem operação") permitiria a máquina ficar sobre a mesma célula da fita em vez de mover para a esquerda ou para direita, não aumenta o poder computacional das máquinas.

A convenção mais comum representa cada "instrução de Turing" na "tabela de Turing" por uma de nove 5-uplas, pela convenção de Turing/Davis (Turing (1936) em Undecidable, p. 126-127 e Davis (2000) p. 152):

(definição 1): (qi, Sj, Sk/E/N, L/R/N, qm) ( estado atual qi , símbolo escaneado Sj , símbolo de impressão Sk/apagar E/nada N , move_um_quadrado_da_fita esquerda L/ direita R/ nada N , novo estado qm )

Outros autores (Minsky (1967) p. 119, Hopcroft e Ullman (1979) p. 158, Stone (1972) p. 9) adotam uma convenção diferente, com um novo estado qm listado imediatamente depois do símbolo escaneado Sj: (definição 2): (qi, Sj, qm, Sk/E/N, L/R/N) ( estado atual qi , símbolo escaneado Sj , novo estado qm , símbolo de impressão Sk/apagar E/nada N , move_um_quadrado_da_fita esquerda L/direita R/nada N )

Para o restante desse artigo a "definição 1" (a convenção de Turing/Davis) será utilizada.

+ Exemplo: tabela de estado para o problema do castor ocupado de 3 estados e 2 símbolos reduzido para 5-tuplas Estado atual Símbolo escaneado Símbolo de impressão Mover fita Estado final(i.e. próximo) 5-tuplas A 0 1 R B (A, 0, 1, R, B) A 1 1 L C (A, 1, 1, L, C) B 0 1 L A (B, 0, 1, L, A) B 1 1 R B (B, 1, 1, R, B) C 0 1 L B (C, 0, 1, L, B) C 1 1 N H (C, 1, 1, N, H)

Na tabela seguinte, o modelo original de Turing permitiu apenas as primeiras três linhas, que ele chamou N1, N2, N3 (cf Turing em Undecidable, p. 126). Ele permitiu a rasura do "quadrado escaneado" nomeando o 0th símbolo S0 = "apagar" ou "branco", etc. Entretanto, ele não permitiu a não impressão, então toda linha de instrução inclui "símbolo de impressão Sk" ou "apagar" (cf nota de rodapé 12 em Post (1947), Undecidable p. 300). As abreviações são de Turing(Undecidable p. 119). Posteriormente ao paper original de Turing em 1936–1937, os modelos de máquina têm permitido todos os nove tipos possíveis de 5-tuplas:

Configuração atual m (Estado de Turing) Símbolo da fita Operação de impressão Movimento na fita Configuração final m (Estado de Turing) 5-tupla Comentários da 5-tupla 4-tupla N1 qi Sj Impressão(Sk) Esquerda L qm (qi, Sj, Sk, L, qm) "branco" = S0, 1=S1, etc. N2 qi Sj Impressão(Sk) Direita R qm (qi, Sj, Sk, R, qm) "branco" = S0, 1=S1, etc. N3 qi Sj Impressão(Sk) Nada N qm (qi, Sj, Sk, N, qm) "branco" = S0, 1=S1, etc. (qi, Sj, Sk, qm) 4 qi Sj Nada N Esquerda L qm (qi, Sj, N, L, qm) (qi, Sj, L, qm) 5 qi Sj Nada N Direita R qm (qi, Sj, N, R, qm) (qi, Sj, R, qm) 6 qi Sj Nada N Nada N qm (qi, Sj, N, N, qm) "Salto" direto (qi, Sj, N, qm) 7 qi Sj Apagar Esquerda L qm (qi, Sj, E, L, qm) 8 qi Sj Apagar Direita R qm (qi, Sj, E, R, qm) 9 qi Sj Apagar Nada N qm (qi, Sj, E, N, qm) (qi, Sj, E, qm)

Qualquer tabela de Turing (lista de instruções) pode ser construída a partir das nove 5-tuplas acima. Por razões técnicas, as três não-impressão ou instruções "N" (4, 5, 6) pode geralmente ser dispensadas. Para exemplos, veja exemplos de máquina de Turing.

Menos frequentemente, o uso de 4-tuplas são encontrados: estes representam uma outra atomização das instruções de Turing (cf Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); também veja mais em Máquina de Post–Turing.

O "estado" A palavra "estado" utilizada em contexto de máquinas de Turing pode ser uma fonte de confusão, como isso pode significar duas coisas. A maioria dos comentaristas depois de Turing utilizaram "estado" para denotar o nome/designador da instrução atual para ser realizada — i.e. , os conteúdos do registro de estado. Mas Turing (1936) fez uma distinção forte entre um registro do que ele chamou de m-configuração da máquina, (seu estado interno) e o "estado de progresso" da máquina (ou pessoa) através da computação - o estado atual do sistema total. O que Turing chamou "a fórmula do estado" inclui ambos a instrução atual e todos os símbolos sobre a fita:

Anteriormente em seu paper, Turing estendeu isto ainda mais: ele dá um exemplo onde ele posicionou um símbolo da configuração atual m —o rótulo da instrução— abaixo do quadrado escaneado, juntamente com todos os símbolos sobre a fita (Undecidable, p. 121); Isto ele chama "a configuração completa" (Undecidable, p. 118). Para imprimir a "configuração completa" sobre uma linha, ele posiciona o estado-rótulo/m-configuração para a esquerda do símbolo escaneado.

Uma variante disto é vista em Kleene (1952), onde Kleene mostra como escrever o número de Gödel de uma "situação" da máquina: ele posiciona o símbolo da "m-configuração" q4 sobre o quadrado escaneado em grosseiramente o centro dos 6 quadrados não-brancos sobre a fita ( veja a imagem da fita de Turing nesse artigo) e coloca isso para a direita do quadrado escaneado. Mas Kleene refere-se ao próprio "q4" como "o estado da máquina" (Kleene, p. 374-375). Hopcroft e Ullman chamam este composto a "descrição instantânea" e segue a convenção de Turing de colocar o "estado atual" (rótulo-instrução, m-configuração) para a esquerda do símbolo escaneado (p. 149).

Exemplo: estado total do problema do castor ocupado de 3 estados e 2 símbolos após 3 "movimentos" (pegando de exemplo "run" na figura abaixo): 1A1 Isso significa: após três movimentos, a fita tem ... 000110000 ... sobre esta, a cabeça está escaneando o 1 mais a direita, e o estado é A. Brancos (nesse caso, representado por "0"s) pode ser parte do estado total como mostrado aqui: B01; a fita possui um único 1 sobre esta, mas a cabeça está escaneando o 0 ("branco") para sua esquerda e o estado é B.

"Estado" no contexto de máquinas de Turing devem ser esclarecidas quanto ao que está sendo descrito: (i) a instrução atual, ou (ii) a lista de símbolos sobre a fita juntamente com a instrução atual, ou (iii) a lista de símbolos sobre a fita juntamente com a instrução atual posicionada pela esquerda do símbolo escaneado ou pela direita do símbolo escaneado.

O biógrafo de Turing, Andrew Hodges (1983: 107), tem notado e discutido esta confusão.

Exemplo