Mostrar código-fonte de Máquina de Turing

{{Mais notas|data=março de 2022}}
[[Imagem:Turing Machine.png|miniatura|direita|247x247px|Representação artística de uma máquina de Turing]]
{{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''.
<!--
A '''máquina de Turing''' é uma [[máquina abstrata]] introduzida em [[1936]] por [[Alan Turing]] para dar uma definição matematicamente precisa de [[algoritmo]] ou 'procedimento mecânico'.
Ela é ainda amplamente usada em [[ciência da computação]] teórica, especialmente em [[teoria da complexidade computacional|teoria da complexidade]] e na [[teoria da computação]].

A tese que afirma que as máquinas de Turing de fato capturam a noção informal de procedimento mecânico ou efetivo na lógica e na matemática é conhecida como [[Tese de Church-Turing]].

O conceito de máquina de Turing é baseado na ideia de uma pessoa executando um procedimento bem definido, mudando o conteúdo de um número infinito de folhas de papel ordenadas que podem conter um símbolo dentro de um conjunto finito de símbolos. A pessoa precisa lembrar de um estado dentro de uma quantidade finita de estados e o procedimento é formulado em etapas muito básicas na forma de "Se seu estado é 42 e o símbolo que você vê é um '0' então substitua-o por um '1', lembre-se do estado 17, e vá para a folha seguinte."

As máquinas de Turing não devem ser confundidas com o [[teste de Turing]], a tentativa de Turing de capturar a noção de [[inteligência artificial]].

Uma máquina de Turing que é capaz de simular qualquer outra máquina de Turing é chamada de '''máquina de Turing universal''' ou simplesmente de '''máquina universal''' como Turing a descreveu em 1947:
<blockquote style="font-style:italic;">
Pode ser mostrado que uma única máquina especial deste tipo pode ser feita pra executar o trabalho de todas. Ela poderia, de fato, ser feita para funcionar como um modelo de qualquer outra máquina. A máquina especial pode ser chamada de máquina universal.</blockquote>
-->
== Definição ==
=== Descrição informal ===
<!--
A Turing machine is a [[pushdown automaton]] made more powerful by relaxing the last-in-first-out requirement of its stack.  (Interestingly, a seemingly minor relaxation enables the Turing machine to perform such a wide variety of computations that it can serve as a model for the computational capabilities of all modern computer software.)
-->
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 (<math>\leftarrow</math> para esquerda e <math>\rightarrow</math> 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 <math display="inline">M=(Q,\Sigma, \Gamma, s, b, F, \delta)</math>, onde

* <math>Q</math> é um [[conjunto finito]] de estados
* <math>\Sigma</math> é um alfabeto finito de símbolos
* <math>\Gamma</math> é o alfabeto da fita (conjunto finito de símbolos)
* <math>s \in Q</math> é o estado inicial
* <math>b \in \Gamma</math> é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação)
* <math>F \subseteq Q</math> é o conjunto dos estados finais
* <math>\delta: Q \times \Gamma</math> ⇒ <math>Q \times \Gamma \times \{\leftarrow,\rightarrow\}</math> é uma [[função parcial]] chamada função de transição, onde <math>\leftarrow</math> é o movimento para a esquerda e <math>\rightarrow</math> é 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 <math>\{\leftarrow,\rightarrow\}</math> para <math>\{\leftarrow,\rightarrow,P\}</math>, 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 <math>\leftarrow</math> e <math>\rightarrow</math> o que  mantém o cabeçote no mesmo lugar.<ref name=":0">{{citar livro|titulo=Introdução a Teoria da Computação|ultimo=SIPSER|primeiro=MICHAEL|editora=PWS Puclishing Company|ano=1997|local=EUA|paginas=|acessodata=}}</ref>

==== Máquina de Turing com ''k'' fitas ====
Uma máquina de Turing com ''k'' fitas também pode ser descrita como uma 7-upla <math>M=(Q,\Sigma, \Gamma^1, \Gamma^2, ..., \Gamma^k, s, b, F, \delta)</math>, onde

* <math>Q</math> é um conjunto finito de estados
* <math>\Sigma</math> é um alfabeto finito de símbolos
* <math>\Gamma^i, i = 1,...,k</math> é o alfabeto da fita <math>i</math> (conjunto finito de símbolos)
* <math>k</math> é o número de fitas
* <math>s \in Q</math> é o estado inicial
* <math>b \in \Gamma</math> é o símbolo branco
* <math>F \subseteq Q</math> é o conjunto dos estados finais
*<math>\delta: Q \times \Gamma \longrightarrow Q \times \Gamma \times \{\leftarrow,\rightarrow\}</math>  é uma função parcial chamada função de transição, onde <math>\leftarrow</math> é o movimento para a esquerda e <math>\rightarrow</math> é 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.<ref name=":0" />

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

Nas palavras de Van Emde Boas (1990) p.&nbsp;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 <math>\{L,R\}</math> para <math>\{L,R,N\}</math>, 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.&nbsp;126-127 e Davis (2000) p.&nbsp;152):

: (definição 1): '''(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)'''
:: '''(''' estado atual '''q<sub>i</sub>''' ''',''' símbolo escaneado '''S<sub>j</sub>''' ''',''' símbolo de impressão '''S<sub>k</sub>'''/apagar '''E'''/nada '''N''' ''',''' move_um_quadrado_da_fita esquerda '''L'''/ direita '''R'''/ nada '''N''' ''',''' novo estado '''q<sub>m</sub>''' ''')'''

Outros autores (Minsky (1967) p.&nbsp;119, Hopcroft e Ullman (1979) p.&nbsp;158, Stone (1972) p.&nbsp;9) adotam uma convenção diferente, com um novo estado '''q<sub>m</sub>''' listado imediatamente depois do símbolo escaneado S<sub>j</sub>:
: (definição 2): '''(q<sub>i</sub>, S<sub>j</sub>, q<sub>m</sub>, S<sub>k</sub>/E/N, L/R/N)'''
:: '''(''' estado atual '''q<sub>i</sub>''' ''',''' símbolo escaneado '''S<sub>j</sub>''' ''',''' novo estado '''q<sub>m</sub>''' ''',''' símbolo de impressão '''S<sub>k</sub>'''/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.

{| class="wikitable" style="text-align: center"
|+ 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.&nbsp;126). Ele permitiu a rasura do "quadrado escaneado" nomeando o 0th símbolo S<sub>0</sub> = "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 S<sub>k</sub>" ou "apagar" (cf nota de rodapé 12 em Post (1947), ''Undecidable'' p.&nbsp;300). As abreviações são de Turing(''Undecidable'' p.&nbsp;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:

{| class="wikitable" style="text-align: center"
|-
!
! style="width:15%" | Configuração atual m (Estado de Turing)
! Símbolo da fita
! Operação de impressão
! Movimento na fita
! style="width:15%" | Configuração final m (Estado de Turing)
! 5-tupla
! Comentários da 5-tupla
! 4-tupla
|-
| N1
| q<sub>i</sub>
| S<sub>j</sub>
| Impressão(S<sub>k</sub>)
| Esquerda L
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, L, q<sub>m</sub>)
| "branco" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
|
|-
| N2
| q<sub>i</sub>
| S<sub>j</sub>
| Impressão(S<sub>k</sub>)
| Direita R
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, R, q<sub>m</sub>)
| "branco" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
|
|-
| N3
| q<sub>i</sub>
| S<sub>j</sub>
| Impressão(S<sub>k</sub>)
| Nada N
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, N, q<sub>m</sub>)
| "branco" = S<sub>0</sub>, 1=S<sub>1</sub>, etc.
| (q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>, q<sub>m</sub>)
|-
| 4
| q<sub>i</sub>
| S<sub>j</sub>
| Nada N
| Esquerda L
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, N, L, q<sub>m</sub>)
|
| (q<sub>i</sub>, S<sub>j</sub>, L, q<sub>m</sub>)
|-
| 5
| q<sub>i</sub>
| S<sub>j</sub>
| Nada N
| Direita R
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, N, R, q<sub>m</sub>)
|
| (q<sub>i</sub>, S<sub>j</sub>, R, q<sub>m</sub>)
|-
| 6
| q<sub>i</sub>
| S<sub>j</sub>
| Nada N
| Nada N
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, N, N, q<sub>m</sub>)
| "Salto" direto
| (q<sub>i</sub>, S<sub>j</sub>, N, q<sub>m</sub>)
|-
| 7
| q<sub>i</sub>
| S<sub>j</sub>
| Apagar
| Esquerda L
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, E, L, q<sub>m</sub>)
|
|
|-
| 8
| q<sub>i</sub>
| S<sub>j</sub>
| Apagar
| Direita R
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, E, R, q<sub>m</sub>)
|
|
|-
| 9
| q<sub>i</sub>
| S<sub>j</sub>
| Apagar
| Nada N
| q<sub>m</sub>
| (q<sub>i</sub>, S<sub>j</sub>, E, N, q<sub>m</sub>)
|
| (q<sub>i</sub>, S<sub>j</sub>, E, q<sub>m</sub>)
|}

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áquinas de Turing|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|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:

