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

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


Comentar:

CorretorEmoji

Se preenchido, o e-mail é usado apenas para notificação de respostas.

Este blog tem comentários moderados.

Este blog optou por gravar os IPs de quem comenta os seus posts.



Pesquisar

Pesquisar no Blog  


calendário

Outubro 2006

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