Dfsdgfg

“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 todas las 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 sila fórmula es válida o no en el sistema”

•“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”.

Según las Definiciones Anteriores, podemos llegar a concluir que se tiene Decibilidad si podemos encontrar una fórmula, método o algoritmo que nos permita decidir si cierta cadena pertenece a unaestructura.

Como ya se había mencionado, la Decibilidad nos sirve en los lenguajes Formales, por lo tanto veremos cuáles son los Lenguajes y su Clasificación:

“Los lenguajes decidibles son cadenas de palabras calculables mediante funciones recursivas por lo cual también se les llama lenguajes recursivos”.

LENGUAJES DECIDIBLES
un lenguaje decidible es aquel lenguaje l para el cual existe unamaquina de turing que le puede aceptar cualquier cadena wl. hay lenguajes formados por cadenas tales que una maquina de turing logra un estado final con las cadenas que reconoce y acepta, solamente. en este caso se dice que la maquina de turing semidecide al lenguaje. los lenguajes semidecididos por una mt se llaman recursivos numerables. las gramáticas sin restricciones son las que generan loslenguajes recursivos numerables. de aquí en adelante será suficiente referirse a los lenguajes recursivos numerables, pues estos generalizan a los lenguajes recursivos, los cuales generalizan a los lenguajes libres de contexto, y estos a los lenguajes regulares. lo anterior tiene relación directa con que los autómatas de turing generalizan a los de la pila y estos a su vez a los autómatas finitos. porotro lado, pese a que lenguajes formales más generales que los recursivos numerables no son reconocidos por un automata de turing, no existe hasta el momento ningún autómata más poderoso capaz de reconocerlos.
en terminos de procedimientos, las cadenas de un lenguaje decidible corresponden a procedimientos que terminan, ya sea realizando lo que indica la palabra ó señalando que no tienen lacapacidad de realizarlo. para un lenguaje semidecidible, las cadenas decididas por la mt son instrucciones realizadas por la mt. de manera complementaria, las cadenas no decidibles por la mt corresponden a procedimientos que no terminan utilizando una maquina de turing. a partir de lo dicho aquí tenemos la definición de algoritmo:
* un algoritmo es una implementación de una maquina de turing talque el conjunto de sus entradas es el lenguaje decidible.
es decir, si un dado un conjunto de entradas bajo las cuales una mt logra un estado de parada para cada entrada, la maquina corresponde a la implementación de un algoritmo. esta es la tesis de church – turing. no es un teorema pues no se puede demostrar matemáticamente, de manera general y categórica. es solo la afirmación de que elconcepto informal del algoritmo corresponde a un objeto matemático. al ser solo una afirmación no demostrable, puede suceder que luego fuera refudada. para que esto ocurra, se necesitaría encontrar un autómata más potente que uno de turing tal que fuese la implementación de un algoritmo. si bien hay algunas propuestas interesantes que pretende generalizar a la mt, hasta la fecha ninguna de ellas hasido aceptada para sustituir nuestro actual concepto de procedimiento comprable.
por otro lado, mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable. por ello, son más los lenguajes no computables o indecidibles. una teoría lógica (tl) se define a partir de un conjunto de enunciados dados llamados axiomas, unas reglas de...