{{quote|Assim o estado de progresso da computação em qualquer estágio é completamente determinado pela nota de instruções e os símbolos sobre a fita. Isso é, o '''estado do sistema''' pode ser descrito por uma única expressão (sequência de símbolos) consistindo dos símbolos sobre a fita seguida por Δ (os quais supomos não aparecer em outro lugar) e então pelo nota de instruções. Essa expressão é chamada de 'fórmula de estado'.|''Undecidable'', p.139–140, ênfase adicionada}}

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.&nbsp;121); Isto ele chama "a ''configuração completa''" (''Undecidable'', p.&nbsp;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 [[Stephen_Cole_Kleene|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" q<sub>4</sub> 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 "q<sub>4</sub>" como "o estado da máquina" (Kleene, p.&nbsp;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.&nbsp;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):
:: 1'''A'''1
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: '''B'''01; 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 ==
A máquina de Turing a seguir tem um alfabeto {¬, 1}, onde ¬ representa o símbolo branco. Ela espera uma série de 1's na fita, com o cabeçote inicialmente no 1 mais à esquerda, e duplica os 1's com um ¬ no meio. Por exemplo, "111" torna-se "111¬111".
O conjunto dos estados é {s1, s2, s3, s4, s5} e o estado inicial é s1.
A tabela de ação é dada a seguir.

  Est.  Símb.  Símb.       Est.
  Act.  Lido   Escr.  Mv.  Novo
  ----  -----  -----  ---  ----
  s1    1      ¬      →    s2
  s2    1      1      →    s2
  s2    ¬      ¬      →    s3
  s3    ¬      1      ←    s4
  s3    1      1      →    s3
  s4    1      1      ←    s4
  s4    ¬      ¬      ←    s5
  s5    1      1      ←    s5
  s5    ¬      1      →    s1

A primeira linha desta tabela pode ser lida como: "Se a máquina estiver no estado s1 e o símbolo lido pelo cabeçote for 1, então escreva o símbolo ¬, mova uma posição para a direita e mude o estado para s2".

Uma computação nesta máquina de Turing pode ser, por exemplo: (a posição do cabeçote é indicada mostrando-se a célula em negrito)

  Passo  Estado  Fita
  -----  ------  ----------
  1      s1      <b>1</b>1
  2      s2      ¬<b>1</b>
  3      s2      ¬1<b>¬</b>
  4      s3      ¬1¬<b>¬</b>
  5      s4      ¬1<b>¬</b>1
  6      s5      ¬<b>1</b>¬1
  7      s5      <b>¬</b>1¬1
  8      s1      1<b>1</b>¬1
  9      s2      1¬<b>¬</b>1
  10     s3      1¬¬<b>1</b>
  11     s3      1¬¬1<b>¬</b>
  12     s4      1¬¬<b>1</b>1
  13     s4      1¬<b>¬</b>11
  14     s5      1<b>¬</b>¬11
  15     s1      11<b>¬</b>11

O comportamento desta máquina pode ser descrito como um laço (loop): Ele inicia em s1, substitui o primeiro 1 com um ¬, então usa o s2 para mover para a direita, passando pelos 1's e pelo primeiro ¬ encontrado. S3 então passa pela próxima sequência de 1's (inicialmente há nenhuma) e substitui o primeiro ¬ que encontra por um 1. S4 move de volta para a esquerda, passando pelos 1's até encontrar um ¬ e vai para o estado s5. S5 então move para a esquerda, passando pelos 1's até achar o ¬ que foi originalmente escrito por s1. Ele substitui o ¬ por 1, move uma posição para a direita e entra no estado s1 novamente para outra execução do laço. Isso continua até s1 achar um ¬ (este é o ¬ que fica entre as duas cadeias de 1's), situação na qual a máquina pára.

== Máquinas de Turing determinísticas e não-determinísticas ==
Se a tabela de ação tem no máximo uma entrada para cada combinação de símbolo e estado então a máquina é uma '''máquina de Turing determinística''' (MTD). Se a tabela de ação contém múltiplas entradas para uma combinação de símbolo e estado então a máquina é uma '''[[máquina de Turing não-determinística]]''' (MTND ou MTN).

== Máquinas de Turing universais ==
{{AP|Máquina de Turing universal}}

Toda máquina de Turing computa uma certa [[função computável]] [[função parcial|parcial]] a partir da cadeia dada formada pelos símbolos do alfabeto. Neste sentido ela comporta-se como um computador com um programa fixo. No entanto, como Alan Turing descreveu, podemos codificar a tabela de ação de qualquer máquina de Turing em uma cadeia de símbolos. Portanto podemos tentar construir uma máquina de Turing que espera em sua fita uma cadeia descrevendo a tabela de ação seguida por uma cadeia descrevendo a fita de entrada, e então computa a fita que a máquina de Turing codificada teria computado.

== Comparação com máquinas reais ==
Frequentemente diz-se que as máquinas de Turing, ao contrário de autômatos mais simples, são tão poderosas quanto máquinas reais, e são capazes de executar qualquer operação que um programa real executa. O que está faltando neste enunciado é que praticamente qualquer programa particular executando em uma ''máquina particular'' e dada uma entrada finita é, na verdade, nada além de um [[autômato finito determinístico]], já que a máquina em que executa pode estar apenas em uma quantidade finita de ''configurações''. Máquinas de Turing poderiam de fato ser equivalentes a uma máquina que tenha uma quantidade ilimitada de espaço de armazenamento. Podemos questionar então por que as máquinas de Turing são modelos úteis de computadores reais. Há várias maneiras de responder a isto:
# A diferença está apenas na habilidade de uma máquina de Turing de manipular uma quantidade ilimitada de dados. No entanto, dada uma quantidade finita de tempo, uma máquina de Turing (como uma máquina real) pode apenas manipular uma quantidade finita de dados.
# Como uma máquina de Turing, uma máquina real pode ter seu espaço de armazenamento aumentado conforme a necessidade, através da aquisição de mais discos ou outro meio de armazenamento. Se o suprimento destes for curto, a máquina de Turing pode se tornar menos útil como modelo. Mas o fato é que nem as máquinas de Turing nem as máquinas reais precisam de quantidades astronômicas de espaço de armazenamento para fazer a maior parte das computações que as pessoas normalmente querem que sejam feitas. Frequentemente o tempo de processamento requerido é o maior problema.
# Máquinas reais são muito mais complexas que uma máquina de Turing. Por exemplo, uma máquina de Turing descrevendo um algoritmo pode ter algumas centenas de estados, enquanto o autômato finito determinístico equivalente em uma dada máquina real tem quadrilhões.
# Máquinas de Turing descrevem algoritmos independentemente de quanta memória eles utilizam. Há um limite máximo na quantidade de memória que qualquer máquina que conhecemos tem, mas este limite pode crescer arbitrariamente no tempo. As máquinas de Turing nos permitem fazer enunciados sobre algoritmos que (teoricamente) valerão eternamente, independentemente dos avanços na arquitetura de computadores ''convencionais''.
# Máquinas de Turing simplificam o enunciado de algoritmos. Algoritmos executando em máquinas abstratas equivalentes a Turing são normalmente mais gerais que suas contrapartes executando em máquinas reais, porque elas têm tipos com precisão arbitrária disponíveis e nunca precisam tratar condições inesperadas (incluindo, mas não somente, acabar a memória).

Uma maneira em que máquinas de Turing são pobres modelos para programas é que muitos programas reais, tais como [[Sistema operativo|sistemas operacionais]] e processadores de texto, são escritos para receber entradas irrestritas através da execução, e portanto não param. Máquinas de Turing não modelam bem tal "computação contínua" (mas ainda podem modelar porções dela, tais como procedimentos individuais).

Outra limitação de máquinas de Turing é que elas não modelam a organização estrita de um problema específico. Por exemplo, computadores modernos são na verdade instâncias de uma forma mais específica de máquina de computação, conhecido como máquina de acesso aleatório. A principal diferença entre esta máquina e a máquina de Turing é que esta utiliza uma fita infinita, enquanto a máquina de acesso aleatório utiliza uma sequência indexada numericamente (tipicamente um campo inteiro). O resultado desta distinção é que há otimizações computacionais que podem ser executadas baseadas nos índices em memória, o que não é possível numa máquina de Turing geral. Assim, quando máquinas de Turing são utilizadas como base para tempo de execuções restritos, um "falso limite inferior" pode ser provado em determinados tempos de execução de algoritmos (graças à premissa falsa de simplificação da máquina de Turing). Um exemplo disto é uma "ordenação por contagem", o que aparentemente viola o limite inferior <math>\Theta(n\log{n})</math> em algoritmos de ordenação.

== Máquinas de Turing físicas ==
Não é difícil simular uma máquina de Turing num computador moderno (exceptuando pela quantidade de memória limitada existente nos computadores actuais). O [[Google Search|''site'' de busca Google]], em comemoração aos 100 anos de Alan Turing, publicou um ''[[doodle]]'' dia [[23 de junho]] de 2012, em forma de uma máquina de Turing.<ref>{{Citar web |url=http://www.google.com/doodles/finder/2012/All%20doodles |título=Doodles |acessodata=23 de junho de 2012 |autor=[[Google]] |publicado=www.google.com}}</ref>

É possível construir uma máquina de Turing com base puramente mecânica. O matemático [[Karl Scherer]] construiu essa máquina em [[1986]], usando conjuntos de construção de metal, plástico e alguma madeira. A máquina, com 1,5 m de altura, usa puxões de fios para ler, movimentar e escrever informação, a qual é, por sua vez, representada por [[Rolamento (mecânico)|rolamentos]]. A máquina encontra-se atualmente em exibição na entrada do Departamento de Ciência de Computadores da [[Universidade de Heidelberg]], na [[Alemanha]].

O conceito de máquina de Turing foi usado como ferramenta educativa na obra de [[ficção científica]] ''[[The Diamond Age]]'' (1995), escrita por [[Neal Stephenson]]. A personagem principal, Nell, possui um livro interactivo que a ensina a pensar criativa e logicamente apresentando-lhe puzzles numa história, os quais, sendo máquinas de Turing, se tornam cada vez mais complexos à medida que a narrativa se desenvolve. Estes puzzles começam por ser simples aparelhos mecânicos e evoluem para processos econômicos abstractos, atingindo um ponto em que se assiste à interação entre completos reinos ficcionais.

== História ==
=== Contexto histórico: máquinas computacionais ===
[[Robin Gandy]] (1919-1995), um estudante de [[Alan Turing]] (1912-1954) e seu amigo ao longo da vida, [[Lepidoptera|traça]] a linhagem da noção de "máquina de calcular" até a Babbage (em cerca de 1834) e, na verdade, propõe a "Tese de Babbage":

{{quote|''Que o desenvolvimento e análise de operações são agora capazes de serem executados por máquinas.''|(Itálico em Babbage como citados por Gandy, p. 54)}}

A análise de Gandy da Máquina Analítica de Babbage descreve as seguintes cinco operações (cf. p. 52-53):
# As funções aritméticas +, -, ×, onde - indica [[subtração]] "apropriada" x - y = 0 se y ≥ x
# Qualquer sequência de operações é uma operação
# Iteração de uma operação (repetir n vezes uma operação P)
# Iteração condicional (repetir n vezes uma operação P condicional sobre o "sucesso" do teste T)
# Transferência condicional (i.e. condicional "goto").
Gandy afirma que "as funções que podem ser calculadas por (1), (2), e (4) são precisamente as que são [[Função computável|Turing computáveis]]." (p. 53). Ele cita outras propostas de "máquinas de calcular universais" incluídas as de [[Percy Ludgate]] (1909), [[Leonardo Torres y Quevedo]] (1914), [[Maurice d'Ocagne]] (1922), [[Louis Couffignal]] (1933), [[Vannevar Bush]] (1936), [[Howard Aiken]] ( 1937). No entanto:

{{quote|... A ênfase está na programação de uma sequência fixa iterável de operações aritméticas. A importância fundamental da iteração condicional e transferência condicional para uma teoria geral da máquinas de calcular não é reconhecida...|Gandy p. 55}}

=== O Entscheidungsproblem (o "problema de decisão"): O décimo problema de Hilbert de 1900 ===
Com relação aos [[problemas de Hilbert]] propostos pelo famoso matemático [[David Hilbert]] em 1900, um aspecto do problema #10 tinha ficado flutuando por quase 30 anos antes de ser enquadrado com precisão. A expressão original de Hilbert para o 10º problema é a seguinte:

{{quote|'''10. Determinação da solubilidade de uma equação Diofantina'''. Dada uma [[Equação diofantina|equação Diofantina]] com qualquer número de incógnitas e com coeficientes inteiros racionais: Elaborar um processo que com ele pode ser determinado em um número finito de operações se a equação é solúvel por números inteiros racionais. O Entscheidungsproblem [problema de decisão para a lógica de primeira ordem ] é resolvido quando sabemos que um procedimento que permite a qualquer expressão lógica dada decidir por um número finito de operações a sua validade ou satisfazibilidade ... O Entscheidungsproblem deve ser considerado o principal problema da lógica matemática.|Citada, com esta tradução e o original em alemão, em Dershowitz e Gurevich de 2008}}

Em 1922, essa noção de " [[Entscheidungsproblem]] "desenvolveu-se um pouco, e H. Behmann afirmou que

{{quote|... a forma mais geral do Entscheidungsproblem [é] como se segue:

Uma prescrição bem definida geralmente aplicável é necessária, ela permitirá decidir em um número finito de passos a veracidade ou falsidade de uma dada afirmação puramente lógica ...|Gandy p. 57, citando Behmann}}

{{quote|Behmann observa que ... o problema geral é equivalente ao problema de decidir quais proposições matemáticas são verdadeiras.|Ibid.}}

{{quote|Se alguém fosse capaz de resolver o Entscheidungsproblem então teria um "procedimento para a resolução de muitos (ou mesmo todos) problemas matemáticos".|Ibid., p. 92}}

Até o [[Congresso Internacional de Matemáticos]] em 1928, Hilbert "fez suas perguntas bastante precisas. Primeiro, a matemática é [[Completude (lógica)|completa]] ... Segundo, a matemática é [[Consistência lógica|consistente]] ... E terceiro, a matemática é[[Decidibilidade| decidível]] ? " (Hodges p. 91, Hawking p. 1121). As duas primeiras questões foram respondidas em 1930 por [[Kurt Gödel]] na mesma reunião onde Hilbert fez seu discurso de aposentadoria (para desgosto de Hilbert); o terceiro- o Entscheidungsproblem teve que esperar até meados de 1930.

O problema era que uma resposta primeiro exigia uma definição precisa de "prescrição definitiva geral aplicável", que o professor de Princeton [[Alonzo Church]] viria a chamar de " [[Método Efetivo|método efetivo]] ", que podemos chamar ainda de [[Algoritmo]], e que em 1928 não existia tal definição. Mas ao longo dos próximos 6-7 anos [[Emil Post]] desenvolveu sua definição de um trabalhador passando de um cômodo para um outro cômodo escrevendo e apagando marcas em uma lista de instruções (Post 1936), assim como Church e os seus dois alunos [[Stephen Kleene]] e [[J. B. Rosser]] pelo uso do [[Lambda Cálculo|lambda-cálculo]] de Church e a [[teoria da recursão]] de Gödel (1934). O artigo de Church (publicado 15 de abril de 1936) mostrou que o Entscheidungsproblem era de fato "indecidível" e superou Turing por quase um ano (o artigo de Turing foi submetido em 28 de maio de 1936 e publicado em janeiro de 1937). Nesse meio tempo, Emil Post apresentou um breve artigo no outono de 1936, Turing, pelo menos, tinha prioridade sobre Post. Enquanto Church arbitrou o artigo de Turing, Turing teve tempo para estudar o artigo de Church e adicionar um Apêndice onde ele provava que o lambda-cálculo de Church e suas máquinas calculariam as mesmas funções.

{{quote|Mas o que Church fez foi algo bastante diferente, e em certos sentidos mais fraco. ... A construção Turing foi mais direta, e dava um argumento a partir dos primeiros princípios, fechando a lacuna da demonstração de Church.|Hodges-p. 112}}

E Post só havia proposto uma definição de calculabilidade e criticou a "definição" de Church, mas não tinha provado nada.

=== Alan Turing uma-máquina(-automática) ===
Na primavera de 1935, Turing como aluno de mestrado em Kings College Cambridge, [[Reino Unido]], aceitou o desafio; ele tinha sido estimulado pelas palestras do lógico [[Max Newman|M. H. A. Newman]] "e aprendeu com elas do trabalho de Gödel e o Entscheidungsproblem ... Newman usou a palavra "mecânico" ... Em seu obituário de Turing em 1955 Newman escreveu:

{{quote|Para a pergunta "o que é um processo "mecânico" ?" Turing retornou a resposta característica "Algo que pode ser feito por uma máquina" e ele embarcou na tarefa altamente congênita de analisar a noção geral de uma máquina de computação.|Gandy, p. 74}}

Gandy afirma que:

{{quote|Eu acho, mas não sei, que Turing, desde o início de seu trabalho, tinha como objetivo uma prova da indecidibilidade do Entscheidungsproblem. Ele me disse que a "ideia principal" do artigo veio a ele quando ele estava deitado nos prados de Grantchester no verão de 1935. A "ideia principal" poderia ter sido sua análise da computação ou a realização de que havia uma máquina universal, e assim um [[Argumento de diagonalização de Cantor|argumento de diagonalização]] para provar insolubilidade.|Ibid, p. 76}}

Enquanto Gandy acredita que a declaração de Newman acima era "enganosa", esta opinião não era compartilhada por todos. Turing tinha um interesse ao longo da vida por máquinas: "Alan tinha sonhado de inventar máquinas de escrever quando menino; [sua mãe] Sra. Turing teve uma máquina de escrever, e ele poderia muito bem ter começado perguntando a si mesmo o que significava chamar uma máquina de escrever 'mecânica'" (Hodges, p. 96). Enquanto em Princeton em busca de seu PhD, Turing construiu um multiplicador com lógica booleana (veja abaixo). Sua tese de [[Doutoramento|doutorado]], intitulada "Sistemas de Lógica Baseado em ordinais", contém a seguinte definição de "uma função computável":

{{quote|Foi dito acima que 'uma função é efetivamente calculável se os seus valores podem ser encontrados por algum processo puramente mecânico. Podemos assumir esta afirmação literalmente, a compreensão por um processo puramente mecânico, que pode ser realizada por uma máquina. É possível dar uma descrição matemática, numa certa forma normal, da estruturas destas máquinas. O desenvolvimento dessas ideias leva a definição do autor de uma função computável, e uma identificação de computabilidade com calculabilidade efetiva. Não é difícil, embora um tanto laboriosa, para provar que estas três definições [a terceira é a λ-cálculo] são equivalentes.|Turing (1939) em ''The Undecidable,'' p. 160}}

Quando Turing retornou ao Reino Unido, ele acabou se tornando juntamente responsável por quebrar os códigos secretos alemães criados por máquinas de criptografia chamadas de "O Enigma", ele também se envolveu no projeto da ACE ( Automatic Computing Engine ), "a proposta ACE [de Turing] foi efetivamente independente, e as suas raízes não estava no [[EDVAC]] [iniciativa dos EUA], mas em sua própria máquina universal "(Hodges p. 318). Argumentos continuam sobre a origem e a natureza do que tem sido chamado por Kleene (1952) Tese de Turing. Mas o que Turing provou com seu modelo de máquina-computacional aparece em seu artigo On Computable Numbers, With an Application to the Entscheidungsproblem (1937):

{{quote|[Que] o Hilbert Entscheidungsproblem pode não ter solução ... Proponho, portanto, para mostrar que não pode haver processo geral para determinar se uma dada fórmula U do cálculo funcional K é demonstrável, ou seja, não pode haver nenhuma máquina que, fornecido com qualquer um U dessas fórmulas, acabará por dizer se U é demonstrável.|A partir do artigo de Turing como reimpresso The Undecidable, p. 145}}

De Turing exemplo (a sua segunda prova): Se alguém perguntar por um procedimento geral para nos dizer: "Será que esta máquina imprime 0", a pergunta é "indecidível".

=== 1937-1970: O "computador digital", o nascimento da "ciência da computação" ===
Em 1937, enquanto em Princeton trabalhando em sua tese de doutorado, Turing construiu um multiplicador (lógico-booleano) digital do nada, fazendo seus próprios relés eletromecânicos (Hodges p. 138). "A tarefa de Alan foi para encarnar o projeto lógico de uma máquina de Turing em uma rede de relé-operacinados interruptores ..." (Hodges p. 138). Embora Turing pudesse estar inicialmente curioso e experimentando, trabalhos muito sérios, no mesmo sentido, estavam sendo desenvolvidos na Alemanha ( [[Konrad Zuse]] (1938)), e nos [[Estados Unidos]] ( [[Howard Aiken]] ) e [[George Stibitz]] (1937); os frutos do seus trabalhos foram usados pelos militares do Eixo e dos Aliados na [[Segunda Guerra Mundial]] (cf Hodges p. 298-299).No início e meados da década de 1950, [[Hao Wang (acadêmico)|Hao Wang]] e [[Marvin Minsky]] reduziram a máquina de Turing a uma forma mais simples (um precursor da [[máquina de Post-Turing]] de [[Martin Davis]]); simultaneamente pesquisadores europeus estavam reduzindo o novíssimo [[computador eletrônico]] a um computador como objeto teórico equivalente ao que estava sendo chamado de "máquina de Turing". No final dos anos 1950 e início dos anos 1960, os desenvolvimentos, coincidentemente paralelamente, Melzak e Lambek (1961), Minsky (1961), e Shepherdson e Sturgis (1961) continuaram o trabalho europeu e reduziram a máquina de Turing para uma máquina mais amigável, como um computador de modelo abstrato chamado de counter machine ; Elgot e Robinson (1964), Hartmanis (1971), Cook e Reckhow (1973) levaram este trabalho ainda mais com a máquina de registo e de acesso aleatório máquina modelos, mas basicamente todos são apenas máquinas multi-fita de Turing com um conjunto de instruções aritméticas.

=== 1970-presente: a máquina de Turing como um modelo de computação ===
Hoje, o contador, registrador e máquinas de acesso aleatório e seu pai a máquina de Turing continuam a ser os modelos de escolha para os teóricos que investigam questões da teoria da computação. Em particular, a [[Complexidade computacional|teoria da complexidade computacional]] faz uso da máquina de Turing;

Dependendo dos objetos um gosta de manipular os cálculos (números como inteiros não negativos ou cordas alfanuméricos), dois modelos têm obtido uma posição dominante na teoria da complexidade baseada em máquina:

{{quote|a máquina ''off-line multi-fita'' de Turing ..., que representa o modelo padrão para a computação orientada a cadeia, e
a máquina de acesso aleatório (RAM), como introduzida por Cook e Reckhow ..., que modela o estilo de computador idealizado por Von Neumann.|van Emde Boas 1990:4}}

{{quote|Somente na área relacionada com a análise de algoritmos esse papel é assumido pelo modelo de RAM.|van Emde Boas 1990:16}}

== Teoria da computação ==
{{Teoria da computação}}

== Ver também ==
* [[Formiga de Langton]], uma representação simples da máquina de Turing em duas dimensões
* [[Tese de Church-Turing]], que diz que máquinas de Turing podem executar qualquer computação que pode ser executada
* [[brainfuck]], é uma linguagem Turing completa, desenhada para desafiar e confundir os programadores
* [[Vermes de Paterson]] - família de autômatos celulares criados para modelar o comportamento e os padrões de alimentação de determinados vermes pré-históricos

{{Referências}}

== Bibliografia ==
* [[Rolf Herken]]: ''The Universal Turing Machine - A Half-Century Survey'', Springer Verlag, ISBN 3-211-82637-8
* [[Paul Strathern]]: ''Turing and the Computer - The big idea'', Anchor Books/Doubleday, ISBN 0-385-49243-X
* {{Link||2=http://www.abelard.org/turpap2/tp2-ie.asp |3=Turing, A., ''On Computable Numbers, With an Application to the Entscheidungsproblem''}}, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reimpresso em M. David (ed.), ''The Undecidable'', Hewlett, NY: Raven Press, 1965;
* Boolos, G. and Jeffrey, R., ''Computability and Logic'', 2ª ed., Cambridge: Cambridge University Press, 1980.
* {{Link||2=http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm |3=Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols"}}, ''Romanian Journal Of Information Science and Technology'', 1(3), 259-265, 1998.  (surveys known results about small universal Turing machines)

== Ligações externas ==
{{Commons|Turing Machine}}
* {{Link|en|http://plato.stanford.edu/entries/turing-machine/|Turing Machines|Enciclopédia de Filosofia de Stanford}}
* {{Link|en|http://plato.stanford.edu/entries/church-turing/|The Church-Turing Thesis|Enciclopédia de Filosofia de Stanford}}
* {{Link|en|http://ironphoenix.org/tril/tm/|Turing Machine Simulator|simulador de máquina de Turing}}

{{DEFAULTSORT:Maquina Turing}}
[[Categoria:Máquina de Turing| ]]
[[Categoria:Métodos formais]]
[[Categoria:Teoria da computação]]
[[Categoria:Década de 1930 na ciência]]