Máquina de Turing

Origem: Wikipédia, a enciclopédia livre.

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 à 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 II Guerra Mundial, tendo utilizado alguns dos conceitos teóricos desenvolvidos para o seu modelo de computador universal.

[editar] Definição

[editar] Descrição informal

Uma máquina de Turing consiste em:

1. Uma fita que é divida 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 0) e um ou mais outros símbolos. 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.
2. Um cabeçote, que pode ler e escrever símbolos na fita e mover-se para a esquerda e para a direita.
3. 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.
4. Uma tabela de ação (ou função de transição) que diz à máquina que símbolo escrever, como mover o cabeçote ('E' para esquerda e 'D' 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 nenhuma entrada na tabela para a combinação atual de símbolo e estado então a máquina pára.

Note que cada parte da máquina é finita; é sua quantidade de fita potencialmente ilimitada que dá uma quantidade ilimitada de espaço de armazenamento. As máquinas de turing desenvolveram-se desde 1934

[editar] Definição formal

[editar] Máquina de Turing com uma fita

Mais formalmente, uma máquina de Turing (com uma fita) é usualmente definida como uma sêxtupla M = (Q,Γ,s,b,F,δ), onde

• Q é um conjunto finito de estados
• Γ é 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 E é o movimento para a esquerda e D é 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 {E,D} para {E,D,P}, 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.

[editar] Máquina de Turing com k fitas

Uma máquina de Turing com k fitas também pode ser descrita como uma sêxtupla M = (Q,Γ,s,b,F,δ), onde

• Q é um conjunto finito de estados
• Γ é o alfabeto da fita (conjunto finito de símbolos)
• é o estado inicial
• é o símbolo branco
• é o conjunto dos estados finais
• é uma função parcial chamada função de transição, onde E é o movimento para a esquerda e D é o movimento para a direita.

Note que uma máquina de turing com "k" fitas não é mais poderosa que uma máquina de Turing tradicional.

[editar] Exemplo

A máquina de Turing a seguir tem um alfabeto {'0', '1'}, onde 0 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 0 no meio. Por exemplo, "111" torna-se "1110111". O conjunto dos estados é {s1, s2, s3, s4, s5} e o estado inicial é s1. A tabela de ação é dada a seguir.

 Old Read   Wr.      New     Old Read   Wr.      New
 St. Sym.   Sym. Mv. St.     St. Sym.   Sym. Mv. St.
 - - - - - - - - - - - -     - - - - - - - - - - - -
  s1  1  ->  0    D   s2      s4  1  ->  1    E   s4
  s2  1  ->  1    D   s2      s4  0  ->  0    E   s5
  s2  0  ->  0    D   s3      s5  1  ->  1    E   s5
  s3  0  ->  1    E   s4      s5  0  ->  1    D   s1
  s3  1  ->  1    D   s3

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 0, 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       Passo Estado Fita
 - - - - - - - -         - - - - - - - - -
    1  s1   11        9  s2   1001 
    2  s2   01       10  s3   1001
    3  s2   010      11  s3   10010
    4  s3   0100     12  s4   10011
    5  s4   0101     13  s4   10011
    6  s5   0101     14  s5   10011
    7  s5   0101     15  s1   11011
    8  s1   1101       -- pára --

O comportamento desta máquina pode ser descrito como um laço (loop): ele inicia em s1, substitui o primeiro 1 com um 0, então usa o s2 para mover para a direita, passando pelos 1's e pelo primeiro 0 encontrado. S3 então passa pela próxima seqüência de 1'd (inicialmente não há nenhuma) e substitui o primeiro 0 que encontra por um 1. S4 move de volta para a esquerda, passando pelos 1's até encontrar um 0 e vai para o estado s5. S5 então move para a esquerda, passando pelos 1's até achar o 0 que foi originalmente escrito por S1. Ele substitui o 0 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 0 (este é o 0 que fica entre as duas cadeias de 1's), situação na qual a máquina pára.

[editar] 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).

[editar] Máquinas de Turing universais

• Artigo principal Máquina de Turing universal

Toda máquina de Turing computa uma certa função computável 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.

[editar] Comparação com máquinas reais

Freqüentemente 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:

1. 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.
2. 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. Freqüentemente o tempo de processamento requerido é o maior problema.
3. 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.
4. Máquinas de Turing descrevem algoritmos independemente 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.
5. 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 sistemas operacionais e processadores de texto, são escrito para receber entradas irrestritas através da execução, e portanto não páram. Máquinas de Turing não modelam tal "computação contínua" bem (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 theta(nlogn) em algoritmos de ordenação.

[editar] Máquina de Turing física

Não é difícil simular uma máquina de Turing num computador moderno (exceptuando pela quantidade de memória limitada existente nos computadores actuais).

É também possivel 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 contruçã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 rolamentos.

A máquina encontra-se actualmente em exibição na entrada do Departamento de Ciência de Computadores da Universidade de Heidelberg, na Alemanha.

É também possivel, usando algumas centenas de espelhos, construir uma máquina de Turing óptica na sua própria casa usando o mapa da ferradura de Smale. Este é baseado num trabalho do matemático estado-unidense Stephen Smale.

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.

[editar] Ver também

• Langton's ant, a simple two-dimensional analogue of the Turing machine.
• Probabilistic Turing machine
• Tese de Church-Turing, que diz que máquinas de Turing podem executar qualquer computação que pode ser executada.
• Busy Beaver
• Computability logic
• Turing completeness
• Turing tarpit, any computing system or language which, like the Turing machine, is not only Turing-complete but also useless for practical computing.

[editar] Referências

• 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
• 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.
• 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)

[editar] Ligações externas

• A Máquina de Turing na Enciclopédia de Filosofia de Stanford
• Informação detalhada sobre a Hipótese de Church-Turing (Enciclopédia de Filosofia de Stanford)
• Citações de CiteSeer

[editar] Simuladores

• Visual Turing, a Turing machine interactive simulator/IDE (software livre para MS Windows).
• Suzanne Britton's Turing Machine Simulator (applet Java).
• Simulador em C++ de uma Máquina de Turing Multifita Determinística e Não-Determinística (software livre).
• Simulador em C++ de uma Máquina de Turing Universal (a qual aceita a Máquina de Turing Multifita) (software livre).
• A Máquina de Turing enquanto jogo freeware de tabuleiro para PCs
• Máquina de Turing II - um jogo freeware educativo de tabuleiro para PCs
• Turing Train Terminal - Uma máquina de Turing construida a partir de combóios à escala.