Computabilidad
La teoría de la computabilidad, junto con la teoría de autómatas y lenguajes
formales, es el fundamento de la informática teórica. Estudia los problemas de
decisión que pueden ser resueltos con un algoritmo o equivalentemente con una
máquina de Turing.
Existen cierto tipo de problemas que, se sabe, pueden resolverse exitosamente
mediante la aplicación de un algoritmo. Puede citarse como ejemplo la
determinación del máximo común divisor entre dos números enteros mediante el
algoritmo de Euclides o la determinación de los números primos, mediante la criba
de Eratóstenes. Se dice que estos problemas son algorítmicamente solubles.
Por otro lado, existe cierto tipo de problemas para los cuales no es posible encontrar
una solución algorítmica.
La teoría de la computabilidad tiene como objetivo encontrar maneras de
representar descripciones de procesos, de modo tal que se pueda asegurar si existe
o no una representación algorítmica viable para un problema dado.
Problemas y lenguajes
Decibilidad
El problema de la parada
Revisión del módulo
Descarga en PDF
Teleclase
Lección 1 de 6
Problemas y lenguajes
Puede afirmarse que un problema se describe con un lenguaje y que cuanto
más formal es el lenguaje, más precisa será la formulación del problema.
Existen diferentes tipos de problemas, que pueden clasificarse de la
siguiente manera:
Problemas de decisión
–
son problemas formulados como pregunta y tienen solo dos posibles
respuestas: SI / NO o, lo que es equivalente, VERDADERO / FALSO.
Pueden citarse como ejemplos determinar si un número natural dado es par o
impar, o dada una cadena arbitraria y un lenguaje regular, determinar si la cadena
pertenece o no al lenguaje.
Problemas de salida general
–
tienen respuestas que no pueden codificarse en solo dos situaciones; se dice que
las posibles respuestas son generales. Como ejemplos pueden citarse el cálculo
del promedio de una lista de números, la determinación del camino óptimo entre
dos ciudades, etc.
A su vez, tanto los problemas de decisión como los de salida general, tienen
subclasificaciones.
Los problemas de decisión se clasifican de la siguiente manera:
existe un algoritmo que, para
Decidibles toda instancia del problema,
devuelve la respuesta correcta.
existe un procedimiento que
Indecidibles solo da respuesta para algunas
instancias del problema
instancias del problema.
Por otra parte, los problemas de salida general se clasifican de la siguiente
forma:
existe un algoritmo que, para
Solubles toda instancia del problema,
devuelve la respuesta correcta.
existe un procedimiento que
Insolubles solo da respuesta para algunas
instancias del problema.
Todo problema de salida general, con un cierto grado de dificultad, se puede
transformar en un problema de decisión con el mismo grado de dificultad.
Desde el punto de vista de la computabilidad, los lenguajes formales se
clasifican de la siguiente manera:
Lenguajes recursivos
–
existe un algoritmo que determina, para cualquier cadena, si pertenece o no
pertenece al lenguaje. Corresponden a los lenguajes generados por gramáticas
regulares (tipo 3), gramáticas independientes del contexto (tipo 2) y gramáticas
dependientes del contexto (tipo 1), según la jerarquía de Chomsky.
Lenguajes recursivos enumerables
–
existe un procedimiento que solo acepta las cadenas que pertenecen al lenguaje,
pero para las que no pertenecen no siempre da respuesta. Corresponden a los
lenguajes generados por las gramáticas sin restricciones (tipo 0) de la jerarquía
de Chomsky.
El análisis del tipo de problema y lenguaje que lo describe permite determinar
si, al enfrentar un problema dado, es posible o no construir un algoritmo, y, en
caso de que sea posible, determinar el tiempo que tardará en dar una
respuesta (complejidad del algoritmo).
C O NT I NU A R
Lección 2 de 6
Decibilidad
El término decidible se refiere a la existencia de un método efectivo para
determinar si un objeto es miembro de un conjunto o no. Es decir, si existe un
algoritmo capaz de decidir en un número finito de pasos y en un tiempo
estimado.
Se dice que un problema es decidible si es posible encontrar una fórmula,
método o algoritmo que permitan determinar si cierta cadena pertenece o no
a una estructura.
Los lenguajes decidibles se definen como formados por cadenas calculables
mediante funciones recursivas; por esta razón, también se les llama
lenguajes recursivos.
Ahora, supongamos que se dispone de una máquina de Turing M y se
plantea el problema de determinar si una cadena específica pertenece o no
al lenguaje reconocido por M.
Sea M un autómata de Turing: ¿w ∈ L (M)?
Las posibles respuestas serán:
M termina en un estado final ⇒ w ∈ L (M)
M termina en un estado no final ⇒ w ∉ L(M)
M no termina ⇒ w ∉ L (M)
Un lenguaje L se define como recursivo si existe una máquina de Turing M
que, independientemente de la entrada, siempre llega a la condición de
parada y cumple con las siguientes condiciones:
Si w ∈ L ⇒ M termina en un estado final
Si w ∉ L ⇒ M termina en un estado no final
Un lenguaje L se define como recursivamente numerable si existe una
máquina de Turing M, tal que:
Si w ∈ L ⇒ M termina en un estado final
Si w ∉ L ⇒ M termina en un estado no final o M no termina.
Según las definiciones anteriores, en una primera aproximación, los
problemas pueden clasificarse sencillamente en:
Computables (o decidibles)
No computables (o no decidibles)
Identificar los problemas que son computables de los que no lo son tiene un
considerable interés, pues indica el alcance y los límites de la computabilidad
y, por ende, los límites teóricos de los ordenadores. Además de las
cuestiones sobre algoritmos, se han encontrado numerosos problemas
menos "generales" que han resultado ser no computables.
Como ejemplos de problemas no computables es posible citar:
El problema de la palabra para grupos
–
dado un subconjunto S de elementos de un grupo G, se trata de decidir si una
expresión compuesta por elementos de S y con las operaciones del grupo es
igual al elemento neutro del grupo.
El décimo problema de Hilbert
–
una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con
coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900,
cuestiona acerca de si hay un procedimiento efectivo que determine si una
ecuación diofántica tiene o no solución.
La decibilidad de las teorías lógicas
–
en lógica, puede demostrarse fácilmente que el cálculo proposicional es
decidible. Church y Turing demostraron, en 1936, que el cálculo de predicados no
lo es.
Por otro lado, son muchos los problemas interesantes que se han
demostrado computables. Todas las funciones construidas por recursividad
primitiva o minimalización a partir de funciones calculables resultan ser
calculables como consecuencia de los trabajos de Church y Turing.
C O NT I NU A R
Lección 3 de 6
El problema de la parada
El problema de la parada o problema de la detención para máquinas de
Turing consiste en lo siguiente: dada una máquina de Turing M y una palabra
w, determinar si M se detendrá cuando es ejecutada usando w como dato de
entrada. Alan Turing, en su famoso artículo, demostró que el problema de la
parada de la máquina de Turing es indecidible.
En términos modernos, el problema de la parada consiste en determinar si
dado un programa p y sus datos de entrada x, p eventualmente terminará en
un número finito de pasos o si entrará a un bucle infinito.
Como demostró Turing, el problema de la parada es no decidible: no hay
manera de decir, en un tiempo finito, si la ejecución de un programa dado,
con una entrada dada, terminará o no.
C O NT I NU A R
Lección 4 de 6
Revisión del módulo
Hasta acá aprendimos
Autómatas a pila
–
Un autómata a pila puede definirse como un autómata finito no determinista al
cual se le ha incorporado un bloque infinito de memoria que se gestiona como
una pila. Esta memoria le permite almacenar y recordar información aumentando,
de esta manera, su poder funcional. La transición de un estado al siguiente se
define en función del estado actual, el símbolo de entrada y el símbolo en el tope
de la pila.
Un autómata a pila es capaz de reconocer cadenas que pertenecen a lenguajes
independientes del contexto o tipo 2, según la jerarquía de Chomsky.
Autómatas a pila y gramáticas independientes del contexto
–
Un autómata a pila puede definirse como el modelo matemático de un sistema
capaz de recibir una cadena conformada por símbolos de un alfabeto de entrada
y determinar si esta cadena pertenece o no a determinado lenguaje. Por cada
gramática independiente del contexto existe un autómata a pila que reconoce las
cadenas del lenguaje por ella generado y, por lo tanto, dada una gramática G se
puede obtener el autómata a pila correspondiente.
Máquina de Turing
–
Una máquina de Turing representa un modelo idealizado de computación capaz
de almacenar y procesar información teóricamente infinita. Su definición marcó
un hito en la historia de la informática y es considerada como el origen de los
actuales ordenadores. Su modelado teórico, junto al análisis de la complejidad de
los algoritmos, permitió la categorización de los problemas computacionales de
acuerdo con su comportamiento.
Computabilidad
–
La teoría de la computabilidad, junto con la teoría de autómatas y lenguajes
formales, es el fundamento de la informática teórica. La computabilidad estudia
los problemas de decisión que pueden ser resueltos con un algoritmo o,
equivalentemente, con una máquina de Turing; y tiene como objetivo encontrar
maneras de representar descripciones de procesos, de modo tal que se pueda
asegurar si existe o no una representación algorítmica viable para un problema
dado.
C O NT I NU A R
Lección 5 de 6
Descarga en PDF
Módulo 4 - Lectura [Link]
257 KB
Lección 6 de 6
Teleclase
CLIP-Lenguajes formales y computabilidad-Módulo 4
MÁS INFORMACIÓN GOOGLE DRIVE
