Turin

Disponível somente no TrabalhosFeitos
  • Páginas : 22 (5295 palavras )
  • Download(s) : 0
  • Publicado : 4 de novembro de 2012
Ler documento completo
Amostra do texto
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 328LEI/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. Outrosmatemá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 umamá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 Figura 9.1.1. Importânciada Máquina de Turing. Até hoje não foi ainda
Um modelo abstracto de computação

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 Problemas resolúveis e irresolúveis

LEI/DEIFCTUC/2009/@ADC

Documento de trabalho

301

Teoria da Computação

Cap. 9 Máquinas de Turing

9.2. A máquina de Turingpadrã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 aesquerda ou para a direita, podendo escrever ou ler um único símbolo em cada movida.

UNIDADE DE CONTROLO

R/W

FITA 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, , , , q0, em que Q é o conjunto de estados internos da unidade de controlo é o alfabeto de entrada , F)

LEI/DEIFCTUC/2009/@ADC

Documento de trabalho

302...
tracking img