Máquina de turing

FACULDADE DOS GUARARAPES - FG
CURSO CIÊNCIA DA COMPUTAÇÃO – TURMA CCO7NA

MÁQUINA DE TURING

RENATA SANTOS

CARLOS ALBUQUERQUE

LEITURA DE TEXTO

JABOATÃO DOS GUARARAPES - PE / 2012.2

MÁQUINA DE TURING

1. INTRODUÇÃO

Em 1936 o matemático inglês Alan Mathison Turing, que tinha na época, 24 anos de idade, idealizou uma máquina que seria capaz de calcular qualquer função matemática mediante um determinado conjunto de instruções. Naturalmente, o propósito não era a criação de um computador como os atuais, mas é possível encontrar alguns princípios semelhantes. Alan Turing mostrou que a computação das operações de leitura escrita e exclusão de símbolos binários poderiam ser satisfeitas por uma máquina que continha uma fita de comprimento ilimitado, com quadrados de tamanho definido sobre ela e um dispositivo com um número finito de estados, que realizava as operações na fita.

Foi formalizado o termo algoritmo, em 1936, como sendo: um conjunto finito de instruções simples e precisas, que são descritas como um número finito de símbolos.

A teoria da máquina foi publicada pela primeira vez um artigo intitulado “On Computable Number, with on Application on the Entscheidungsproblem”, em resposta ao tratamento do problema da decisão, na universidade de Princeton, Nova Jersey-EUA, onde Alan Turing estudava.

2. DEFINIÇÃO

É um dispositivo imaginário que formou a estrutura para fundamentar a ciência da computação moderna, conhecido como máquina universal

O conceito de máquina de Turing é semelhante ao de uma fórmula ou equação. Assim. Há uma infinidade de possíveis máquinas de Turing, cada uma correspondendo a um método definido ou algoritmo. Turing propôs que casa algoritmo, formalizado como um conjunto finito de instruções bem definidas. Pudesse ser interpretado e executado por um processo mecânico.

Uma máquina de Turing consiste em:

1.