Undecidable Problems · Problemas Indecidíveis
| English | Português |
|---|---|
| cannot/ˈkænɒt/ | não pode |
| decidable/dɪˈsaɪdəbl/ | decidível |
| undecidable/ˌʌndɪˈsaɪdəbl/ | indecidível |
| limit/ˈlɪmɪt/ | limite |
| inefficient/ɪnɪˈfɪʃənt/ | ineficiente |
Not every problem is solvable
- Not every problem can be solved by a computer, even in principle.
- To see why, we sort problems into two kinds.
- One kind a computer can always answer; the other it cannot.
- This is a proven fact of computer science, not a gap we might one day fill.
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: · Um problema decidível é aquele em que:
"Is n even?" is decidable — always answerable. · "n é par?" é decidível — sempre respondível.
Decidable problems
- A decidable 可判定 problem has an algorithm that always gives a correct yes-or-no answer for every case.
- "Is this number even?" is decidable — a simple test always answers correctly.
- "Is this number prime?" is decidable too, even if slow for huge numbers.
- If a correct algorithm exists for every case, the problem is decidable.
Problemas decidíveis
- Um problema decidível 可判定 tem um algoritmo que sempre fornece uma resposta correta de sim ou não para cada caso.
- "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.
Decidable or undecidable? · Decidível ou indecidível?
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. · Um problema decidível tem um algoritmo que sempre responde corretamente para cada caso; um indecidível não tem tal algoritmo — sendo impossível, não meramente lento.
An undecidable problem: · Um problema indecidível:
Some cases defeat every possible program. · Alguns casos derrotam qualquer programa possível.
Deciding in general whether any given program will ever stop running is: · Decidir, em geral, se algum programa dado parará de executar é:
No single algorithm answers this correctly for every program. · Nenhum único algoritmo responde a isso corretamente para todo programa.
Undecidability marks a hard ______ on what computation can achieve. · A indecidibilidade marca uma barreira dura ______ sobre o que a computação pode alcançar.
Some questions simply have no general algorithm. · Algumas perguntas simplesmente não têm um algoritmo geral.
Undecidable problems
- An undecidable 不可判定 problem has no algorithm that solves every case correctly.
- No matter how clever the program, some cases will defeat it.
- The classic example: deciding, in general, whether any given program will ever stop running.
- Undecidability is a limit 极限 on what computation can achieve — some questions simply have no general algorithm.
Problemas indecidíveis
- Um problema indecidível 不可判定 não possui nenhum algoritmo que resolva todos os casos corretamente.
- 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 极限 no que a computação pode alcançar — algumas perguntas simplesmente não têm um algoritmo geral.
Undecidable and merely inefficient (slow) mean the same thing. · Ineficiente e meramente ineficiente (lento) significam a mesma coisa.
Inefficient can be solved slowly; undecidable cannot be solved for every case at all. · Ineficiente pode ser resolvido lentamente; indecidível não pode ser resolvido para todos os casos.
Testing whether a number is prime is decidable, even if it is slow for huge numbers. · Testar se um número é primo é decidível, mesmo que seja lento para números enormes.
An algorithm always answers; slow is not the same as impossible. · Um algoritmo sempre responde; lento não é o mesmo que impossível.
Undecidable is not just slow
- Do not confuse undecidable with merely inefficient 低效.
- An inefficient problem can be solved, just slowly. An undecidable one cannot 不能 be solved for every case at all.
Prime vs halting. Testing whether a number is prime is decidable — an algorithm always answers, even if slow for huge numbers. But deciding in general whether any program will halt is undecidable: no single algorithm answers correctly for every program. Slow is not the same as 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 em absoluto.
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.
A decidable problem has an algorithm that always answers correctly ("is n even?", "is n prime?"). An undecidable problem has no such algorithm for every case (will a program halt?) — a real limit of computing. Undecidable means it cannot be solved at all, not merely inefficient (slow).
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).