Aspectos teóricos da computação - Máquina de Turing
Por: SonSolimar • 19/9/2018 • 974 Palavras (4 Páginas) • 240 Visualizações
...
Segue abaixo uma lista de regras - código e descrição - que dirão a uma máquina de Turing como desenvolver um determinado "jogo":
[pic 1]
Note que se houver um branco no quadrado ativo quando os estados forem 1 ou 7, ou se há um I no quadrado ativo quando o estado da máquina é 2, ela para, pois não saberia o que fazer. O jogo neste caso é duplicar uma sequência de “I”s que estejam na fita. Se a fita contiver I I I I, no final conterá I I I I I I I I. Para se jogar (em termos mais técnicos diríamos executar o programa descrito na lista de regras) é necessário especificar uma configuração inicial na fita, qual o quadrado inicial ativo e o estado inicial da máquina. Quando a máquina começar a executar, ela, a partir do estado inicial e do quadrado ativo seguirá a sequência (lógica) de regras que darão o produto final.
Em sua essência, toda máquina de Turing move-se ou move símbolos, de uma posição para outra em uma fita, da mesma maneira que no exemplo dado acima ou visto no applet. Nos dias de hoje estes símbolos podem ser impulsos eletrônicos em um microcircuito e a fita uma série de endereços de memória em um chip, mas a ideia é a mesma. Turing provou que sua hipotética máquina é uma versão automatizada de um sistema formal especificado por uma combinação inicial de símbolos (o conjunto de “I”s na fita no início do processo) e as regras (aquelas instruções escritas). Os movimentos são mudanças de “estado” da máquina que correspondem a específicos passos de computação. Turing provou que para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imitá-lo. Era este sistema formal genérico, com a habilidade de imitar qualquer outro sistema formal, o que Turing procurava. Tais sistemas chamam-se Máquinas de Turing Universais.
2 REFERÊNCIAS BIBLIOGRÁFICAS
HODGES, Andew - Turing Um Filósofo da Natureza - 1ª Edição.
POZZA, O.A.; PENEDO, S. A Máquina de Turing. Dissertação – Mestrado em Ciências da Computação – Universidade Federal de Santa Catarina, SC. 2002.
...