Maquina de Turing

Máquina de Turing

Faculdade Joaquim Nabuco
Aluno: Luiz Henrique Ribeiro de Oliveira
Matricula: 10007238
6º Período
Profº Clóvis Holanda

Sumário
Introdução 3
Máquina de Turing universa 6
Edição de Máquinas de Turing 7
Visual Turing 2.0 8
Execução de Máquina de Turing 9
Problema de Comparação de Lista e Solução Simplista 9
Formato de Entrada 9
Formato de Saída 9
Algoritmo de Solução Simplista 10
Submáquina genérica marca_ e _vai 10
Máquinas específicas de reconhecimento de palavras 11
Implementação 11
Submáquina inicial 12
Submáquina prox_let 12
Submáquina prox_pal 12
Submáquina volta_pal 12
Submáquina reinicia_pal 13
Submáquina aceita_pal 13
Submáquina recusa_pal 13
Submáquina final 14
Submáquina contábil 14
Submáquina mais_um 14
Conclusão 14

Introdução

As Máquinas de Turing (MT) estiveram no centro do desenvolvimento dos computadores e da computação durante os últimos 70 anos. Alain Turing (1912-1954) foi um brilhante matemático, em Cambridge, Inglaterra, numa época efervescente de desenvolvimento da lógica e da matemática que haveria de resultar no computador digital, os anos 30 e 40 do século passado. É geralmente considerado como o fundador das ciências da computação.

Outros matemáticos famosos, como Gödel, Bertrand Russel na Europa, Church nos EUA, foram contemporâneos de Alain Turing. Em 1940 Alan Turing procura formalizar a noção de algoritmo, identificando as operações fundamentais e primitivas que possam servir de base ao cálculo matemático.

Depois, definiu uma máquina abstrata capaz de executar essas operações segundo regras bem definidas. A Máquinas de Turing foi assim concebida para ser um modelo de computação, formalizando um conjunto de operações básicas às quais se pode reduzir qualquer computação.

Os autómatos finitos são para as linguagens regulares, os autómatos de pilha para as linguagens livres de contexto. E as Máquinas de Turing? Com que linguagens se relacionam? Já encontrámos