Lauda: Maquina de Turing

Lauda: Máquina de Turing
Nome: Mariana Rosal Tavares RGM: 85293-7
Professor Ivan Oliveira Curso: Ciência da Computação.

A máquina de Turing ou “Máquina Automática” é um modelo abstrato de um computador, ou seja, um autômato imaginário. Foi criada em 1936, pelo matemático inglês Alan Turing conhecido como “Pai da Computação”, muito antes da invenção do computador digital. Capaz de calcular qualquer função matemática mediante a um determinado conjunto de instruções, para qualquer sistema formal existe uma máquina de Turing que pode ser programada para imita-lo.
Formalmente a máquina de Turing se consiste em uma fita que pode ser infinita para esquerda ou para direita, dividido em células adjacentes, que contém um símbolo do alfabeto, um cabeçote que pode ler e escrever símbolos na fita movimenta-se para esquerda e para direita, um registrador de estados que faz o armazenamento dos estados da máquina e uma tabela com as funções de transição, que nos diz que símbolo escrever, como mover o cabeçote e qual será o novo estado dependendo do símbolo que esta lendo e do estado que se encontra.
Para definir formalmente uma máquina de Turing, usa-se a tupla, que da esquerda para direita, consiste em um alfabeto de símbolos, conjunto de estados, as funções de transição, o estado inicial, o conjunto de estados finais, conjuntos de símbolos auxiliares, símbolo branco e o símbolo que indica o inicio da fita.
A função de transição vai ser um estado que lê um símbolo que vai para o outro estado e escreve um símbolo e nos diz a direção, ou seja, se ele vai para direita ou para esquerda. Se não houver entrada de alguma tabela para a combinação atual de símbolos e estados, então a máquina para. Resumindo a máquina de Turing é um simples mecanismo capaz de realizar cálculos.

Referências: http://pt.wikipedia.org/wiki/M%C3%A1quina_de_Turing http://www.educ.fc.ul.pt/docentes/opombo/seminario/vonnewman/NetMenu/maquina_de_turing.htm