46

Eu já li e reli no Wikipédia, já assisti uns 15 videos em inglês e em português sobre esse assunto, já li vários artigos no google, mas não consigo entender.

Por que ela entraria num loop infinito? Ou por que ela pararia? Todas as explicações usando a contradição não fazem sentido na minha cabeça.

Por favor, sem termos técnicos. Me ajude com lógica simples a entender.

7
  • 1
    Essa pergunta é aberta com uma explicação intuitiva do assunto: pt.stackoverflow.com/q/30749/64969 ; ajudou no entendimento? Commented 16/02/2018 às 2:16
  • 1
    Não @jeffersonquesado. Isso só me deixou mais confuso. Eu estou lendo até agora, e não consigo entender, por que por principio de contrádição o problema de parada é indecidivel.
    – Nakamoto
    Commented 16/02/2018 às 2:50
  • Estou elaborando uma resposta naquela questão, então depois eu volto para a sua questão. Por sinal o autor da outra questão sugeriu uma heurística que poderia ser boa o suficiente, e o questionamento dele foi se a heurística dele era realmente boa o suficiente ou se poderia haver alguma outra heurística boa o suficiente para tal Commented 16/02/2018 às 2:55
  • Escreva um programa A que lê o programa B e diz se o programa B nunca para. Agora suponha que A é um programa que nunca para, nem mesmo A vai conseguir dar uma resposta quando lê a si mesmo (a resposta é dada quando o programa para)
    – jean
    Commented 16/02/2018 às 15:26
  • @jean mas aí você poderia supor que A não para. A resposta do Victor Stafusa fala muito bem do assunto, até melhor do que a minha Commented 16/02/2018 às 15:30

2 Respostas 2

65
+200

O que é uma máquina de Turing para leigos?

Uma máquina de Turing é um modelo matemático minimalista de um computador com uma memória infinita. Embora seja minimalista, todas as máquinas de Turing são capazes de simular umas as outras. Ou seja, todos os computadores com memória infinita são capazes de simular uns aos outros (mesmo que o desempenho seja péssimo).

Assim sendo, uma vez que você tem uma quantidade de memória ilimitada, você pode resolver qualquer problema computacional, certo? Não!

O problema da parada

O problema da parada é o primeiro problema que foi comprovado ser computacionalmente insolucionável qualquer que seja a quantidade de memória disponível. Para ver porque, vamos elaborar o problema da parada dessa forma:

Preciso de um programa de computador (termina) que seja capaz de inspecionar o código de outro programa de computador (P) para determinar se ele entra ou não em um laço infinito quando lhe é dada a entrada C. O programa termina deve dar como saída "Sim" ou "Não" em um tempo finito.

Vamos supor que você vá projetar o programa termina com a linguagem de programação que quiser utilizando as técnicas que quiser. Uma forma de verificar se P pode entrar em um laço infinito com a entrada C é simulá-lo com tal entrada e ficar monitorando cada estado individual da memória de P. Se o programa P repetir algum estado de memória, então ele seguramente entrou em um laço infinito e o programa termina responde "Não". Se o programa P terminar a sua execução (parar), então seguramente ele não entrou em um laço infinito e o programa termina responde "Sim". Entretanto, isso não é tudo.

O programa P pode ocupar cada vez mais e mais memória a medida que processa a entrada C, e mesmo se/quando consumir a entrada toda, ainda assim não parar e continuar consumindo mais e mais memória (que lembre-se é infinita, e portanto ele pode consumir o quanto quiser). Dessa forma, é possível que ele nunca pare e também nunca repita um estado da memória. Com isso, o programa termina precisará ser mais inteligente do que simplesmente monitorar os estados da memória buscando por uma repetição ou por uma finalização de P.

Se o programa P consome cada vez mais e mais memória infinitamente, o programa termina poderia ver se essa memória segue algum padrão de repetição. Entretanto, isso também não funciona, pois vai que o programa P esteja produzindo os dígitos de π infinitamente e portanto nunca haveria repetição nesse padrão. O programa termina poderia determinar que depois de consumir um número bem grande (X) de células de memória, então P não para, mas vai que após X + 1 células de memória ele pararia?

Exemplo 1 de por que o problema da parada é difícil

O programa termina pode inspecionar a estrutura do programa P para determinar se ele pararia, mas vamos supor que o programa P seja o programa collatz abaixo*, escrito em Python:

def collatz(n):
    while n != 1:
        print(n)
        if n % 2 == 0:
            n = n / 2
        else:
            n = n * 3 + 1

Esse é um programa bem simples. O valor n é a entrada. Quando o n chegar em 1, o programa termina. Se o n for par, ele é dividido por dois. Se for ímpar é multiplicado por 3 e é somado 1. Ele imprimirá uma sequência de números até que n chegue a 1. Veja aqui esse programa executando no ideone para o número 127. A imagem abaixo mostra um gráfico com os números gerados nesse processo:

Números no processo de Collatz com 127

*:Peguei esse programa e também essa imagem da Wikipédia

