AULA 14 - MAQUINAS DE TURING (CAPITULO 9) ========================================= Comparacao com computadores: --------------------------- ==> um modelo matematico simples de um computador Semelhancas: le e escreve em posicoes arbitrarias de memoria Diferencas: sem limite no tamanho de memoria ==> define uma classe de linguagens (conjuntos recursivamente enumeraveis - a maquina para se a palavra pertence a linguagem, porem pode entrar em loop caso contrario) ==> define uma classe de funcoes que ele computa (funcoes parcialmente recursivas - dada a entrada para a funcao, a maquina pode ou nao parar) ==> formalizacao aceita de um procedimento efetivo (que pode ser resolvido algoritmicamente) Exemplos de problemas para os quais nao existe algoritmos: - Ideia: existem mais problemas que algoritmos - determinar se o complemento de uma CFL e' vazia (nao e' possivel determinar se uma gramatica arbitraria gera Sigma*) Um modelo formal de um procedimento efetivo de ter: 1) descricao finita 2) o procedimento deve ser composto de passos discretos que podem ser executados mecanicamente Hipotese de Church/Turing: existe um procedimento efetivo para solucionar um problema se e somente se existir uma maquina de Turing que pare para todas as entradas possiveis e que resolva o problema. Exemplo: {0^n 1^n | n > 0} Ideia: 1) troca o primeiro 0 por X 2) move a direita (pulando 0's e Y's) ate' achar o primeiro 1 3) Se encontrar, troca 1 por Y se nao encontrar (achar B ao inves de 1) rejeita a palavra 4) volta a esquerda (pulando Y's e 0's) ate' achar o X 5) se a direita existe um 0, voltar a 1 se a direita existe um Y (acabaram os 0's), ir ate' o final verificar se ainda existem 1's. Se existir rejeita, senao aceita. Cada posicao da fita contem um simbolo. Existe uma posicao mais a esquerda, mas a fita e' infinita a direita. Note que em um passo a maquina, dependendo do simbolo de entrada e o estado atual pode: 1) mudar de estado 2) escrever um simbolo na fita (por cima do simbolo lido) 3) mover a cabeca de leitura para a direita ou esquerda Formalmente: Def: uma maquina de Turing é uma tupla de 7 elementos M=(Q, Sigma, Gama, delta, q0, B, F), onde Q e' um conjunto finito de estados Gama e' um conjunto finito de simbolos da fita B, um simbolo em Gama, e' o branco Sigma subconjunto de Gama e' o conjunto de simbolos de entrada delta e' um funcao de QxGama para QxGamax{L,R} q0 em Q e' o estado inicial F subconjunto de Q e' o conjunto de estados finais. Def: a DESCRICAO INSTANTANEA de uma maquina M e' descrita por A1 q A2, onde q e' o estado atual e A1 e A2 sao strings em Gama*, que e' o conteudo da fita do inicio da fita ate' o simbolo nao Branco mais a direita. O simbolo sendo lido e' o simbolo mais a esquerda de A2. Def: a relacao |- (resulta) para uma maquina de Turing M e' definida por: 1) X1 X2 ... Xi-1 q Xi ... Xn |- X1 X2 .. Xi-2 p Xi-1 Y Xi+1 ... Xn se delta(q,Xi) = (p, Y, L). . se Xi-1 = n (ou seja, Xi...Xn e' uma sequencia de B) entao Xi = B . se i = 1 entao a computacao aborta, pois a cabeca da fita nao pode se mover mais para a esquerda 2) X1 X2 ... Xi-1 q Xi ... Xn |- X1 X2 .. Xi-1 Y p Xi+1 ... Xn se delta(q, Xi) = (p, Y, R) |-* e' o fecho transitivo e reflexivo de |- Def: A linguagem ACEITA por uma maquina de Turing M=(Q, Sigma, Gama, delta,q0, B, F) e' definido por: {w em Sigma* | q0 w |-* A1 p bA2 para algum p em F, A1 e A2 em Gama* e b em Gama tal que delta(p,b) e' indefinido} assumindo que se w pertence a linguagem a maquina para; porem, se w nao pertence a linguagem a maquina pode entrar em loop. Exemplo da computacao de 0011 na maquina acima: q0 0011 |- X q1 011 |- X0 q1 11 |- X q2 0Y1 |- q2 X0Y1 |- X q0 0Y1 |- XX q1 Y1 |- XXY q1 1 |- XX q2 YY |- X q2 XYY |- XX q0 YY |- XXY q3 Y |- XXYY q3 |- XXYYBq4 Exemplo de diferentes tipos de nao aceitacao: L = {a,b,c}* - {ab}{a,b,c}* (todas as palavras que nao comecam com ab): 1) para sempre se w em L ou nao. Se w comeca com ab, nem e' preciso processar a palavra inteira. a/a, R b/b, L ((q0)) --------> ((q1)) --------> (q2) 2) so' para se w em L a/a, R ((q0)) --------> ((q1)) <------- b/b, L Exemplo de utilizacao da M.T para computar funcoes: -------------------------------------------------- Subtracao: m - n igual a: m - n se m >= n 0 se m < n representacao de m e n: qualquer numero i pode ser representado por 0^i, portanto podemos representar m e n por: 0^m 1 0^n, usando 1 como o separador de numeros resultado: se m>=n no final da computacao a fita deve conter m-n 0's se m< n no final da computacao a fita deve conter apenas B's Note que neste exemplo nao existe estado final -- a maquina sempre para quando o resultado esta' na fita. Ideia: 1) troca o primeiro 0 por B e procura a direita pelo primeiro 0 depois do 1. Troca este 0 por 1 e volta a esquerda ate' encontrar um B. Repete. 2) a maquina para se: . procurando o primeiro 0 depois do 1, encontra um B -> quer dizer que os n 0's ja' foram transformados em 1's. como o primeiro 0 ja' foi transformado em B, voltar, transformando os n 1's em brancos e quando encontrar um B (no inicio da fita), transforma-lo de volta em 0. . no inicio do ciclo, ao inves de encontrar um 0, encontra um 1 -> quer dizer que m <= n. Entao transformar todos os 0's e 1's em B's. Exemplo da computacao de 0010: q0 0010 |- B q1 010 |- B0 q1 10 |- B01 q2 0 |- B0 q3 11 |- B q3 011 |- q3 B011 |- B q0 011 |- BB q1 11 |- BB1 q2 1 |- BB11 q2 |- BB1 q4 1 |- BBq4 1 |- Bq4 |- B0 q6 TECNICAS DE CONSTRUCAO DE MAQUINAS DE TURING -------------------------------------------- Sao tecnicas de "alto nivel" para a construcao de maquinas de Turing. 1) ARMAZENAMENTO DE DADOS NOS ESTADOS cada estado e' um par [estado,dado1,..., dado_n]. Note que nada na maquina e' alterado. Isto e' so' uma tecnica para auxiliar no projeto da M.T, simplesmente usando um nome "significativo" para cada estado. Exemplo: {w em {0,1}* | o primeiro simbolo de w nao aparece mais no restante da palavra} 2) FITA COM MULTIPLAS TRILHAS Podemos imaginar que a fita de uma TM e' dividida em k trilhas, para um numero finito k. Ex: +---+---+---+---+---+---+---+---+---+---+---- | # | 1 | 0 | 1 | 1 | 1 | 1 | $ | B | B | ... trilha 1 +---+---+---+---+---+---+---+---+---+---+---- | B | 1 | 0 | 0 | 1 | 0 | 1 | B | B | B | ... trilha 2 +---+---+---+---+---+---+---+---+---+---+---- | B | B | B | B | 1 | 0 | 1 | B | B | B | ... trilha 3 +---+---+---+---+---+---+---+---+---+---+---- Decidir se um numero n representado em binario na trilha 1 da fita e' primo. - O numero inicia com o simbolo # e termina com o simbolo $. - No inicio do processamento, as duas outras trilhas estao brancas, ou seja, os valores de entrada sao: [#,B,B], [0,B,B], [1,B,B], [$,B,B]. Ideia: 1) colocar o numero 2 em binario na trilha 3 2) repetir se trilha 1 = trilha 3 entao o numero e' primo senao copiar trilha1 na trilha 2 repetir trilha2 - trilha3 ate' que trilha2 < trilha 3 se trilha 2 = 0 entao nao e' primo senao somar 1 na trilha 3 3) CHECAR SIMBOLOS PROCESSADOS Podemos utilizar uma segunda trilha na fita de entrada para marcar quais os simbolos de entrada ja' processados sem destruir a entrada para a maquina. E' util para reconhecer linguagens definidas por 1) repeticao de strings: Ex: {ww | w em {0,1}*} {wcy | w e y em {0,1}* e w not= y} {ww^R | w em {0,1}*} 2) comparacao de tamanho: Ex: {a^i b^i | i >= 1} {a^i b^j c^k | i not= j ou j not= k} Exemplo: {wcw | w em {a,b}+} - os estados sao pares [q,d], onde d guarda o simbolo sendo processado (a,b,B) - a fita tem duas trilhas: uma com a palavra a outra o simbolo V (checado) ou B, ou seja, cada entrada da fita e' [X,d], onde X pode ser B ou V (checado) e d pode ser B, a, b, ou c Ideia: . checar o simbolo de entrada d corrente . mover a direita ate' passar o c e todos os simbolos checados depois dele . se o primeiro simbolo nao checado for igual a d entao volta a esquerda ate' encontrar a proxima entrada nao checada senao erro 4) MOVER O CONTEUDO DA FITA N CELULAS PARA DIREITA OU ESQUERDA Exemplo: mover o conteudo da fita 2 celulas a direita. M=(Q, Sigma, Gama, delta, q0, B, F), onde cada estado em Q e' da forma [q,A1,A2], A1 e A2 em Gama e X e' um simbolo especial em Gama usado somente para fazer o "shift". - A1 guarda o simbolo lido duas celulas antes da celula corrente - A2 guarda o simbolo lido uma celula antes da corrente Ideia: +---+---+---+---+---+---+---+---+---- | 0 | 1 | 1 | 0 | 0 | B | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,B,B] +---+---+---+---+---+---+---+---+---- | X | 1 | 1 | 0 | 0 | B | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,B,0] +---+---+---+---+---+---+---+---+---- | X | X | 1 | 0 | 0 | B | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,0,1] +---+---+---+---+---+---+---+---+---- | X | X | 0 | 0 | 0 | B | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,1,1] +---+---+---+---+---+---+---+---+---- | X | X | 0 | 1 | 0 | B | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,1,0] +---+---+---+---+---+---+---+---+---- | X | X | 0 | 1 | 1 | B | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,0,0] +---+---+---+---+---+---+---+---+---- | X | X | 0 | 1 | 1 | 0 | B | B | .... +---+---+---+---+---+---+---+---+---- ^ [q1,0,B] +---+---+---+---+---+---+---+---+---- | X | X | 0 | 1 | 1 | 0 | 0 | B | .... +---+---+---+---+---+---+---+---+---- ^ [q2,B,B] 5) SUBROTINAS Assim como podemos construir programas modulares, podemos tambem construir TM de forma modular. Uma TM pode simular todos os tipos de subrotina encontrados em linguagens de programacao, inclusive procedimentos recursivos e os diversos tipos de passagem de parametros (isso vai ficar mais claro quando mostrarmos como uma TM pode simular uma maquina RAM). Cada subrotina tem um estado inicial e um estado de retorno, que temporariamente nao tem nenhuma transicao e que sera' usado como retorno de um procedimento. Exemplo: multiplicacao 0^m 1 0^n -- efetuar a multiplicacao m*n e no final a fita deve conter 0^{m*n} Ideia: 1) colocar 1 no final de 0^m 1 0^n 2) copiar um bloco de n 0's a direita m vezes, cada vez removendo um dos m 0's. O resultado sera' B^m 1 0^n 1 0^{m*n} 3) trocar 1 0^n 1 por B's Subrotinas: copia: copia um bloco de n 0's uma vez 0^m 1 q1 0^n 1 0^i ==> 0^m 1 q5 0^n 1 0^{i+n} inicio: troca um dos m 0's por B e chama copia q0 0^m 1 0^n 1 ==> B 0^{m-1} 1 q1 0^n 1 retorno ao inicio (depois da copia): B^i 0^{m-i} 1 q5 0^n 1 0^{n*i} ==> B^i q0 0^{m-i} 1 0^n 1 0^{n*i} resultado (remove 10^n1): B^m 1 q5 0^n 1 0^{m*n} ==> B^m B B^n B q12 0^{m*n} preparacao inicial: q13 0^m 1 0^n ==> q0 0^m 1 0^n 1