Skip to main content
Fim da Recompensa com 50 pontos de reputação concedidos por bfavaretto
Link para problemas de decisão
Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

Em problemas de decisãoproblemas de decisão, existem alguns problemas que é possível responder, em tempo finito, se a resposta para ele é sim. Em compensação, talvez não seja capaz de responder não. O exemplo mais típico desses problemas em que há resposta para sim porém talvez não haja resposta para não é o problema da parada. Esses problemas pertencem a classe RE. Todos os problemas dentro dessa classe podem ser resolvidos por uma máquina de Turing.

Em problemas de decisão, existem alguns problemas que é possível responder, em tempo finito, se a resposta para ele é sim. Em compensação, talvez não seja capaz de responder não. O exemplo mais típico desses problemas em que há resposta para sim porém talvez não haja resposta para não é o problema da parada. Esses problemas pertencem a classe RE. Todos os problemas dentro dessa classe podem ser resolvidos por uma máquina de Turing.

Em problemas de decisão, existem alguns problemas que é possível responder, em tempo finito, se a resposta para ele é sim. Em compensação, talvez não seja capaz de responder não. O exemplo mais típico desses problemas em que há resposta para sim porém talvez não haja resposta para não é o problema da parada. Esses problemas pertencem a classe RE. Todos os problemas dentro dessa classe podem ser resolvidos por uma máquina de Turing.

Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

Não vou entrar no mérito tradicional, que creio que as respostas do Maniero e OnoSendai já respondem o núcleo da questão, mas vou entrar na real vantagem de se usar pilhas em algumas classes de problemas. Portanto, espere ver classes de complexidade nesta resposta e se, por acaso, o termo "classe de complexidade" não fizer sentido pra você, então essa resposta não acrescentará muito.

Em problemas de decisão, existem alguns problemas que é possível responder, em tempo finito, se a resposta para ele é sim. Em compensação, talvez não seja capaz de responder não. O exemplo mais típico desses problemas em que há resposta para sim porém talvez não haja resposta para não é o problema da parada. Esses problemas pertencem a classe RE. Todos os problemas dentro dessa classe podem ser resolvidos por uma máquina de Turing.

O nome RE significa recursivamente enumerável

Em compensação, temos uma outra classe de problemas: aqueles que se responde não em tempo finito, porém não necessariamente se responde sim em tempo finito. Esses problemas pertencem a co-RE.

O prefixo co significa "complemento", sendo o complemento entendido como sendo a operação de complemento da Teoria dos Conjuntos

E existem aqueles problemas que você consegue responder em tempo finito sim ou não. Esses problemas estão na interseção de RE e co-RE, a chamada classe R.

O nome R significa recursivo

Enquanto que para problemas RE você necessita de uma máquina de Turing com plena capacidade, para problemas R você consegue resolução com uma máquina de Turing com uma fita de tamanho finito dependente da entrada.

Tá, mas o que isso significa no final das contas?

Quando você está verificando para saber se é possível responder, você tem uma fita da máquina de Turing preenchida com a cabeça posicionada em um local arbitrário, e a máquina está em outro estado arbitrário. A partir daí, você tem uma quantidade finita de mudanças:

  • os estados que a máquina de Turing pode assumir são definidos por um conjunto finito S
  • os símbolos que a máquina de Turing pode preencher em uma célula da fita são limitados pelo conjunto finito Σ
  • a máquina de Turing pode ir pra esquerda na fita ou ir pra direita na fita
    • existem alguns autores que falam de uma terceira possibilidade: da máquina de Turing continuar na mesma posição

Logo, o próximo estado está em uma quantidade finita de opções para se buscar. Se o problema for R, isso significa que existe uma profundidade máxima de estados (no grafo de alteração de estado da máquina/fita) que se percorre até encontrar um beco com a resposta sim ou não, o que implica que, se tiver uma resposta positiva, ela está em outro percurso. Lembre-se também que, por conta da máquina de Turing que resolve estes problemas tem um tamanho de fita limitado, isso significa que ela não pode ir continuamente à direita, pois um dia ela irá esbarrar no limite da fita e estará em estado inválido e um Kuegelblitz surgirá e o universo será engolido por um buraco negro formado pela gravidade de fotóns em espaço compacto.

Porém, num problema RE, talvez não seja possível indicar que um caminho chegou ao final do processamento. A máquina de Turing continuará a se deslocar para a direita sem nunca chegar numa conclusão se a resposta para aquele caminho é não.

Na estrutura de resolução desses problemas, se você usar uma pilha (LIFO) para um problema RE, você pode entrar num poço infinito e jamais sairá de lá para investigar outro caminho. O jeito correto de se pesquisar por alguma resposta para problemas desta classe é usando uma fila (FIFO).

Em problemas de classe R, entretanto, usar uma pilha pode apresentar uma resposta mais rapidamente, pois você estará indo em profundidade no problema. Uma busca em largura exige verificar muitos caminhos intermediários que, talvez, não levem à resposta, sem falar que necessitam de uma memória sem limites.

Então, no final das contas:

  • a pilha oferece menor capacidade de busca em termos de classes de problemas que se resolve com buscas
  • a pilha oferece um limite menor de memória máxima usada para problemas que de fato ela consegue resolver
  • potencialmente a pilha responderá mais rapidamente um sim para o seu problema

Veja mais sobre busca em largura x busca em profundidade


Um outro ponto que eu gostaria de ressaltar aqui, sobre autômatos:

  • autômatos de pilha conseguem responder problemas que podem ser representados por uma linguagem livre de contexto
  • autômatos de fila são equivalentes em poder de resolução de problemas à máquinas de Turing