Undecidable Problems
Introducido| English | Significado |
|---|---|
| cannot/ˈkænɒt/ | no puede |
| decidable/dɪˈsaɪdəbl/ | decidible |
| undecidable/ˌʌndɪˈsaɪdəbl/ | indecidible |
| limit/ˈlɪmɪt/ | límite |
| inefficient/ɪnɪˈfɪʃənt/ | ineficiente |
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:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
"Is n even?" is decidable — always answerable.
Problemas decidibles
- Un problema decidible tiene un algoritmo que siempre proporciona 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.

Problemas decidibles e indecidibles
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:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Some questions simply have no general algorithm.
Problemas indecidibles
- Un problema indecidible no tiene ningún algoritmo que lo resuelva correctamente en todos los casos.
- 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 puede lograr la computación; algunas preguntas simplemente no tienen un algoritmo general.
Undecidable and merely inefficient (slow) mean the same thing.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
False. Primality is decidable: an algorithm always gives an answer. Being slow is not the same as being impossible.
Indecisible no es solo lento
- No confundir indecidible con simplemente ineficiente.
- Un problema ineficiente puede resolverse, solo lentamente. Uno indecidible no puede resolverse para todos los casos 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.
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).