O problema da parada normalmente é fornecido da seguinte maneira:
Dado um programa e uma entrada que ele aceite, esse programa vai me dar uma resposta? Ou seja, ele vai em algum momento parar a sua execução?
Obs.: eu tenho todo o tempo do mundo, mas não tempo infinito.
Aparentemente, a resposta deveria ser sim. Mas... nem sempre é o caso. Às vezes o programa entra em laço infinito. Isso pode acontecer porque o programador que o escreveu cometeu um erro, ou porque o programador escolheu a abordagem errada ao tratar do problema, ou simplesmente porque o problema em questão não pode ser resolvido.
Mas existem problemas que não podem ser resolvidos? Sim, existem. Eles são problemas que, dada uma entrada, existe a possibilidade do programa entrar em laço infinito. Independente do quão bom for o programa. E ele não entra em laço infinito de maneira simples e trivial não. Alguns problemas, como reconhecer se uma palavra pertence a uma gramática irrestrita, ou se dado um conjunto finito de matrizes n x n
é possível obter a matriz nula apenas multiplicando (com repetições) os elementos desse conjunto, os programas que resolvem tais problemas podem entrar em recursões e nunca voltar para algum estado anterior.
Agora, respondendo às perguntas do texto... na ordem que eu acho mais adequada. E estou tentando colocar os conceitos de maneira mais leve o possível, mas por questões de corretude vai chegar em momentos em que precisarei ser técnico demais. Sempre que possível procurarei separar um conceito na parte "leiga", e deixar uma explicação mais técnica e matemática abaixo ou linkada.
... por que ela [máquina de Turing] pararia?
Uma máquina de Turing é um autômato. Como tal, a única coisa que ela faz é:
E ela faz isso a partir de um dado inicial, chamado de entrada. Em problemas de decisão você precisa de uma resposta "sim" ou "não". E essa resposta só é útil no final do processamento, quando a máquina de Turing estiver parada. A aceitação ou rejeição da entrada pode ser feita através de uma escrita, mas normalmente é mais útil saber se está em um estado de aceitação ou não.
Por que ela [máquina de Turing] entraria em loop infinito?
Porque existem problemas insolúveis/indecidível. O @Guilherme Bernal propõe uma heurística para procurar casos para identificar quando um software entra em laço infinito nessa questão, mas eu apontei um caso "trivial" de falha do programador que ele não conseguiria detectar com a heurística dele. Também apontei outra heurística "mais feia" que é mais leve, porém com quantidade menor de falso positivo para "programa em laço infinito".
(Spoiler alert: parte técnica começou) Um exemplo de problema que é indecidível é saber se uma palavra pode ser obtida a partir de uma gramática irrestrita.
Uma gramática irrestrita é uma gramática que aceita produções de qualquer tipo. Veja mais aqui, aqui.
Em outras palavras, esse problema é w ∈ L(G)
:
w
é a palavra que queremos saber se pode ser obtida a partir da gramática
G
é a gramática irrestrita em questão
L
é a "função linguagem", que dada uma linguagem, retorna todas as palavras que podem ser geradas a partir dela
Em gramáticas de linguagens infinitas, computar L(G)
em sua completude é... infinito também. Talvez infinito vezes algum polinômio não nulo?
Então, deve haver alguma maneira de verificar sem precisar listar todas as palavras, certo? Bem, aí depende da gramática.
Em caso de gramáticas regulares, é trivial. O primeiro passo, entretanto, é transformar o problema em uma autômato de estados finitos determinístico (veja mais aqui). Após isso, é apenas alimentar o autômato com a palavra e, se ele parar em um estado de aceitação, a palavra pertence à linguagem. Caso contrário, ela não pertence à linguagem.
Para gramáticas livres de contexto, você poderia normalizar para a forma normal de Chomsky e tentar montar a árvore de derivação pela estratégia ascendente. Se conseguir o não-terminal S
no topo, então pertence à gramática, caso contrário (achou outro não-terminal ou não achou resposta alguma) então não pertence.
Para gramática sensíveis a contexto, a coisa começa a complicar. Não há caminho direto a se seguir. O máximo que podemos fazer é transformar em uma gramática não-retraente. Toda gramática sensível ao contexto pode ser transformada em uma gramática não-retraente de modo queL(Gsc) = L(Gnr)
, onde Gsc
é a gramática sensível ao contexto e Gnr
é a gramática não-retraente. Uma propriedade interessante da gramática não-retraente é que uma forma sentencial só pode ser derivada em formas sentenciais de mesmo tamanho ou maior. Então, se a forma sentencial intermediária for maior do que o comprimento de w
, já sabemos que estamos no caminho errado, então é só voltar e tentar outro caminho. E, sim, a solução para gramáticas sensíveis a contexto mais eficiente é listando em profundidade todas as transformações possíveis e cortando quando a forma intermediária é grande demais.
Para gramáticas irrestritas... bem, elas podem ser escritas de modo a serem retraentes... inclusive não há nada proibindo o consumo de um terminal gerado no meio de uma produção. Então, limitar pelo tamanho da forma sentencial não é uma boa para o caso geral.
O que fazer, nesse caso? Bem, o melhor que pode ser feito é construir o grafo de derivações. Esse mesmo grafo pode ser usado para as outras gramáticas restritas também.
Como funciona esse grafo? Bem, começamos com o vértice com o não-terminal inicial, S
. Então verificamos quais são as produções que esse vértice pode sofrer, e para cada produção nós pegamos o vértice P1
, P2
... Pn
para cada uma das n
produções possíveis e ligamos com arestas ao vértice originador. Caso uma das produções gere uma forma sentencial Pi
já conhecida, devemos ligar a esse vértice no lugar de criar um novo vértice. Então adicionamos todos os vértices na estrutura de visitas futuras e marcamos S
como já visitado.
O próximo passo é pegar o próximo vértice da estrutura de visitas futuras e, em cima dele, fazer todas as derivações possíveis, adicionar os novos vértices e novas arestas no grafo, adicionando os vértices vizinhos na estrutura de visita futura para, então, marcar o vértice como visitado. Claro, se um vértice já foi visitado, não se deve fazer esse processamento novamente.
Caso o vértice sendo visitado seja composto apenas de terminais, então podemos verificar se Pv = w
. Se sim, achamos a resposta, caso contrário não sabemos de nada.
No caso das gramáticas não-retraentes, a estrutura adequada para armazenar os vértices de visita futura é pilha, fazendo uma busca em profundidade. Isso porque é sabido que, como a gramática é não-retraente, existe um limite máximo de vértices que podem ser gerados no meio do caminho. Se existirem n
não-terminais, só preciso examinar no máximo (n+len(w))^len(w)
vértices distintos, pois existem n+len(w)
símbolos distintos na gramática que são relevantes para a palavra w
e qualquer forma sentencial Pg
tal que len(Pg) > len(w)
implica que w
não pode ser obtida a partir de Pg
.
Já no caso da gramática irrestrita, a melhor estrutura para fazer essa análise é a fila. Isso vai permitir fazer uma busca em largura do grafo de derivações. Usar a busca em largura evita cair num buraco da perdição que mesmo explorando as infinitas possibilidades dele não chegue em w
, pois o processamento de outros caminhos continua a ser feito.
Caso seja possível responder "sim", ocasionalmente em um dos vértices conterá w
e garantidamente passaremos por ele daqui até o final dos tempos. Caso não seja possível, existem duas hipóteses:
- Todos os caminhos foram investigados até o fim, portanto a gramática gera uma linguagem finita
- Pelo menos um dos caminhos é um poço sem fim e o programa continuará a explorar esse poço em largura, adicionando novos vértices para serem visitados
No segundo caso, a máquina de Turing não irá parar.
Todas as demonstrações usando a contradição não fazem sentido na minha cabeça.
Bem, creio que isso signifique que você tem dúvidas sobre como provar que o problema da parada é indecidível. Vamos usar o problema anterior para esclarecer isso?
Caso você, caro leitor, tenha pulado a seção anterior após ver o spoiler alert: parte técnica começou, vou recapitular brevemente qual o problema. Deseja-se saber se uma palavra w
pode ser gerada a partir de uma gramática irrestrita G
. Modelamos então um grafo que representa todas as formas sentenciais que posso obter a partir de uma forma sentencial prévia obedecendo às regras de produção de G
e fazemos uma busca em largura.
Os resultados possíveis são:
- se
w
realmente poder ser gerada por G
, depois de "alguns" processamentos encontraremos w
- se tentarmos percorrer em largura todos os caminhos e eles acabaram sem achar
w
, então a linguagem L(G)
gerada por G
era finita e nós enumeramos todos os seus elementos e nenhum deles era w
- um dos caminhos é um poço sem fim, em que a busca em largura continuará indefinidamente gerando novos vértices à toa, sem nunca levar a
w
A gente sabe esses resultados porquê de certo modo sabemos a priori se w ∈ L(G)
. E o que aconteceria se nós realmente não soubermos do resultado do algoritmo?
Neste caso, vamos precisar esperar que o algoritmo dê uma resposta (1), enumere todas as possibilidades e nenhuma delas seja w
(2) ou que ele entre em loop infinito (3).
Os casos (1) e (2) são triviais. Afinal, se parou, parou, temos a resposta. E para o caso (3)? O @Guilherme Bernal forneceu uma heurística nessa questão. Mas infelizmente ela não funciona para o caso geral.
Olhando de outra perspectiva... vou deixar minha máquina de Turing trabalhando por um tempo. Deixo ela processando por... duas semanas. Após esse tempo eu pauso ela e verifico seu estado interno. Bem, ela diz que ainda há caminhos a serem desbravados, vértices não visitados. Então deixo ela processar mais um pouco. Volto cinco anos depois, e aí? Bem, agora existem dois bilhões de vértices a serem visitados. Me assusto, mas isso significa que ela está progredindo... ou não?
Bem, talvez no próximo segundo ela simplesmente pare e grite "terminei, achei w
". Talvez demore mais uma semana. Ou então dois séculos. Impossível determinar isso olhando para ela. Talvez esses dois bilhões de vértices sejam dois bilhões de poços sem fim. Ou não! Talvez todos eles consigam gerar w
no futuro, próximo ou distante. Talvez o processamento esteja levando para algum lugar, talvez seja apenas processamento em vão.
Ao pegar uma máquina de Turing que resolve o problema de saber se w
é gerada por G
e ela ainda estiver em processamento, é impossível determinar se é porque ela está a caminho de (1) ou de (2), ou se ela está na perdição em (3).
Esse é um exemplo que mostra a impossibilidade de determinar se uma dada máquina de Turing irá um dia dar uma resposta. Afinal, eu tenho todo o tempo do mundo, mas não tempo infinito.