Diferencia entre revisiones de «Problema de decisión»
Contenido eliminado Contenido añadido
m Aplico plantilla MathWorld |
mSin resumen de edición |
||
Línea 4:
Un problema de decisión también se puede formalizar como el problema de decidir si una cierta frase pertenece a un [[conjunto]] dado de frases, también llamado [[lenguaje formal]]. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. La pregunta anterior sobre los números primos se puede ver también como el lenguaje de todas las frases en el alfabeto {0, 1,..., 9} tales que el entero correspondiente es primo.
Si existe un [[algoritmo]] que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un [[problema indecidible]]. Cuando existe un algoritmo que puede responder positivamente cuando la frase está en el lenguaje, pero que corre indefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es ''parcialmente decidible''. En [[
==Ejemplos==
Línea 11:
* Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.
* Las frases que describen un [[grafo]] con aristas etiquetadas con [[número natural|números naturales]] que indican su longitud, dos vértices del grafo y un camino en el grafo que es el [[problema del camino más corto|camino más corto]] entre esos dos vértices.
* Las frases que describen una [[máquina de Turing]] y una cinta de entrada para esta máquina tal que [[problema de parada|la máquina se
Los problemas de decisión son interesantes dado que todos los problemas [[Ciencias formales|formales]] (que incluye tanto lógicos como matemáticos) pueden ser redactados para que tomen la forma de un problema de decisión. Las soluciones al problema de decisión y al problema original se diferencian a lo sumo por un factor lineal.
| |||