Saltar para: Post [1], Pesquisa e Arquivos [2]

O Bico de Gás



Sexta-feira, 20.10.06

Máquinas (VII)

Máquina de Turing:


Uma máquina de Turing consiste em:
  1. Uma fita que é divida em células, uma adjacente à outra. Cada célula contem 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. (Wikipédia)

ASENSIO

Autoria e outros dados (tags, etc)

às 23:39



Pesquisar

Pesquisar no Blog  


calendário

Outubro 2006

D S T Q Q S S
1234567
891011121314
15161718192021
22232425262728
293031