Undecidable Problems
Introduzido| English | Significado |
|---|---|
| cannot/ˈkænɒt/ | não pode |
| decidable/dɪˈsaɪdəbl/ | decidível |
| undecidable/ˌʌndɪˈsaɪdəbl/ | ind decidível |
| limit/ˈlɪmɪt/ | limite |
| inefficient/ɪnɪˈfɪʃənt/ | ineficiente |
Nem todo problema é solucionável
- Nem todo problema pode ser resolvido por um computador, mesmo em princípio.
- Para entender o motivo, classificamos os problemas em dois tipos.
- Um tipo que o computador sempre pode responder; o outro ele não consegue.
- Este é um fato comprovado da ciência da computação, e não uma lacuna que talvez preenchemos um dia.
A decidable problem is one where:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
"Is n even?" is decidable — always answerable.
Problemas decidíveis
- Um problema decidível possui um algoritmo que sempre fornece uma resposta correta de sim ou não para todos os casos.
- "Este número é par?" é decidível — um teste simples responde corretamente sempre.
- "Este número é primo?" também é decidível, mesmo que seja lento para números enormes.
- Se existe um algoritmo correto para todos os casos, o problema é decidível.

Problemas decidíveis e indecidíveis
Decidable or undecidable?
A decidable problem has an algorithm that always answers correctly for every case; an undecidable one has no such algorithm — being impossible, not merely slow.
An undecidable problem:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Some questions simply have no general algorithm.
Problemas indecidíveis
- Um problema indecidível não possui algoritmo algum que resolva corretamente todos os casos.
- Não importa quão inteligente seja o programa, alguns casos o derrotarão.
- O exemplo clássico: decidir, em geral, se qualquer programa dado parará de executar alguma vez.
- A indecidibilidade é um limite do que a computação pode alcançar — algumas questões simplesmente não possuem um algoritmo geral.
Undecidable and merely inefficient (slow) mean the same thing.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Inefficient can be solved slowly; undecidable cannot be solved for every case at all.
Testing whether a number is prime is undecidable because it can be slow for huge numbers.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
False. Primality is decidable: an algorithm always gives an answer. Being slow is not the same as being impossible.
Indecidível não é apenas lento
- Não confunda indecidível com meramente ineficiente.
- Um problema ineficiente pode ser resolvido, apenas lentamente. Um indecidível não pode ser resolvido para todos os casos.
Primo vs. Parada. Testar se um número é primo é decidível — um algoritmo sempre responde, mesmo se for lento para números enormes. Mas decidir em geral se qualquer programa vai parar é indecidível: nenhum único algoritmo responde corretamente para todos os programas. Lento não é o mesmo que impossível.
Um problema decidível tem um algoritmo que sempre responde corretamente ("n é par?", "n é primo?"). Um problema indecidível não tem nenhum tal algoritmo para todos os casos (um programa vai parar?) — um verdadeiro limite da computação. Indecidível significa que ele não pode ser resolvido em absoluto, e não apenas ineficiente (lento).