Computabilidade e Linguagens Formais

Máquinas de Turing
Gabriel David / Cristina Ribeiro
1
Hello, world
main()
{
printf(″hello, world\n″);
}

Qual a saída deste programa?
Máquinas de Turing -2
Hello, world de novo
int exp(int i, n)
/* calcula i^n */
{
int ans, j;
ans = 1;
for (j=1; j<=n; j++) ans *= i;
return(ans);
}
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++;
}
n
n
n
}
– Último teorema
x +y =z


Qual a saída deste programa?
Para entrada 2? E 3?

de Fermat
Levou 300 anos a provar que é
impossível para n3
Máquinas de Turing -3
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
–

Os programas são numeráveis
–
–
–

Não é possível estabelecer uma correspondência biunívoca com 
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 -4
Teste do “Hello, world”

Hipótese
–

P
I
H
yes
no
Um problema que tenha um
algoritmo como H é decidível
–

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
Senão é indecidível
Vamos provar que H não existe
–
Seria estranho que um programa
resolvesse o último teorema de
Fermat
Máquinas de Turing -5
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
P
I
H1
yes
hello,
world
Máquinas de Turing -6
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
H2
yes
hello,
world
H2 é modificação de H1
–
–

P
yes
hello,
world
H2 começa por ler P para um array com
H2
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?
Máquinas de Turing -7
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

–
Se imprimir hello, world (tem que ser uma ou outra das
possibilidades) então a saída da caixa tem que ser yes


Mas acaba-se de assumir que H2 com entrada H2 imprime 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 -8
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
Decide
yes ou no conforme a
sua entrada instância do
problema P2 está ou não
na linguagem do problema
P1
Constrói
P2
Decide
yes
no
Máquinas de Turing -9
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 -10
Exemplo de redução

Problema
–
–
–
–

Construção
–
–
–
–
–

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
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 -11
Motivação

Problemas indecidíveis
–

Problemas intratáveis
–
–

Não existe algoritmo
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 -12
Contexto

David Hilbert (início do séc. XX)
–

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)
–
–

Há alguma maneira de determinar se qualquer fórmula da lógica de
predicados de primeira ordem, aplicada aos inteiros, é verdadeira?
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 -13
Máquina de Turing
Controlo
… B

Xn
B
B
…
Número finito de estados
Cada célula pode conter um símbolo (alfabeto finito)
Entrada
–
–

Xi
Fita de comprimento infinito dividida em células
–

X1 X2
Controlo finito
–

B
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
Máquinas de Turing -14
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

–
2. Escrita de um símbolo na célula onde está a cabeça

–
Pode ser o mesmo
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 -15
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 -16
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 -17
Exemplo 0n1n


TM para aceitar a linguagem {0n1n | n1}
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 -18
Exemplo 0n1n
Estado
0
q0
(q1,X,R)
(q3,Y,R)
q1
(q1,0,R) (q2,Y,L)
(q1,Y,R)
q2
(q2,0,L)
q3
1
X
Y
B
(q0,X,R) (q2,Y,L)
(q3,Y,R) (q4,B,R)
q4
–
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
Máquinas de Turing -19
Computações no exemplo

Entrada 0011
–



q00011 ├ Xq1011 ├ X0q111 ├ Xq20Y1 ├ q2X0Y1 ├
Xq00Y1 ├ XXq1Y1 ├ XXYq11 ├ XXq2YY ├ Xq2XYY ├
XXq0YY ├ XXYq3Y ├ XXYYq3B ├ XXYYBq4B
–



Descrição instantânea inicial q00011
aceita
Entrada 0010
q00010 ├ Xq1010 ├ X0q110 ├ Xq20Y0 ├ q2X0Y0 ├
Xq00Y0 ├ XXq1Y0 ├ XXYq10 ├ XXY0q1B
–
morre
Máquinas de Turing -20
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
Y/Y 
0/0 
Start
q0
0/X 
q2
X/X 
Y/Y 
q3
1/Y 
q1
Y/Y 
0/0 
B/B 
Y/Y 
q4
Máquinas de Turing -21
Exemplo

Diagrama de transição para uma TM que aceite a linguagem
das cadeias com número igual de 0 e 1.
Y/Y 
Start
q0
0/X 
1/X 
B/B 
q1
1/1 
Y/Y 
0/Y 
q2
Y/Y 
0/0 
1/Y 
X/X 
q4
q3
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 -22
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
TM
PDA, CFG
DFA (NFA, -NFA), RE
Linguagens recursivamente enumeráveis
Linguagens sem contexto (CFL)
Linguagens regulares
(RL)
Máquinas de Turing -23
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 -24
Técnicas de programação de TM


Uma TM tem o mesmo poder computacional que os
computadores actuais
Memória no estado
–
–

Pistas múltiplas
–
–

Estado = controlo + memória de dados
Ver o estado como um tuplo
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 -25
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 -26
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 -27
Restrições




TM com fitas semi-infinitas
Máquinas com várias pilhas
Máquinas com contadores
Comparação com computadores
Máquinas de Turing -28