Maquina De Turing

CAPÍTULO 9

MÁQUINAS DE TURING

9.1. Introdução 301

9.2. A Máquina de Turing padrão 302

9.3. Diagrama de estados ou de transição da MT 309

9.4. MT como aceitador de linguagens 311

9.5. MT como transdutores 319

9.6. Combinações de máquinas de Turing para tarefas complicadas 324

9.7. A tese de Turing 325

Bibliografia 328

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

LEI/DEIFCTUC/2009/@ADC Documento de trabalho 301

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á encontrámos linguagens que não são livres de contexto, como por exemplo anbncn. Por

isso não é possível construir um autómato de pilha que as aceite.

Será que uma MT é suficientemente poderosa para aceitar linguagens dependentes do

contexto? Todas elas? Qual é o autómato mais poderoso? Quais os limites da computação?

São questões às quais as MT respondem.

Máquina de Turing

Um modelo abstracto de computação

Problemas resolúveis e

irresolúveis

Figura 9.1.1. Importância da Máquina

de Turing. Até hoje não foi ainda

inventado um computador capaz de

resolver um problema que a MT não

possa resolver. Este facto mantém ainda

válida a tese de Church-Turing

Teoria da Computação Cap. 9 Máquinas de Turing

LEI/DEIFCTUC/2009/@ADC Documento de trabalho 302

9.2. A máquina de Turing padrão

A máquina de Turing é um autómato, com uma unidade de controlo e com um dispositivo

especial que funciona simultaneamente como entrada (onde lê), armazenamento, e saída (onde

escreve). Esse dispositivo é uma fita unidimensional que contém um número ilimitado de

células cada uma das quais pode conter um único símbolo. Essa é a sua característica

distintiva em relação aos autómatos finitos (que não têm dispositivo de armazenamento) e

aos autómatos de pilha (que armazenam numa pilha ).

A fita da MT prolonga-se indefinidamente em ambos os sentidos e por isso pode conter

uma quantidade infinita de informação. Esta informação pode ser lida e alterada em qualquer

ordem e daí o potencial da MT.

Associada à fita está uma cabeça de leitura-escrita que se pode mover sobre a fita para a

esquerda ou para a direita, podendo escrever ou ler um único símbolo em cada movida.

Figura 9.2.1 Componentes da Máquina de Turing

Definição 9.2.1.

Uma máquina de Turing M é definida pelo septeto

M = (Q,