AULA 15: MAQUINAS DE TURING (continuacao) ========================================= MODIFICACOES NA MAQUINA QUE MANTEM O MESMO PODER COMPUTACIONAL: 0) Maquina com cabecote imovel --------------------------- Permite-se que o cabecote possa ficar imovel em uma transicao: A funcao delta e' entao: QxGama -> QxGamax{L,R,S} S (stay) Exemplo: posicional o cabecote no final de uma palavra em {a,b}* B/B,L b/b,L B/B,S B/B,R a/a,L --> q0 -------> q1 --> q0---------> q1 ----------> q2 | | | | +-+ +-+ a/a,R a/a,R b/b,R b/b,R 1) Fita infinita nos dois sentidos ------------------------------- M2 = (Q2, Sigma2, Gama2, delta2, q2, B, F2): -----+-----+-----+-----+-----+-----+-----+-----+-----+----- ... | A-3 | A-2 | A-1 | A0 | A1 | A2 | A3 | A4 | .... -----+-----+-----+-----+-----+-----+-----+-----+-----+----- Pode ser simulada por uma MT simples usando uma fita com duas trilhas e infinita somente a direita: M1 = (Q1, Sigma1, Gama1, delta1, q1, B, F1): +-----+-----+-----+-----+----- | A0 | A1 | A2 | A3 | ... +-----+-----+-----+-----+----- | < | A-1 | A-2 | A-3 | ... +-----+-----+-----+-----+----- onde Q1 = {[q,U], [q,D] | q em Q2} uniao {q1} U (up) leva em conta somente a trilha de cima da fita D (down) leva em conta somente a trilha de baixo da fita Gama1 = {[x1, x2] | x1, x2 em Gama2 uniao {<} } Sigma1 = {[a,B] | a em Sigma2} F1 = {[q,U], [q,D] | q em F2} delta1 e' definido por: a) para as transicoes do estado inicial para a direita: se delta2(q2,a)=(q,X,R) entao delta1(q1,[a,B]) = ([q,U],[X,<],R) b) para as transicoes do estado inicial para a esquerda: se delta2(q2,a)=(q,X,L) entao delta1(q1,[a,B]) = ([q,D],[X,<],R) c) para as transicoes que leem '<' (chega no inicio da fita): se delta2(q,X) =(p,Y,A) entao delta1([q,U],[X,<]) = delta1([q,D],[X,<]) = ([p,C],[Y,<],R), onde C=U se A=R e C=D se A=L d) M1 simula M2 na trilha de cima. Seja Y not= '<', A= L ou R se delta2(q,X)=(p,Z,A) entao delta1([q,U],[X,Y],A)=([p,U],[Z,Y],A) e) M1 simula M2 na trilha de baixo. Em M1, todo movimento e' contrario ao movimento em M2: se delta2(q,X)=(p,Z,A) entao delta1([q,D],[X,Y],A)=([p,D],[X,Z], inverso(A)) 2) Multiplas Fitas --------------- A maquina tem multiplas fitas, cada uma com seu proprio cabecote de leitura/escrita (que sao operados independentemente). A funcao de transicao de uma MT M=(Q, Sigma, Gama, B, delta, q0, F) e' delta: QxGama^k -> Qx(Gamax{L,R,S})^k. Inicialmente, a fita contem '<' seguido de uma palavra em Sigma* e as demais fitas sao todas brancas, com o cabecote na segunda posicao em todas as fitas: +-----+-----+-----+-----+----- fita 1 | < | a | a | b | ... +-----+-----+-----+-----+----- ^ +-----+-----+-----+-----+----- fita 2 | B | B | B | B | ... +-----+-----+-----+-----+----- ... ^ +-----+-----+-----+-----+----- fita n | B | B | B | B | ... +-----+-----+-----+-----+----- ^ Exemplo: maquina de duas fitas para {w w^R w | w em {0,1}^*} Ideia: 1) para cada 3 simbolos na fita 1 (com a palavra) escreve um X na fita 2. fita 1: < abb bba abb ^ fita 2: B XXX ^ 2) volta copiando o ultimo terco da palavra na fita 2 (troca X por 0 ou 1): fita 1: < abb bba abb ^ fita 2: B abb ^ 3) verifica se fita 1 (da direita para esquerda e' igual a fita 2 da esquerda para direita) fita 1: < abb bba abb ^ fita 2: B abb ^ 4) verifica se fita 1 (da direita para esquerda e' igual a fita 2 da direita para esquerda) fita 1: < abb bba abb ^ fita 2: B abb ^ Como simular esta maquina numa MT padrao: Dada uma maquina de duas fitas M=(Q,Sigma,Gama,delta,B,q0,F), construir uma MT com 4 trilhas. A trilha 1 contera' a palavra da fita 1, a trilha 2 marca com um 'X' qual a posicao do cabecote da fita 1; a trilha 3 contera' os simbolos da fita 2 e a trilha 4 marca com um 'X' a posicao do cabecote da fita 2. Ideia geral: a maquina faz uma passada da esquerda para a direita para ----------- obter quais os simbolos nas trilhas 1 e 3 que estao marcados com 'X'. Depois faz uma passada da direita para a esquerda, escrevendo nas trilhas 1 e 3 e alterando a posicao do cabecote nas trilhas 2 e 4. Assim, os estados em M' sao da forma [e,a1a2b1b2d1d2], onde a1: simbolo sendo lido pelo cabecote da fita 1 a2: simbolo sendo lido pelo cabecote da fita 2 b1: simbolo a ser escrito pelo cabecote da fita 1 b2: simbolo a ser escrito pelo cabecote da fita 2 d1: direcao a mover o cabecote da fita 1 d2: direcao a mover o cabecote da fita 2 Cada um destes itens pode ter o valor _ se ele ainda nao e' conhecido. M' tera' um novo estado inicial que chamaremos de q0'. Inicialmente, a maquina contem < e a palavra a ser reconhecida na trilha 1 e as demais trilhas em B. O cabecote esta' no primeiro simbolo da palavra. 1) escrever 'X' na posicao 2 das trilhas 2 e 4: s1 e' qualquer simbolo em Sigma [s1,B,B,B]/[s1,X,B,X], S q0' ---------------------------> [q0,______] 2) para cada estado q em Q: - busca os simbolos a1 e a2 marcados com 'X' Caso 1: encontra o cabecote da fita 1 primeiro: [a1,X,s2,B]/[s1,X,s2,B],R [e,______] --------------------------> [e,a1_____] [s1,B,s2,B]/[s1,B,s2,B],R [e,a1_____] --------------------------> [e,a1_____] [s1,B,a2,X]/[s1,B,a2,X],S [e,a1_____] --------------------------> [e,a1a2____] Caso 2: encontra o cabecote da fita 2 primeiro: similar ao caso 1 Caso 3: encontra os dois cabecotes juntos: [a1,X,a2,X]/[a1,X,a2,X],S [e,______] --------------------------> [e,a1a2____] - se delta(e,a1,a2) = (e',b1,d1; b2,d2) entao volta da direita para a esquerda escrevendo b1 em cima de a1 na trilha 1 e movendo o 'X' para a direcao d1 na trilha 2, escrevendo b2 em cima de a2 na trilha 3 e movendo o 'X' na direcao d2 na trilha 4. Caso 1: se o cabecote estiver na posicao do 'X' da trilha 2: - troca a1 por b1 e move 'X' para d1 [a1,X,s2,B]/[b1,B,s2,B],d1 [e,a1a2____] ---------------------------> [e,a1a2b1___] __ [s1,B,s2,x2]/s1,X,s2,x2],d1 [e,a1a2b1___] ---------------------------> [e,a1a2b1d1__] - procura 'X' da trilha4, troca a2 por b2 e move 'X' para d2 [s1,x1,s2,B]/[s1,x1,s2,B],L [e,a1a2b1d1__] ----------------------------> [e,a1a2b1d1__] [s1,x1,a2,X]/[s1,x1,b2,B],d2 [e,a1a2b1d1__] ----------------------------> [e,a1a2b1d1b2_] [s1,x1,s2,B]/[b1,B,s2,X],L [e,a1a2b1d1b2_] ---------------------------> [e,a1a2b1d1b2d2] Caso 2: se o cabecote estiver na posicao 'X' da trilh 4: similar ao Caso 1. - volta para o inicio da fita e vai para o estado e' [s1,x1,s2,x2]/[s1,x1,s2,x2],L [e,a1a2b1b2d1d2] -------------------------------> [e,a1a2b1b2d1d2] [<,x1,s2,x2]/[<,x1,s2,x2],R [e,a1a2b1b2d1d2] -------------------------------> [e',______] 3) Nao determinismo ---------------- Em uma MT nao deterministica, para cada par (estado, simbolo) ha' mais de uma transicao possivel. Seja k o numero maximo de alternativas de um par (estado, simbolo) na maquina. Entao para cada estado e simbolo existem no maximo k alternativas possiveis (se houver menos, a mesma transicao pode ser repetida). Assim, uma computacao em n passos pode ser representada por uma sequencia de n numeros, cada um tendo valor no intervalo [1,k]. Exemplo: (Sudkamp) {w em {a,b,c}* | existe um 'c' precedido ou seguido de 'ab'} Estado Simbolo Transicao Estado Simbolo Transicao --------------------------- ------------------------ q1 a 1 q1,a,R q3 b 1 q4,b,R 2 q1,a,R 2 q4,b,R 3 q1,a,R 3 q4,b,R q1 b 1 q1,b,R q5 b 1 q6,b,L 2 q1,b,R 2 q6,b,L 3 q1,b,R 3 q6,b,L q1 c 1 q1,c,R q6 a 1 q7,a,L 2 q2,c,R 2 q7,a,L 3 q5,c,L 3 q7,a,L q2 a 1 q3,a,R 2 q3,a,R 3 q3,a,R Neste caso, k=3, e a computacao definida pela sequencia (1,2,1,1) e': q1 acabB 1 |- a q1 cabB 2 |- ac q2 abB 1 |- aca q3 bB 1 |- acab q4 B Note que agora cada transicao e' determinada por um numero entre 1 e k alem do par (estado, simbolo). Assim, uma MT nao deterministica pode ser simulada por uma MT deterministica de 3 fitas da seguinte forma: Fita 1: contem a palavra Fita 2: vai gerar sequencialmente os passos de uma computacao: primeiro gera todas as sequencias de tamanho 1, de tamanho 2, etc. Assim, se uma determinada alternativa "entrar em loop", isso nao impede que outras alternativas sejam analisadas Fita 3: uma copia da palavra e' colocada nesta fita para fazer a computacao segundo a sequencia da fita 2. Maquina que faz a geracao a sequencia de numeros entre 1 e k: Como simular maquinas RAM em uma MT =================================== Hipotese de Church: a classe de "funcoes computaveis" e' igual a classe ------------------ das funcoes recursivas (ou seja, para as quais existe uma M.T que pare para todas as entradas possiveis) Embora isso nao possa ser provado, podemos dar evidencias de que isso e' razoavel. 1) partindo do pressuposto que uma funcao e' computavel independente do numero de passos e quantidade de memoria, e' facil nos convencermos que tudo que uma MT faz pode ser computavel. 2) o que e' menos claro e' se tudo que e' computavel pode ser executado por um MT. Para nos convencermos disso, podemos mostrar como um MT simula um modelo de computador abstrato, chamado RAM. A RAM e' composto por uma memoria infinita, numerada 0, 1, ... Cada posicao de memoria pode conter um inteiro. A maquina possui tambem um conjunto finito de registradores aritmeticos, cada um podendo conter um inteiro. Com um conjunto de instrucoes adequado, a RAM pode simular qualquer computador existente. Simulacao de um RAM por uma MT: A simulacao pode ser feita por uma MT com multiplas fitas: - uma fita para a memoria: #0*v0 #1*v1 #2*v2 .... onde vi e' o conteudo da memoria na palavra de endereco i. - uma fita para cada registrador aritmetico - uma fita para o contador de instrucao - uma fita para o registrador de endereco da memoria (o endereco de memoria onde uma palavra deve ser lida ou armazenada) Exemplo de simulacao da instrucao: 1) suponha que o contador de instrucao contem o endereco i 2) procura a posicao de memoria #i a partir do inicio da fita 1. Se encontrar brancos, a maquina para. 3) se encontrar a posicao #i, examina a instrucao. Suponha que a instrucao esta' nos 10 primeiros bits da palavra e que ela contem "ADD no registrador 2 o conteudo do endereco j", onde o restante da palavra contem o endereco j. 4) soma 1 na fita do contador de instrucao 5) copia j na fita do registrador de endereco 6) procura o endereco #j na fita 1 comecando do inicio. 7) se nao encontrar o endereco, assume que o endereco contem zero e executa a proxima instrucao 7) se encontrar #j*vj, vj e' somado a fita do registrador 2