Se eu definir um número bem grande para o n, ele vai parar ao eventualmente produzir 1? Ou ele vai gerar números cada vez maiores indefinidamente para sempre? A resposta é que não se sabe. Esse é um problema matemático (conjectura de Collatz) proposto em 1937 para o qual não se conhece solução, embora acredita-se que a resposta seja que ele sempre pare. Se o seu programa termina for determinar se este programa collatz para, então termina é um programa capaz de solucionar essa conjectura em um tempo finito. Isso significa que termina teria que ser programado com técnicas sofisticadas o suficiente para provar conjecturas matemáticas não-solucionadas.

Exemplo 2 de por que o problema da parada é difícil

Outro exemplo (também em Python):

def reversed_string(a_string):
    return a_string[::-1]

def lychrel(n):
    s = str(n)
    if s == reversed_string(s):
        print(s + ' é palíndromo!')
        return n
    m = int(reversed_string(s))
    c = m + n
    print(s + ' + ' + str(m) + ' = ' + str(c))
    return lychrel(c)

Nesse exemplo, a entrada é um número n. Se n for um número palíndromo (também chamado de capicua, ou seja, igual a ele mesmo de trás-para-frente), ele é retornado. Se não for, desse número n, é produzido um número m que é n de trás-para-frente e então os dois são somados produzindo c que é usado recursivamente como um novo n até que um palíndromo seja produzido. Para ficar claro o que o programa está fazendo, ele imprime na saída todos esses números que ele gera. Veja aqui o programa funcionando no ideone para o número 468.

A função lychrel termina quando a entrada é o número 196? Esse é outro problema matemático em aberto. A conjectura de Lychrel afirma que terminaria sempre, mas acredita-se que essa conjectura é falsa e que 196 seria o primeiro contra-exemplo dela. Novamente, como esse é um problema matemático em aberto, ninguém sabe a resposta, e após algumas bilhões de iterações que produzem números com bilhões de dígitos, um palíndromo insiste em não se formar, mas não se sabe se eventualmente um se formaria com um trilhão, um quadrilhão ou um zilhão de iterações ou se de fato nunca se formaria. Veja aqui o programa rodando no ideone para o número 196.

Se o seu programa termina fosse examinar o programa lychrel para determinar (em um tempo finito) se ele termina com a entrada 196, ele precisaria ser capaz de ou determinar quando ele terminaria ou então descobrir uma razão pela qual nunca terminaria, e com isso solucionar um outro problema matemático em aberto. Novamente, para fazer isso, esse programa termina não seria algo simples.

Exemplo por diagonalização de por que o problema da parada é difícil

E então caímos na prova por contradição a partir da diagonalização. Imagina que o programa P fosse esse:

import termina

def malandro(entrada):
    if termina(malandro, 'não importa'):
        while True:
            print('Estou num laço infinito')
    else:
        print('Acabou')

Esse programa é malandro. Consiste no seguinte: Sabendo que o programa termina determina se um outro programa para com alguma entrada qualquer, o programa malandro usa o programa termina para determinar se ele mesmo termina com a entrada 'não importa'. Se termina determinar que malandro para, então malandro entra em um laço infinito. Se termina determinar que malandro entra em um laço infinito, então malandro termina.

Ou seja, o programa malandro, pergunta ao programa termina o que ele faz e então faz exatamente o contrário! Isso significa que não há como o programa termina dar a resposta correta quando receber como entrada o programa malandro. Ou seja, ou o programa termina está incorreto ou ele pode não terminar em um tempo finito.

Dessa forma, está demonstrado que não existe forma de se construir o programa termina que execute tanto corretamente quanto em um tempo finito. Qualquer tentativa de construí-lo irá, pelo menos em alguns casos patológicos, ou produzir a resposta errada ou não produzir resposta em tempo finito. Logo, uma versão sem erros e perfeita do programa termina simplesmente não existe.

E se o programa pudesse responder que caiu em contradição?

Uma possível (e ingênua) solução seria se o programa termina observasse que o programa malandro usa o próprio programa termina ou então que ele depende de condições contraditórias e com isso, ao invés de responder "Sim" ou "Não", responda "impossível determinar".

Isso também não daria certo. Vamos supor que o programa malandro2 tenha dentro de si uma cópia do programa termina, mas com todas as variáveis e funções renomeadas e criptografado. O programa termina teria que determinar que há uma cópia de si mesmo dentro do programa que ele quer analisar. E então o programa seria isso:

import copia_malandra_de_termina

def malandro2(entrada):
    z = copia_malandra_de_termina(malandro2, 'não importa')
    if z == 'Sim':
        while True:
            print('Estou num laço infinito')
    elif z == 'Não':
        print('Acabou')
    elif z == 'impossível determinar':
        print('Impossível determinar uma ova, acabou sim!')
    else:
        print('Haha, vai acabar do mesmo jeito')

Ou seja, não importa o quão sofisticada fosse a forma que o programa termina assumisse para tentar evitar a contradição, sempre haverá uma forma ainda mais sofisticada para derrotá-la. Isso reafirma a hipótese de que o programa termina simplesmente não existe.

