Undecidable Problems · Problemas Indecidibles
| English | Español |
|---|---|
| cannot/ˈkænɒt/ | no puede |
| decidable/dɪˈsaɪdəbl/ | decidable |
| undecidable/ˌʌndɪˈsaɪdəbl/ | indecidible |
| limit/ˈlɪmɪt/ | límite |
| 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.
No todos los problemas son resolubles
- No todos los problemas pueden ser resueltos por una computadora, ni siquiera en principio.
- Para entender el porqué, clasificamos los problemas en dos tipos.
- Un tipo de problema que la computadora siempre puede resolver; el otro, no.
- Este es un hecho demostrado de la ciencia de la computación, no una brecha que podamos llenar algún día.
A decidable problem is one where: · Un problema decidable es aquel en el que:
"Is n even?" is decidable — always answerable. · "¿Es n par?" es decidable — siempre respondible.
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 decidibles
- Un problema decidible tiene un algoritmo que siempre da una respuesta correcta de sí o no para cada caso.
- "¿Es este número par?" es decidible — una prueba simple siempre responde correctamente.
- "¿Es este número primo?" también es decidible, aunque sea lento para números inmensos.
- Si existe un algoritmo correcto para cada caso, el problema es decidible.
Decidable or undecidable? · ¿Decidable o indecisible?
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. · Un problema decidable tiene un algoritmo que siempre responde correctamente para cada caso; uno indecisible no tiene tal algoritmo — siendo imposible, no simplemente lento.
An undecidable problem: · Un problema indecisible:
Some cases defeat every possible program. · Algunos casos derrotan a cualquier programa posible.
Deciding in general whether any given program will ever stop running is: · Determinar en general si algún programa dado se detendrá alguna vez es:
No single algorithm answers this correctly for every program. · No hay un solo algoritmo que responda correctamente para todos los programas.
Undecidability marks a hard ______ on what computation can achieve. · La indecidibilidad marca una difícil ______ sobre lo que la computación puede lograr.
Some questions simply have no general algorithm. · Algunas preguntas simplemente no tienen un algoritmo general.
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 indecidibles
- Un problema indecidible no tiene ningún algoritmo que resuelva correctamente cada caso.
- No importa cuán inteligente sea el programa, algunos casos lo derrotarán.
- El ejemplo clásico: decidir, en general, si cualquier programa dado se detendrá alguna vez.
- La indecidibilidad es un límite sobre lo que la computación puede lograr — algunas preguntas simplemente no tienen un algoritmo general.
Undecidable and merely inefficient (slow) mean the same thing. · Indecisibilidad e ineficiencia (lento) significan lo mismo.
Inefficient can be solved slowly; undecidable cannot be solved for every case at all. · La ineficiencia puede resolverse lentamente; la indecisibilidad no puede resolverse para todos los casos en absoluto.
Testing whether a number is prime is decidable, even if it is slow for huge numbers. · Probar si un número es primo es decidable, incluso si es lento para números enormes.
An algorithm always answers; slow is not the same as impossible. · Un algoritmo siempre responde; ser lento no es lo mismo que ser imposible.
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.
Indecisible no es solo lento
- No confunda indecidible con meramente ineficiente.
- Un problema ineficiente puede ser resuelto, solo que lentamente. Uno indecidible no puede ser resuelto para cada caso en absoluto.
Primos vs. detención. Probar si un número es primo es decidible — un algoritmo siempre responde, incluso si es lento para números grandes. Pero decidir, en general, si cualquier programa se detendrá es indecidible: ningún único algoritmo responde correctamente para cada programa. Lento no es lo mismo que imposible.
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).
Un problema decidible tiene un algoritmo que siempre responde correctamente ("¿es n par?", "¿es n primo?"). Un problema indecidible no tiene ningún tal algoritmo para cada caso ("¿se detendrá un programa?") — un verdadero límite del cómputo. Indecisible significa que no puede ser resuelto en absoluto, no meramente ineficiente (lento).