Decidibilidad

UNIDAD 5.- DECIBILIDAD
Se dice que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es.
En lógica, el término decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de fórmulas.
Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todaslas fórmulas válidas en el sistema es decidible. Es decir, existe un algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límitesteóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas menos “generales” que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal.
5.1.- LENGUAJES DECIDIBLES
Son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajesrecursivos.
Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba.
Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos que, por ejemplo la palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándosefrecuentemente.
A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.
Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:
* Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
* Las frases sobre elalfabeto {a, b, c} que contienen igual número de letras a y b.
* Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que es el 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 la máquina se para enun tiempo finito al procesar esa entrada.
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras solamente pueden ejecutar algoritmos, esto es secuencia de instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente.
No es una sorpresa que esta idea intuitiva de algoritmo puedaser definida formalmente. El correspondiente modelo matemático se llama máquina de Turing (Alan Turing, 1936).
La teoría de computabilidad tiene como objetivo el estudio de problemas de decisión, con el fin de determinar si los mismos son teóricamente decidibles.
Los problemas se pueden clasificar desde el punto de vista de la teoría de computabilidad en resolubles y no resolubles. Losproblemas resolubles son objeto de estudio de la teoría de complejidad computacional.
En el contexto de complejidad computacional, el interés está centrado en establecer una medida de la cantidad de recursos computacionales (en términos de tiempo y/o espacio) necesarios para resolver un determinado problema o equivalentemente reconocer un lenguaje
LOS PROBLEMAS RESOLUBLES SE SUBDIVIDEN EN TRATABLES EINTRATABLES
Los problemas tratables son: Aquellos para los cuales existe un algoritmo eficiente que los resuelve.
Los intratables son: Aquellos para los cuales no se conoce (o tal vez no exista) un algoritmo eficiente que los resuelva
Lenguajes aceptables y decidibles
- Lenguaje decidible: es aquel lenguaje L para el cual existe una máquina de Turing que puede aceptar cualquier cadena...