Turin

Teoria da Computação

Cap. 9 Máquinas de Turing

CAPÍTULO 9

MÁQUINAS DE TURING

9.1. Introdução 9.2. A Máquina de Turing padrão 9.3. Diagrama de estados ou de transição da MT 9.4. MT como aceitador de linguagens 9.5. MT como transdutores 9.6. Combinações de máquinas de Turing para tarefas complicadas 9.7. A tese de Turing Bibliografia

301 302 309 311 319 324 325 328

LEI/DEIFCTUC/2009/@ADC

Documento de trabalho

299

Teoria da Computação

Cap. 9 Máquinas de Turing

LEI/DEIFCTUC/2009/@ADC

Documento de trabalho

300

Teoria da Computação

Cap. 9 Máquinas de Turing

9.1. Introdução
Uma pesquisa no Google em 6 de Dezembro de 2007 com “turing machine” deu 1.820.000 resultados. Este número mostra a importância do tema. 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. Existe em Portugal um blog como seu nome, http://turing-machine.weblog.com.pt, que merece uma visita. 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 abstracta capaz de executar essas operações segundo regras bem definidas. A MT 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 MT? Com que linguagens se relacionam? Já