Outros problemas insolúveis

Uma forma de se provar que um problema é insolúvel, é reduzi-lo ao problema da parada. A forma de fazer isso é por contradição. Vamos dizer que sbrubbles é o nome do nosso problema insolucionável e que tenhamos alguma biblioteca hipotética com um programa sbrubbles_solver que de alguma forma o solucione. Se você conseguir bolar um algoritmo que ao utilizar o programa sbrubbles_solver seja capaz de fornecer uma solução ao problema da parada então você chega nisso:

  • Se existe um programa para solucionar o problema sbrubbles, então podemos usá-lo para criar uma solução para o problema da parada.
  • Sabemos que não podemos criar uma solução para o problema da parada.
  • Logo, por modus tollens, não podemos criar uma solução para o problema sbrubbles.

Assim sendo, por meio dessa técnica de reduzir um problema Q ao problema da parada, é possível provar-se que Q é um problema insolúvel.

É verdade que elaborar um algoritmo que em teoria resolveria o problema da parada ao aproveitar-se de uma função/programa hipotético que resolva o problema Q pode não ser tarefa simples. Entretanto é exatamente assim que muitos problemas são demonstrados serem insolúveis.

Em especial, de acordo com o teorema de Rice, determinar se algum programa de computador tem qualquer propriedade semântica não-trivial é um problema insolúvel. Por propriedade trivial entenda-se aquelas que são válidas para todos os programas ou para nenhum programa (e portanto, as não-trivias são aquelas que são verdadeiras para uns e falsas para outros). Por propriedade semântica, entenda-se por propriedades sobre o comportamento do programa. O motivo disso ser insolúvel é que o programa em questão pode, da mesma forma que o programa malandro, utilizar-se do programa que determina se ele mesmo contém tal propriedade semântica para produzir uma contradição. Assim sendo, é um problema insolúvel projetar-se qualquer algoritmo A que tente decidir algo sobre o comportamento de um outro algoritmo B sem que exista algum erro, limitação ou laço infinito no algoritmo A.

13
  • 1
    Conjectura de Collatz, esqueci totalmente dela! Muito bem lembrado Commented 16/02/2018 às 15:13
  • 2
    @JeffersonQuesado Tentei dar uma resposta menos teórica e muito mais for dummies que a sua. Commented 16/02/2018 às 15:18
  • 2
    eu tentei dar uma resposta mais leiga que a minha, mas não consegui. A sua está muito boa, dá uma ideia muito interessante e muito intuitiva do porquê é difícil fazer o termina. Entrando na leitura da diagonalização agora Commented 16/02/2018 às 15:22
  • 1
    Acho que você tem a contribuir com essa outra questão sobre uma tentativa de heurística para o problema da parada: pt.stackoverflow.com/q/30749/64969 Commented 16/02/2018 às 15:31
  • 2
    @JeffersonQuesado A heurística do problema de parada cai na mesma cilada de tentar provar que Pi é uma dízima periódica. Pode-se supor que Pi vai apresentar um padrão de repetição antes de infinitos dígitos mas pode ser que esse padrão só se repita após um zilhão de dígitos e por enquanto nós só conseguimos calcular até 22.4 trilhões de dígitos (e levou mais de três meses rodando isso)
    – jean
    Commented 16/02/2018 às 15:51
35

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 é:

  • ler dados
  • escrever dados

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:

  1. Todos os caminhos foram investigados até o fim, portanto a gramática gera uma linguagem finita
  2. 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:

  1. se w realmente poder ser gerada por G, depois de "alguns" processamentos encontraremos w
  2. 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
  3. 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.

4
  • 1
    Jefferson, sua resposta está excelente. Mas ainda assim meio confusa para mim e para algumas pessoas. Imagina, por exemplo, como eu explicaria sua explicação para usa sala de aula na sexta série? Para uma pessoa de 13 anos?
    – Nakamoto
    Commented 17/02/2018 às 11:07
  • 1
    Mesmo assim, sua resposta é válida. Ela é bem completa e ajuda muito se alguém quiser se aprofundar mais ou ter uma ideia melhor do problema. Até por que, depois do wikipédia, artigos em português na internet sobre esse assunto são escassos. Então, sendo assim, aqui deixo meu muito obrigado como forma de agradeço.
    – Nakamoto
    Commented 17/02/2018 às 11:07
  • @Nakamoto, tentei meu melhor, mas a resposta do Victor realmente tá mais adequada. Vou continuar tentando melhorar com o passar do tempo, mas sei que não vou conseguir chegar perto da resposta dele. Commented 17/02/2018 às 15:04
  • Jefferson sua resposta ficou ótima também. Ela ficou mais completa, técnica e abrangente. Ela pode ajudar alguém que queira ainda mais informações para entender o problema. Você contribuiu para aumentar ainda mais a qualidade do SOpt.
    – Nakamoto
    Commented 23/02/2018 às 18:04

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .