automato

-489585-109220Escola Superior de Tecnologia
Curso de 1º Ciclo em Engenharia Informática
2º Semestre do 1º Ano
Unidade Curricular: Matemática para a Informática II
Docente: Ana Paula Neves Ferreira da Silva
Ano lectivo 2013/2014
Trabalho Prático nº2
Data de entrega: 6 de Junho
Nome do Aluno: Diogo Filipe Marques Carvalho Nº2013108
Nome do Aluno: Tiago Neves Baeta Nº20131013
1. Enquadramento Histórico
A máquina de Turing foi proposta por Alan Turing em 1936 e é universalmente conhecida e aceita como formalização de algoritmo. Trata-se de um mecanismo simples que formaliza a ideia de uma pessoa que realiza cálculos, semelhante a um automato finito.Possui por sua vez, no mínimo, o mesmo poder computacional de qualquer computador de propósito geral.Não constitui uma máquina, mas sim um programa para uma máquina universal.O modelo da Máquina de Turing é importante para a Ciência da Computação porque através dele é possível determinar quais as funções que são computáveis e quais não são através de um conceito bastante simples (no qual é possível provar teoremas de forma facilitada) define-se assim a classe das funções calculáveis logo se uma função pode ser calculada, há um modelo de Turing ou equivalente para tal função.
2.Descrição de uma Máquina de Turing97726585090
Uma Máquina de Turing é uma 7-upla: M =(Q, , Γ ,,q0, qaceita, qrejeita) q0 estado inicial da máquina, tal que q0 é elemento de Q; qaceita é o estado de aceitação da máquina e pertence a Q; qrejeita é o estado de aceitação da máquina e pertence a Q, onde qaceita ≠ qrejeita
O Símbolo de início de fita ocorre exatamente uma vez e sempre na célula mais à esquerda da fita e a cabeça da fita encontra-se na célula mais à esquerda da fita.
3. Apresentação de um exemplo
3.1 Descrição do problema
A função programa considera: estado corrente p Q, símbolo lido da fita au ( V { ß, }) para determinar: novo estado q Q símbolo a ser gravado av ( V {