Problema de decisión para niños

En el mundo de la teoría de la computación, que es una parte de la informática que estudia qué se puede hacer con las computadoras, un problema es como un conjunto de preguntas que tienen una estructura similar. Cada pregunta tiene una respuesta específica. Un problema de decisión es un tipo especial de problema donde la única respuesta posible es "sí" o "no".

Imagina que un problema de decisión es como un juego de adivinanzas. Te dan una frase o un dato, y tú tienes que decidir si ese dato cumple con una regla específica, respondiendo solo "sí" o "no". Esto también se puede ver como decidir si una frase pertenece a un grupo especial de frases, que en informática llamamos un lenguaje formal. Este grupo contiene todas las frases para las cuales la respuesta es "sí".

¿Qué es un problema de decisión en computación?

Cuando hablamos de un "problema" en computación, nos referimos a un tipo de pregunta que se repite, pero con diferentes datos de entrada. Por ejemplo, la pregunta "¿Es un número primo?" es un problema. La respuesta a esta pregunta depende del número que nos den.

¿Qué es una instancia de un problema?

Una instancia es un caso particular de un problema. Es cuando le damos valores específicos a los datos de entrada. Siguiendo el ejemplo anterior, si preguntamos "¿Es 17 primo?", esa es una instancia del problema "¿Es un número primo?". La respuesta a esta instancia es "sí".

Otro ejemplo de problema de decisión es: "¿Contiene una palabra las letras 'a' y 'b' alternadas?". Una instancia sería: "¿La palabra 'ababab' contiene las letras 'a' y 'b' alternadas?". La respuesta es "sí".

¿Cuándo un problema es decidible o indecidible?

Un problema de decisión es decidible si podemos crear un algoritmo (una serie de pasos o instrucciones que una computadora puede seguir) que siempre nos diga "sí" o "no" para cualquier dato de entrada. Este algoritmo siempre debe terminar y dar una respuesta.

¿Qué significa que un problema sea parcialmente decidible?

Si un algoritmo puede decirnos "sí" cuando la respuesta es positiva, pero se queda "pensando" para siempre (nunca termina) cuando la respuesta es negativa, entonces decimos que el problema es parcialmente decidible. Es como si el algoritmo supiera cuándo algo es verdad, pero no cuándo es falso.

¿Qué es un problema indecidible?

Si no existe ningún algoritmo que pueda resolver un problema de decisión para todas las posibles entradas, entonces el problema es indecidible. Esto significa que no hay forma de que una computadora, siguiendo un conjunto de reglas, siempre pueda dar una respuesta de "sí" o "no" para ese problema.

En la teoría de la computabilidad, los expertos estudian qué problemas pueden ser resueltos por las computadoras y cuáles no. En la complejidad computacional, se analiza cuántos recursos (como tiempo o memoria) necesita un algoritmo para resolver un problema decidible.

Ejemplos de problemas de decisión

Aquí tienes algunos ejemplos de problemas de decisión, expresados como si fueran lenguajes o grupos de frases:

• ¿Una frase hecha solo con las letras 'a' y 'b' tiene estas letras alternadas? Por ejemplo, "ababab" (sí) o "aaabbb" (no).
• ¿Una frase hecha con las letras 'a', 'b' y 'c' tiene la misma cantidad de 'a's que de 'b's? Por ejemplo, "abcab" (sí, tiene dos 'a's y dos 'b's) o "aaabbc" (no).
• ¿Existe un camino entre dos puntos en un grafo (un diagrama con puntos conectados por líneas) que sea el más corto? Un grafo es como un mapa donde los puntos son ciudades y las líneas son carreteras con distancias.
• ¿Una máquina de Turing (un modelo teórico de computadora) se detendrá en un tiempo determinado al procesar una entrada específica? Este es un problema muy famoso llamado el problema de parada.

Los problemas de decisión son muy importantes porque muchos problemas en las matemáticas y la lógica se pueden transformar en problemas de decisión. Esto ayuda a los científicos a entender mejor qué se puede resolver con las computadoras.

Decidibilidad y conjuntos recursivos

A veces, para hablar de decidibilidad, usamos términos especiales para grupos de números naturales:

• A los grupos de números que corresponden a problemas decidibles se les llama recursivos.
• A los grupos de números que corresponden a problemas parcialmente decidibles se les llama recursivamente enumerables.

Véase también

En inglés: Decision problem Facts for Kids

• Decidibilidad
• Función recursiva