Decibilidad
Enviado por alonsopadron • 30 de Agosto de 2013 • 384 Palabras (2 Páginas) • 546 Visitas
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.
...