Upload
blaze
View
50
Download
0
Embed Size (px)
DESCRIPTION
Computabilidade e Linguagens Formais. Máquinas de Turing. Gabriel David / Cristina Ribeiro. Hello, world. main() { printf( ″ hello, world\n ″ ); } Qual a saída deste programa?. Hello, world de novo. int exp(int i, n) /* calcula i^n */ { int ans, j; ans = 1; - PowerPoint PPT Presentation
Citation preview
1
Computabilidade e Linguagens Formais
Máquinas de Turing
Gabriel David / Cristina Ribeiro
Máquinas de Turing -2
Hello, world
main()
{
printf(″hello, world\n″);
} Qual a saída deste programa?
Máquinas de Turing -3
Hello, world de novo
main(){
int n, total, x, y, z;scanf(″%d″, &n);total = 3;while(1){
for (x=1; x<=total-2; x++) for (y=1; y<=total-x-1; y++){ z = total-x-y; if (exp(x,n) + exp(y,n) == exp(z,n)) printf(″hello, world\n″);
}total++;
}}
Qual a saída deste programa? Para entrada 2? E 3?
int exp(int i, n)/* calcula i^n */{
int ans, j;ans = 1;for (j=1; j<=n; j++) ans *= i;return(ans);
}
xn + yn = zn
– Último teorema de Fermat Levou 300 anos a provar que é
impossível para n3
Máquinas de Turing -4
Devem existir problemas indecidíveis
Problema é decidir se uma cadeia pertence a uma linguagem O número de linguagens diferentes sobre um alfabeto com
mais do que um símbolo não é numerável– Não é possível estabelecer uma correspondência biunívoca com
Os programas são numeráveis– Cadeias finitas sobre alfabetos finitos– Ordenar por comprimento e por ordem lexicográfica– Podem ser contados, embora em número infinito
Há infinitamente menos programas do que problemas– Linguagem ao acaso dá provavelmente um problema indecidível– A maioria dos problemas parecem decidíveis porque são escolhidos
Máquinas de Turing -5
Teste do “Hello, world”
Hipótese– Existe um programa H que recebe
como entrada um programa P e uma entrada I e imprime yes se P com entrada I imprimir hello, world e no no caso contrário; e faz sempre uma coisa ou outra
Um problema que tenha um algoritmo como H é decidível
– Senão é indecidível Vamos provar que H não existe
– Seria estranho que um programa resolvesse o último teorema de Fermat
HPI
yesno
Máquinas de Turing -6
Prova por contradição
Simplificação na classe de programas P
– Só programas em C com saída em caracteres e que só usam printf()
Modificar H– As modificações não põem em causa
a existência de H– Modificar printf() de forma a que
quando devesse imprimir no, passe a imprimir hello, world
– Obtém-se H1
H1PI
yeshello, world
Máquinas de Turing -7
Prova por contradição
Interesse em programas que processam programas
Restringir H1
– Só tem entrada P– Pergunta o que faz P quando recebe P
como entrada
H2 é modificação de H1
– H2 começa por ler P para um array com malloc()
– H2 simula H1 substituindo leituras de P e de I por leituras do array
O que faz H2 quando é dado como entrada a ele próprio?
H2Pyeshello, world
H2H2
yeshello, world
Máquinas de Turing -8
H2 não pode existir
H2, dado P– Imprime yes se P imprimir hello, world com entrada P– Imprime hello, world se P, com entrada P, não imprimir hello, world
Dando H2 a H2– Se imprimir yes diz que H2 com entrada H2 imprime hello, world
Mas acaba-se de assumir que H2 com entrada H2 imprime yes
– Se imprimir hello, world (tem que ser uma ou outra das possibilidades) então a saída da caixa tem que ser yes
Contradição também
Portanto H2 não pode existir nem H1 nem H– O problema do hello, world é indecidível
Máquinas de Turing -9
Redução de problemas
Outros problemas– Para testar a indecidibilidade pode-se construir um programa
paradoxal, semelhante a H2
– Alternativa: reduzir o problema indecidível ao novo problema; se conseguisse decidir o novo, também decidia o antigo; como o antigo é indecidível, o novo também é
Questão: saber se se consegue reduzir o antigo ao novo Nota: reduzir o novo ao antigo não resolve porque daria
Decidível(antigo) Decidível(novo), mas o antecedente é falso
Decideyes ou no conforme asua entrada instância do
problema P2 está ou nãona linguagem do problema
Constrói DecideP1 P2yes
no
Máquinas de Turing -10
Fase de construção
A construção tem que reduzir cada instância de P1 (cadeia w) a uma instância de P2 (cadeia x) com a mesma resposta
– Qualquer cadeia no alfabeto de P1 que não pertence à linguagem de P1 tem que ser convertida para uma cadeia que não está na linguagem de P2
– Assim, se w está em P1, x está em P2 e Decide diz yes; se w não está em P1, x não está em P2 e Decide diz no; fala verdade sobre w
Máquinas de Turing -11
Exemplo de redução Problema
– Programa Q, com entrada y, chama a função foo?– Se Q não tiver a função foo é fácil– P1 é o problema hello, world e P2 é o problema chama-foo– Dado um programa Q com entrada y construir um programa R com
entrada z que chame foo se e só se Q com entrada y imprimir hello, world Construção
– Se Q tiver foo, renomeá-la e a todas as suas chamadas– Adicionar uma função foo vazia e que não é chamada– Memorizar no array A os primeiros 12 caracteres da saída– Sempre que o programa escrever para a saída, verifica em A se está lá
hello, world e, nesse caso, chama foo– O programa modificado é R; a entrada z é igual a y
Se fosse possível decidir R também seria possível decidir Q
Máquinas de Turing -12
Motivação
Problemas indecidíveis– Não existe algoritmo
Problemas intratáveis– Os algoritmos conhecidos são demasiado dispendiosos– Simplificação; heurísticas
Necessidade de um modelo simples de computador para estudar a computabilidade
– Máquinas de Turing– Modelo de computador, mais do que de linguagem
Máquinas de Turing -13
Contexto
David Hilbert (início do séc. XX)– Há alguma maneira de determinar se qualquer fórmula da lógica de
predicados de primeira ordem, aplicada aos inteiros, é verdadeira? Kurt Gödel (1931)
– Teorema da incompletude: construiu uma fórmula que não pode ser provada nem refutada
– Técnica semelhante ao programa contraditório H2
Alan Turing (1936)– Máquina de Turing: modelo de qualquer computação possível– Veio a estar envolvido, durante a 2ª Guerra, no esforço de construção de
máquinas de que emergiram os computadores Hipótese de Church (tese de Church-Turing, não demonstrável)
– Todos os modelos gerais de computação são equivalentes às funções parciais recursivas e às máquinas de Turing (mesmo os computadores actuais)
Máquinas de Turing -14
Máquina de Turing
Controlo finito– Número finito de estados
Fita de comprimento infinito dividida em células– Cada célula pode conter um símbolo (alfabeto finito)
Entrada– Cadeia finita constituída por símbolos do alfabeto de entrada– Colocada na fita no início; resto da fita preenchido com brancos (B)
Símbolos da fita– Alfabeto de entrada + branco + possivelmente outros símbolos
B B X1 X2 Xi BBXn… …
Controlo
Máquinas de Turing -15
Máquina de Turing
Cabeça da fita– Sempre posicionada numa célula– No início, está na célula mais à esquerda da entrada
Movimento ou passo da máquina– função do estado do controlo e do símbolo a ser varrido pela cabeça– 1. Mudança de estado
Pode ser o mesmo
– 2. Escrita de um símbolo na célula onde está a cabeça Pode ser o mesmo
– 3. Deslocação da cabeça de uma célula à esquerda ou à direita Não restringe: sequência de passos com a cabeça parada seguida de um
com movimento pode ser resumida neste
Máquinas de Turing -16
Formalização
Semelhante a autómatos de pilha Máquina de Turing (TM) M= (Q, , , , q0, B, F)
– Q: conjunto finito de estados do controlo : conjunto finito de símbolos de entrada : conjunto finito de símbolos da fita : função de transição (q, X) = (p,Y,D)
q é um estado, X um símbolo da fita p é o novo estado, em Q; Y é o símbolo em que substitui X; D é L ou R, esquerda ou direita, direcção em que a cabeça se move depois da substituição
– q0: estado inicial
– B: branco, símbolo que preenche a fita, excepto as células com a entrada– F: conjunto de estados de aceitação ou finais
Máquinas de Turing -17
Computação
Descrição instantânea– X1X2…Xi-1qXiXi+1…Xn
– Células desde a primeira à última não brancas (nº finito) Mais um prefixo ou sufixo finito com brancas até à cabeça
– O estado (q) e a célula (i) onde a cabeça está
Passo da máquina de Turing M (├M;├*M – 0 ou mais passos)– Supondo (q,Xi) = (p,Y,L)
– X1X2…Xi-1qXiXi+1…Xn ├M X1X2…Xi-2pXi-1YXi+1…Xn
Estado q passa a p; célula Xi passa a Y; cabeça anda para a esquerda
Se i=1: qX1X2…Xn ├ pBYX2…Xn
Se i=n e Y=B: X1X2…Xn-1qXn ├ X1X2…Xn-2pXn-1
Simétrico para (q,Xi) = (p,Y,R)
Máquinas de Turing -18
Exemplo 0n1n
TM para aceitar a linguagem {0n1n | n1} Ideia
– Fita no início contém 0’s e 1’s– Mudar o primeiro 0 para X; deslocar para a direita até ao primeiro 1
e mudá-lo para Y; deslocar para a esquerda até ao primeiro X; deslocar um para a direita; recomeçar
– Se num estado aparecer algum símbolo não previsto, a TM morre Se a entrada não for 0*1*
– Se na iteração em que marca o último 0 também marca o último 1 então aceita
Máquinas de Turing -19
Exemplo 0n1n
– M = ({q0,q1,q2,q3,q4), {0,1}, {0,1,X,Y,B}, , q0, B, {q4}) q0: muda 0 para X q1: desloca-se para a direita até ao primeiro 1 que muda para Y q2: desloca-se para a esquerda até encontrar um X e volta a q0
Se tiver um 0 reinicia o ciclo; se tiver um Y vai para a direita; se encontrar um branco vai para q4 e aceita; senão morre sem aceitar
Estado 0 1 X Y B
q0 (q1,X,R) (q3,Y,R)
q1 (q1,0,R) (q2,Y,L) (q1,Y,R)
q2 (q2,0,L) (q0,X,R) (q2,Y,L)
q3 (q3,Y,R) (q4,B,R)
q4
Máquinas de Turing -20
Computações no exemplo
Entrada 0011– Descrição instantânea inicial q00011
q00011 ├ Xq1011 ├ X0q111 ├ Xq20Y1 ├ q2X0Y1 ├
Xq00Y1 ├ XXq1Y1 ├ XXYq11 ├ XXq2YY ├ Xq2XYY ├
XXq0YY ├ XXYq3Y ├ XXYYq3B ├ XXYYBq4B– aceita
Entrada 0010 q00010 ├ Xq1010 ├ X0q110 ├ Xq20Y0 ├ q2X0Y0 ├
Xq00Y0 ├ XXq1Y0 ├ XXYq10 ├ XXY0q1B– morre
Máquinas de Turing -21
Diagramas de transição
Semelhante a autómato de pilha– Nós são estados da TM– Arco do estado q para o estado p com etiquetas X/YD
(q,X) = (p,Y,D), X e Y são símbolos da fita e D é L ou R
– Start é estado inicial; circunferência dupla, estados finais; B, branco
Start q0 q1
0/X q2
Y/Y 0/0
q3 q4
1/Y
Y/Y 0/0
X/X Y/Y
B/B
Y/Y
Máquinas de Turing -22
Exemplo Diagrama de transição para uma TM que aceite a linguagem
das cadeias com número igual de 0 e 1.
Start q0 q1
1/X q2
1/1 Y/Y
q3q4
1/Y
Y/Y 0/0
B/B X/X
0/X Y/Y
0/Y
0/0 1/1 Y/Y
• q00110 ├ Xq2110 ├ q3XY10 ├ Xq0Y10 ├ XYq010 ├ XYXq10 ├ XYq3XY ├ XYXq0Y ├ XYXYq0B ├ XYXYBq4B
• q0110 ├ Xq110 ├ X1q10 ├ Xq31Y ├ q3X1Y ├ Xq01Y ├ XXq1Y ├ XXYq1B
Máquinas de Turing -23
Linguagem de uma TM Cadeia de entrada colocada na fita
– Cabeça no símbolo mais à esquerda
Se a máquina entrar num estado de aceitação, a cadeia é aceite Linguagem da TM M= (Q, , , , q0, B, F)
– Conjunto das cadeias w em * tais que q0w ├* p e p F
– Linguagens recursivamente enumeráveis
Linguagens recursivamente enumeráveis
Linguagens sem contexto (CFL)
Linguagens regulares(RL)DFA (NFA, -NFA), RE
PDA, CFG
TM
Linguagens
Máquinas de Turing -24
Paragem
Uma TM pára se entrar num estado q a ler um símbolo X e (q,X) não estiver definida
– Permite encarar a máquina de Turing como executando uma computação, com princípio e fim
exemplo: calcular a diferença de dois inteiros q00m10n ├* 0m-nqf
– TM que param sempre, aceitem ou não a entrada, constituem modelos de algoritmos (linguagens recursivas)
Pode-se assumir que uma TM pára sempre que aceita Infelizmente não é sempre possível exigir que uma TM pare
quando não aceita– Indecidibilidade (linguagens recursivamente enumeráveis)– Possibilidade de uma TM se referir a si própria (poder para ser
indecidível)
Máquinas de Turing -25
Técnicas de programação de TM
Uma TM tem o mesmo poder computacional que os computadores actuais
Memória no estado– Estado = controlo + memória de dados– Ver o estado como um tuplo
Pistas múltiplas– Fita composta por várias pistas; um símbolo em cada pista– Alfabeto da fita constituída por tuplos
Poder das TM permanece inalterado
Máquinas de Turing -26
Subrotinas
Uma TM é um conjunto de estados que executa um processo– Tem uma entrada e estados finais
Encarada como subrotina de uma TM principal– Chamada vai para estado principal– Não existe noção de endereço de retorno– Se uma subrotina for chamada de vários estados diferentes, faz-se
cópias (macro) para retornar ao estado que chamou
Máquinas de Turing -27
Extensões
TM com várias fitas– Cada qual tem a sua cabeça– Entrada só na primeira fita– Movimento: esquerda, direita e estacionário– Equivalente a uma fita
Complexidade temporal quadrática
TM não deterministas– Função de transição dá conjunto de tuplos (q,Y,D)– Equivalente a determinista
Codificar na fita uma fila com as descrições instantâneas a processar Simular o não determinista percorrendo-as em largura
Máquinas de Turing -28
Restrições
TM com fitas semi-infinitas Máquinas com várias pilhas Máquinas com contadores Comparação com computadores