Decibilidad

Decibilidad

1.- 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.

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í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.

5.1 Lenguajes Decidibles

Son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llamas lenguajes recursivos.

Existen problemas que no pueden ser resueltos por una computadora dado que las computadoras solamente pueden ejecutar algoritmos. 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 en resolubles y no resolubles. Los problemas resolubles son objeto de estudio de la teoría de complejidad computacional.

Los problemas resolubles se subdividen en tratables e intratables

> 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 y rechazar cualquier cadena.

> Lenguaje aceptable: es aquel lenguaje L para el cual no existe ninguna máquina de Turing que puede aceptar cualquier cadena y rechazar cualquier cadena.

> Lenguajes recursivamente innumerables: lenguajes estructurados por frases.

> Lenguajes recursivos: lenguajes decidibles por una máquina de Turing

Comparación entre lenguaje aceptable y lenguaje decidible

> Lenguaje aceptable

La máquina separa al reconocer una cadena

del lenguaje.

> Lenguaje decidible

La máquina dice si una cadena pertenece al

lenguaje o no.

Implica reconocer el complemento del lenguaje

¡Existen lenguajes aceptables que no son

decidibles!

Un lenguaje es aceptable pero su

complemento no.

2.- PROBLEMA DE LA PARADA el problema de parada para máquinas de Turing es el ejemplo de problema irresoluble más conocido. Se define así: Dado un programa y su entrada, decidir si ese programa terminará para esa entrada o si

...