Contenido principal
Curso: Principios de ciencias de la computación avanzados (AP Computer Science Principles) > Unidad 4
Lección 3: Resolver problemas difícilesProblemas indecidibles
Algunos problemas toman mucho tiempo en resolverse, así que usamos algoritmos que dan soluciones aproximadas. Hay algunos problemas que una computadora jamás podrá resolver, así sea la computadora más poderosa del planeta con tiempo infinito: los problemas indecidibles.
Un problema indecidible es aquel que debería dar una respuesta de "sí" o "no", pero para el cual todavía no existe un algoritmo que dé la respuesta correcta para todas las entradas posibles.
El problema de parar
Alan Turing probó la existencia de problemas indecibles en 1936 al encontrar un ejemplo, el hoy en día famoso "problema de parar":
Basado en su código y una entrada, ¿terminará de ejecutar un programa en particular?
Por ejemplo, considera este programa que cuenta hacia abajo:
num ← 10
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num - 1
}Ese programa parará, puesto que
num finalmente llega a 0.Compara ese con este programa que cuenta hacia arriba:
num ← 1
REPEAT UNTIL (num = 0) {
DISPLAY(num)
num ← num + 1
}Cuenta hacia arriba por siempre, puesto que
num nunca será igual a 0.Hay algoritmos que pueden predecir correctamente que el primer programa para y el segundo no lo hace. Estos son programas sencillos que no cambian con base en entradas diferentes.
Sin embargo, no existe un algoritmo que pueda analizar el código de cualquier programa y determinar si para o no.
Para probar que dicho algoritmo no puede existir, Turing usó una "prueba por contradicción".
Comenzamos por imaginar que si existe un algoritmo que determina si un programa para.
Luego proponemos un programa llamado
HaltChecker que toma dos entradas, el código de un programa y la entrada para ese programa. A continuación usamos ese algoritmo hipotético de parar que retorna "para" o "nunca".El siguiente diagrama de flujo visualiza a
HaltChecker:Si le damos los programas anteriores como entrada a
HaltChecker, veríamos que el programa de contar hacia abajo retorna "para" y el programa de contar hacia arriba retorna "nunca". Observa que no está realmente corriendo los programas, sino que examina su código y decide basado en su estructura.Pero ahora proponemos un programa llamado
Reverser. Toma una sola entrada, el código de un programa. Le envía a HaltChecker ese programa como el programa a analizar y como la entrada a usar. HaltChecker entonces determina si el programa de entrada para cuando recibe a sí mismo como entrada. Si HaltChecker retorna "para", Reverser ejecuta un bucle infinito. Si HaltChecker retorna "nunca", Reverser inmediatamente retorna.El siguiente diagrama de flujo visualiza a
Reverser:Si le damos el programa de contar hacia abajo como entrada a
Reverser, entonces verá que HaltChecker retorna "para" y por tanto decide iterar indefinidamente.Si le damos el programa de contar hacia arriba como entrada a
Reverser, verá que HaltChecker retorna "nunca" y por tanto decide retornar inmediatamente.Reverser es verdaderamente un programa extraño. Se detiene cuando encuentra que otro programa no para, y le gusta seguir indefinidamente cuando encuentra que otro programa sí para. Esto es raro, pero está bien. en el mundo se permiten programas extraños.Pero aqui es donde todo se cae en pedazos: ¿qué pasa si le damos el mismo
Reverser como entrada a Reverser?HaltChecker analiza el código de Reverser para determinar si se detiene o no. Si decide que no se detiene, entonces retorna "nunca". Reverser ve el resultado y retorna inmediatamente.Pero, ¡espera un segundo!
HaltChecker acaba de afirmar que Reverser nunca para, y luego paró. HaltChecker no nos dió luna respuesta correcta.¿Qué pasa si en vez de esto
HaltChecker retorna "para"? Cuando Reverserve el resultado, itera indefinidamenteHaltChecker acaba de afirmar que Reverser para, y sin embargo, continúa corriendo indefinidamente. Una vez más, HaltChecker no nos dio la respuesta correcta. De hecho, no hay forma que HaltChecker nos dé la respuesta correcta en esta situación.En consecuencia, hemos probado que nunca existirá un algoritmo perfectamente correcto para predecir paradas y que el problema de parar es indecidible.
Me tomó un buen rato entender de verdad el problema de parar. Si también tienes algún problema, este video animado puede serte útil.
Más problemas indecidibles
Los científicos de computación y los matemáticos han descubierto muchos otros problemas indecidibles. Muchos de estos, una vez simplificados, parecen variantes del problema de parar. Generalmente, todos los problemas indecidibles giran alrededor de la dificultad de determinar propiedades sobre la entrada y salida de programas.
Es útil darnos cuenta cuando estamos confrontados con un problema indecidible. Entonces podemos aceptar que nuestro programa no puede responder correctamente con un sí o un no a todas las entradas, y encontrar un enfoque diferente.
Por ejemplo, nuestro ambiente de programación en Khan Academy intenta evitar correr programas con bucles infinitos para evitar que se congele el pobre navegador. Pero, ¿cómo podemos saber que un programa tiene un bucle infinito? ¡No podemos, pues es indecidible! En vez de esto, monitoreamos cuánto demoran los bucles, y cuando un bucle toma demasiado tiempo, nos negamos a ejecutar el código. No podemos saber con certeza si ese bucle iba a ejecutar indefinidamente, pero para nuestros propósitos, es mejor prevenir que luego lamentar.
🙋🏽🙋🏻♀️🙋🏿♂️¿Tienes alguna pregunta sobre este tópico? Nos encantaría contestarte; ¡simplemente pregunta en el área de preguntas abajo!
¿Quieres unirte a la conversación?
quisera ejemplos de la vida cotidiana(2 votos)