A Maquina de Turing e maquina de Turing universal

Ma´quina de Turing e ma´quina de Turing universal

Rodrigo Santos de Souza

1 Universidade Cato´lica de Pelotas - UCPel Mestrado em Cieˆncia da Computac¸a˜o Disciplina de Teoria da Computac¸a˜o Prof. Antoˆnio Carlos da Rocha Costa

Resumo.  Este trabalho descreve a ma´quina de Turing e a ma´quina de Turing universal segundo a o´tica de duas bibliografias distintas. O objetivo e´ resumida- mente apresentar o que e´ cada ma´quina e quais suas caracter´ısticas apontadas pelos livros Elementos de Teoria da Computac¸a˜o, de autoria de Harry R. Lews e Christos H. Papadimitriou e Teoria da Computac¸a˜o ma´quinas universais e Computabilidade, de Tiaraju´ A. Diverio e Paulo B. Menezes.

1. Introduc¸a˜o

A ma´quina de Turing foi proposta por Alan Turing e 1936 e embora tenha sido criada anos antes do primeiro computador digital, tem uma grande importaˆncia para a cieˆncia da computac¸a˜o, pois possui no m´ınimo o mesmo poder computacional de qualquer computa- dor de propo´sito geral.  Devido a sua importaˆcia, este texto tem o objetivo de apresentar a maquina de Turing e a ma´quina de Turing universal segundo a o´tica de dois livros, sa˜o eles: Elementos de Teoria da Computac¸a˜o, de autoria de Harry R. Lews e Christos H. Pa- padimitriou e Teoria da Computac¸a˜o Ma´quinas Universais e Computabilidade, de Tiaraju´

1. Diverio e Paulo B. Menezes. A orgaizac¸a˜o to texto traz dois cap´ıtulos distintos em que cada um trata o assunto sengundo a visa˜o de cada um dos livros.

1. Livro: Elementos de Teoria da Computac¸a˜o (Harry R. Lews e Christos H. Papadimitriou)

1. Ma´quina de Turing

Os aspectos ba´sicos das ma´quinas de Turing sa˜o semelhantes aos dos Autoˆmatos Finitos e Autoˆmatos de Pilha,  mas sa˜o capazes de reconhecer linguagens que sa˜o imposs´ıveis para  estes  autoˆmatos.   A  sua  forma  ba´sica  consiste  de  um  controle  finito,  uma  fita  e um cabec¸ote que pode realizar leituras ou escritas na fita (ver Figura 1).  Existem out- ras formas mais sofisticadas das ma´quinas de Turing que se utilizam de mu´ltiplas fitas, ma´quinas com dispositivos de memo´ria que podem ser lidos ou gravados em regime de acesso aleato´rio, mas nenhum dos modelos apresenta um poder computacional maior do que a forma ba´sica.  Uma visa˜o amplamente aceita e´ de que qualquer forma aceita´vel de expressa˜o das ide´ias contidas em um “algor´ıtmo” seja, em u´ltima instaˆncia, equivalente a` que pode se se obter empregando-se uma ma´quina de Turing.

A ma´quina de Turing foi idealizada para satisfazer os seguintes crite´rios: Devem operar como Autoˆmatos.[pic 1]

Devem ser s´ımples de descrever, de definir e de entender.[pic 2]

Podem apresentar a maior generalidade poss´ıvel quanto a`s computac¸o˜es que po- dem realizar.[pic 3]

Uma ma´quina de Turing consiste de um controle de estados finito associado a uma unidade de fita.  A comunicac¸a˜o entre ambas e´ proporcionada por um s´ımples cabec¸ote responsa´vel pela leitura e escrita dos s´ımbolos na fita.   A unidae de controle opera de forma que a cada passo ela realiza duas operac¸o˜es, que dependem do seu estado atual e do s´ımbolo lido da fita pelo cabec¸ote:

1. Levar a unidade de controle para um novo estado.
2. Gravar um s´ımbolo na ce´lula na posic¸a˜o apontada pelo cabec¸ote, ou enta˜o Mover o cabec¸ote uma posic¸a˜o, para a esquerda ou direita.

A fita e´ delimitada na extremidade esquerda, mas pode extender-se indefinida-

mente para a direita. Para delimitar a extremidade esquerda utiliza-se o s´ımbolo . e sempre que o cabec¸ote encontrar este s´ımbolo, move-se automaticamente uma posic¸a˜o para a direita. Uma ma´quina de Turing e´ alimentada gravando-se previamente a cadeia de entrada nas ce´lulas mais a esquerda da fita, imediatamente a direita do s´ımbolo ., sendo o restaante da fita preenchido com espac¸os em branco,  representados pelo s´ımbolo    . Os so´mbolos      e      denotam o movimento do cabec¸ote, para esquerda ou para direita, respectivamente, sendo que nenhum dos dois podem ser membro de qualquer alfabeto utilizado.  A ma´quina e´ livre para modificar o conteu´do de qualquer posic¸a˜o da fita, seja na sua cadeia de entrada assim como nos infinitos espac¸os em brancos existentes a direita dela[Lewis 2000].[pic 4][pic 5]

1. Definic¸a˜o formal da ma´quina de Turing:

Uma ma´quina de Turing e´ uma quintupla (K, Σ, δ, s, H), onde

K:  E´  um conjunto finito de estados;

Σ:  E´  o alfabeto de entrada;

s:  E´  o estado inicial. Sendo que s ∈ K;

H:  E´  o conjunto de estados de parada. Sendo que H ⊆ K);        S[pic 6]

δ:  A func¸a˜o de transic¸a˜o, e´ uma func¸a˜o de (K        H)        Σ para K        (Σ

tal que,

• para todos os q ∈ K − H, se δ(q, .) = (p, b), enta˜o b =→

{→, ←}),

• para todos os q ∈ K − H e a ∈ Σ, se δ(q, a) = (p, b), enta˜o b ƒ= .

[pic 7]

Figure 1. MODELO BA´ SICO DE UMA MA´ QUINA DE TURING

Exemplo:

Considera-se uma ma´quina de Turing M  = (K, Σ, δ, s, {h}), onde

K = {q0, q1, h}

Σ = {a, H, .}

...