Decibilidad

Decibilidad
Algunas definiciones de Decibilidad:
* En lógica, el termino decidible se refiere a la existencia de un método efectivo para determinar si un objeto es miembro de un conjunto de formulas. Un sistema lógico o teoría es decidible sintácticamente si el conjunto de todas las formulas validas en el sistemas es decidible. Es decir, existe un algoritmo tal que para cada formula delsistema es capaz de decidir en un número finito de pasos si la formula es valida o no en el sistema.

* Se dice que un sistema formal es decidible si existe un algoritmo que diga en término finito si una cadena cualquiera es un teorema o no lo es.

* Dícese de la proposiciones de un sistema axiomático cuya verdad o falsedad puede demostrarse dentro del sistema.

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

Definición general acerca de los lenguaje formales y después una definición mas técnica para una mayor comprensión:
“Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobreeste 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ándose frecuentemente A diferencia de que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), unlenguaje puede estar compuesto por un numero infinito de palabras.
Estos son algunos ejemplos de problemas de decisión expresados como leguajes:
* Las frases sobre el alfabeto {a,b} que contienen alternadas las letras a y b.
* Las frases sobre el alfabeto {a,b,c} que contienen igual numero de letras a y b.
* Las frases que describen un grafo con aristas etiquetadas con números naturales queindican su longitud, dos vértices del grafo y un camino en el grafo que es el camino mas acorto entre esos dos vértices.
* Las frases que describen una maquina de Turing y una cinta d entrada para esta maquina tal que la maquina se para en un tiempo finito al procesar esa entrada.
Existen problemas que no pueden ser resueltos por una computadora, dado que las computadoras, dado que solamentepueden ejecutar algoritmos, esto e secuencia de instrucciones universalmente precisas y entendibles que resuelven cualquier instancia de problemas computacionales definidos rigurosamente,

Aquí presentamos una definición más formal:
“Sea M un autómata de Turing: ¿w ∈ L (M)?

Posibles respuestas:
1.M termina en un estado final ⇒ w ∈ L (M)
2.M termina en un estado no final ⇒ w∉L(M)
3.M notermina ⇒ w ∉L (M)

Es un lenguaje RECURSIVO si existe un autómata de Turing M que para ante cualquier entrada y tal que:
•Si w ∈ L ⇒ M termina en un estado final
•Si w∉L ⇒ M termina en un estado no final

L es un LENGUAJE RECURSIVAMENTE NUMERABLE
Si existe un autómata 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”.“Así, en una primera aproximación, los problemas pueden clasificarse en:
•Computables (o decidibles)
•No computables (o no decidibles)”

Un algoritmo indecidible:
Sea el siguiente algoritmo, debido a Lagarias (1985) :
Por ejemplo, si el valor inicial de X es 7, va tomando los valores:
7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

1 Entrar X
2 Mientras X≠1 hacer:
3 Si X es par, X = X/24 Si no, X = 3X +1
5 Parar

Sin embargo, no se puede demostrar que este algoritmo llegue siempre a pararse, para cualquier número positivo de entrada. Aunque tampoco puede demostrarse lo contrario: que exista algún número para el cual el algoritmo no se para nunca.

El problema de la parada:

Dado un programa (o algoritmo) A y un valor de la entrada X, ¿podemos saber siempre si A se...