automato

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (469 palavras )
  • Download(s) : 0
  • Publicado : 28 de outubro de 2014
Ler documento completo
Amostra do texto
-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 NevesFerreira 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 ideiade 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, massim 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 equais 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á ummodelo 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 umexemplo
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...
tracking img