6.6 Adaptive information layering
6.6.2 Layering information
Apêndice A –
Codificando Máquinas de Turing como CadeiasComo vimos na seção 2.3 deste volume, uma máquina de Turing X qualquer pode ser descrita por meio de uma tupla X=(Q,Σ,Γ,δ,s, ,F). Essa definição será o ponto de partida para representarmos X como uma cadeia. Uma primeira idéia seria simplesmente escrever a definição formal “em uma só linha” e usá-la como cadeia. Porém, nesse caso, teríamos que usar um alfabeto com muitos símbolos, que é algo que não desejamos.
O que nós vamos querer é codificar uma MT usando o seu próprio alfabeto de entrada. Para simplificar, vamos considerar apenas o alfabeto de entrada {0,1}. Ou seja, vamos trabalhar com as máquinas de Turing na forma:
X = (Q, {0,1}, Γ, δ, s, , F)
Agora o problema será representar todas as máquinas desse tipo usando apenas 0’s e 1’s. A idéia básica dessa representação será transformar todos os
elementos de cada conjunto da definição em números naturais maiores que zero. Em especial, basta numerar os elementos dos conjuntos Q, Γ e os
movimentos da cabeça, pois as outras partes da definição são dadas a partir deles. Cada um desses conjuntos usará uma numeração separada, que descreveremos, por enquanto, como #n (para algum valor n).
Seguindo a ordem em que aparece na definição formal, vamos começar falando do conjunto de estados Q. Vamos considerar que cada MT terá, pelo menos dois estados. Cada estado será representado por um número, que pode ir de #1 a infinito O estado #1 será sempre o estado inicial e o estado #2 será sempre o estado de aceitação, que será único. (Isso não é um problema porque toda MT com vários estados de aceitação pode ser convertida para
uma MT com um só estado de aceitação). Os outros estados podem ser numerados de qualquer maneira com números a partir de #3. Isso pode ser resumido pela tabela abaixo:
Número Estado que representa
#1 Estado inicial
#2 Estado de aceitação
#n, para n > 2 Quaisquer outros estados
Agora vamos falar do alfabeto de fita Γ, que inclui o alfabeto de entrada {0,1}, pela definição dada na seção 2.3. Também vamos representar cada símbolo desse alfabeto com um número de #1 a infinito. O símbolo 0 será representado pelo número #1 (não usamos #0 porque, como foi dito antes, os números precisam ser maiores que zero). Já o símbolo 1 será representado como #2. O símbolo branco ( ) também faz parte desse alfabeto e será representado como #3.
Quanto aos demais símbolos de Γ, eles vão variar de máquina para máquina. Em todas elas, no entanto, eles têm uma função meramente auxiliar. Por isso, eles podem ser representados, em qualquer ordem, por quaisquer números a partir de #4. Por exemplo, se a MT usa os símbolos A e B, podemos representar com {A=#4 e B=#5} ou {A=#5 e B=#4}, etc. A tabela abaixo resume a representação dos símbolos:
Número Símbolo que representa
#2 1
#3 Símbolo branco
#n, para n > 3 Quaisquer outros símbolos que
não sejam símbolos de entrada
Ao descrevermos a representação númerica de Q e Γ, veja que acabamos por descrever também como representar s (o estado inicial), F (o conjunto de estados de aceitação) e (o símbolo branco). O que falta agora é a função de transição δ, que é a parte mais importante. Aliás, a representação da função de transição já será a representação final da máquina de Turing, pois todas as outras informações da MT podem ser obtidas a partir dela.
Na representação da função, vamos assumir que o movimento E (esquerda) será representado por #1 e D (direita) será representado como #2, como mostra a tabela abaixo:
Número Movimento que representa
#1 E (esquerda)
#2 D (direita)
Com isso, podemos definir cada transição de δ usando apenas valores numéricos. Por exemplo, uma transição:
Assumindo que qinicio é o estado inicial e qaceita o estado de aceitação, a
transição pode ser descrita assim:
δ( #1, #1 ) = ( #2, #3, #2)
Ou seja, cada transição pode ser vista simplesmente como uma seqüência de cinco números: #1, #1, #2, #3, #2. O desafio, agora, é representar cada seqüência dessas como uma cadeia de 0’s e 1‘s. Mas como fazer isso?
É mais simples do que parece. Podemos simplesmente “contar” cada número usando repetidos 0’s. Por exemplo, #3 seria representado como 000 e o número #2 como 00. Para separar os cinco “números” da transição, colocamos símbolos 1 entre eles. Assim, a transição dada antes seria representada com a cadeia 0101001000100. Cada subcadeia de 0’s está associada a um dos números da transição como indica a figura abaixo:
De forma geral, cada transição δ( #m, #n ) = ( #o, #p, #q) será representada por uma cadeia na forma (0#m
)1(0#n)1(0#p)1(0#q), onde os parênteses são apenas para agrupamento (não são parte da cadeia).
As transições de δ devem ser todas convertidas da maneira explicada. Isso irá gerar várias cadeias, que deverão ser concatenadas para formar uma só cadeia. Porém, para permitir identificar cada transição individualmente, usaremos uma subcadeia 11 para separar as transições entre si. Pronto, depois disso, a cadeia final produzida será a representação final da máquina de Turing!
Como exemplo, vamos usar a máquina T dada abaixo parar criar a cadeia <T> que a representa. Vamos considerar que o seu alfabeto de entrada é {0,1} e o seu alfabeto de fita é {0,1, ,K}:
Veja que essa máquina de Turing possui as seguintes transições:
δ( qA, 0 ) = ( qB, 0, D )
δ( qB, 1 ) = ( qB, K, D )
δ( qB, ) = ( qC, K, E )
Como explicamos antes, qA, por ser estado inicial, deverá ser representado pelo número #1 e qC, por ser estado de aceitação, pelo número #2. O estado qB poderia ser representado por qualquer outro número, mas escolheremos o número #3. Quanto aos símbolos, lembre-se que 0 é representado por #1, 1 é representado por #2 e é representado por #3, obrigatoriamente. O símbolo K poderia ser representado por qualquer outro número, mas usaremos #4.
Assim, as transições acima podem ser representadas pelas seguintes cadeias:
010100010100
00010100010000100
00010001001000010
Separando essas cadeias por 11 e concatenando tudo, teremos a cadeia final que representa T:
Em geral, desejamos codificar uma máquina de Turing X e uma cadeia de entrada w para ela, tudo junto em uma só cadeia. Nos referimos a essa cadeia como <X, w>. A primeira parte dela é a codificação de X, que já vimos como fazer. A segunda parte é uma codificação da cadeia w em uma forma mais compatível com a codificação de X.
Vamos codificar cada símbolo de w usando os códigos de símbolos que vimos antes (segunda tabela). Os símbolos de w serão separados entre si por 1. Por exemplo, a cadeia 0100 ficaria na forma 01001010.
Agora, podemos concatenar <X> com 111 e, depois, com essa codificação da cadeia w (o trecho 111 serve para distinguir as duas partes). Por exemplo, a situação em que “a máquina T recebe a cadeia 0100” seria representada pela cadeia abaixo:
<T, 0100> = 0101000101001100010100010000100 110001000100100001011101001010
Uma codificação como essa pode ser dada como entrada para uma máquina de Turing qualquer – inclusive para a própria máquina T. Porém, o interesse aqui é usá-la como entrada em uma Máquina de Turing Universal (MTU) para que ela simule o comportamento de T quando T recebe w. Detalhes sobre isso você pode ver no capítulo 3.
Resumo
Neste fascículo, vimos dois novos modelos computacionais: Autômato com Pilha e Máquina de Turing. Em especial, vimos que o modelo Máquina de Turing, é o modelo computacional mais poderoso que existe. Ou seja, ele é o modelo capaz de decidir mais linguagens e, também, de decidir mais problemas. Até mesmo os computadores modernos que usamos são, no máximo, tão capazes quando as Máquinas de Turing.
Uma prova do poder das MTs é que podemos criar uma MT que pode ser “programada”, mais ou menos como os nossos computadores. Essa MT é chamada de máquina de Turing Universal e ela permite simular qualquer MT dada como entrada para ela.
Porém, o modelo MT também tem suas limitações: não podemos usar ele para reconhecer quando uma MT vai entrar em loop. Esse problema foi chamado de Problema da Parada e é apenas um exemplo de um problema indecidível, ou seja, que não pode ser decidido pela MT nem por qualquer computador imaginável. Existem diversos outros problemas indecidíveis. Alguns deles nós apenas citamos. Fica como sugestão de atividade complementar para os alunos interessados pesquisar detalhes de outros problemas indecidíveis.
Referências
HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à teoria de autômatos, linguagens e computação. Rio de Janeiro: Campus, c2003. 560 p. ISBN 8535210725
MENEZES, Paulo Fernando Blauth. Linguagens formais e autômatos. 4. ed. Porto Alegre: Sagra Luzzatto, 2002. 165p. ISBN 8524105542
SIPSER, Michael. Introdução à teoria da computação. [São Paulo]: Thomson Learning, 2007. 460 p. ISBN 9788522104994.