ATPS Teoria Da Computação

ETAPA 02

Relatório 03 Alan Turing.

Proposta por Alan Truing em 1936, é universalmente conhecida a aceita como formalização de algoritimo, trata-se de mecanismo simples que formaliza a idéia de uma pessoa que realiza cálculo, possui , no mínimo, o mesmo poder computacional de qualquer computador de propósito geral; não constitui uma máquina, como definida anteriormente, mas sim um programa para uma máquina universal.

Noção como Máquina

Os símbolos podem pertencer:

Ao alfabeto de entrada:

Ao alfabeto auxiliar

branco β

fita de início de marcador ¤

Inicialmente, a palavra a ser processada ocupa as células mais à esquerda, após o marcador de início debranco fita, ficando as demais com .

Fita:

Usada simultaneamente como dispositivo de entrada,

de saída e de memória de trabalho;

É finita à esquerda e infinita (tão grande quanto

necessário) à direita, sendo dividida em células, cada

uma das quais armazenando um símbolo.

O programa pode ser representado como um grafo

Finito.

A parada pode ser de duas maneiras: aceitando ou w rejeitando a entrada .

As condições de parada são as seguintes:

º ESTADO FINAL: A máquina assume um estado final: a

máquina para, e a palavra de entrada é aceita;

º FUNÇÃO INDEFINIDA: A função programa é indefinida para o argumento (símbolo lido e estado corrente): a máquina para, e a palavra de entrada é rejeitada;

º MOVIMENTO INVÁLIDO: O argumento corrente da função programa define um movimento à esquerda e a cabeça da fita já se encontra na célula mais à esquerda: a máquina para, e a palavra de entrada é rejeitada.