Indecibilidad


Indecibilidad

La indecibilida es la propiedad de un problema que no puede ser solucionado mediante un algoritmo.
Sí nos centramos en la Máquina de Turing en la que no existen las limitaciones podremos entender mejor la idea básica de que algún dispositivo de computación será capaz de hacerlo en el futuro.
La Máquina de Turing se puede estudiar como un calculador de funciones o como reconocedorde lenguajes, la clase de los lenguajes se puede identificar con la clase de las funciones recursivas totales, y la clase de lenguajes recursivamente numerables se puede identificar con la clase de las funciones parciales.
La hipótesis de Church permite identificar las funciones computables con las recursivas parciales, es decir, se pueden diseñar Máquinas de Turing para calcular las funcionesrecursivas parciales, o dicho de otra forma, se pueden diseñar Máquinas de Turing que aceptan una cadena sí forma parte de un lenguaje recursivamente enumerable (de ahí que algunos autores denominen indistintamente a las funciones computables, como funciones Turing-computables o funciones Turing-aceptables).
Si una función es computable, se puede calcular su solución cuando exista. Y esa solución sepuede calcular mediante una Máquina de Turing. Está garantizado que será finito cuando la función es total, ya que se conoce su dominio de definición (para estos valores finalizará con éxito, para los demás finalizará con un error). Pero en una función parcial, el dominio de definición no está determinado. Por lo tanto, no siempre se podrá garantizar la finitud y corrección del proceso, solopara ciertos valores de los parámetros.
Si una función es total, existe al menos una Máquina de Turing que siempre se detiene, bien dando el resultado del cálculo, bien indicando la existencia de un error. Ese error sólo se dará si los parámetros no pertenecen al dominio de definición de la función. La situación equivalente, desde el punto de vista del reconocimiento de un lenguaje, es la cadena nopertenece al lenguaje.
Si una función es parcial existirá una Máquina de Turing de la que sólo se asegura que parará devolviendo el resultado del cálculo cuando los parámetros pertenecen al dominio de definición de la función. No se puede garantizar que ocurre en caso contrario. De nuevo, se establece un paralelismo evidente entre este comportamiento y lo que ocurre desde el punto de vista dereconocimiento del lenguaje.
Un Problema es un enunciado cierto o falso dependiendo de los valores de los parámetros que aparecen en su definición.
Sí el lenguaje asociado a un determinado problema es o no es recursivo, se puede saber si el problema es o no es decidible y si se puede o no garantizar la existencia de un algoritmo de ejecución finita. Es decir, se asocia la existencia de un algoritmo ala existencia de una Máquina de Turing que siempre pare, diciendo SI o NO. Y se usarán indistintamente ambos términos.
Se consideran problemas tratables aquellos problemas que se pueden resolver mediante algoritmos con comportamiento descrito por funciones polinómicas. Por lo tanto, puede resultar interesante agrupar en una misma “superclase” a todos los problemas tratables. Lo que sigue es ladefinición de esas clases, PSPACE, NPSPACE, P y NP, según que se trate de complejidad espacial o temporal, sobre Máquinas de Turing deterministas o no deterministas.
Si L es aceptado por una Máquina de Turing determinista con complejidad espacial polinómica, S(n) = aknk + ak−1nk−1 + . . . + a0, se dice que L está en la clase de lenguajes PSPACE. Si L es aceptado por una Máquina de Turing nodeterminista con cota espacial polinómica, se dice que L está en la clase NPSPACE.
Si L es aceptado por una Máquina de Turing determinista con complejidad temporal polinómica, T (n) = aknk + ak−1nk−1 +. . . + a0, se dice que L está en la clase de lenguajes P. Si L es aceptado por una Máquina de Turing no determinista con cota temporal polinómica, se dice que L está en la clase NP.
Si un problema se...