Decibilidad

0
I n s t i t u t o T e c n o l ó g i c o
S u p e r i o r d e U r u a p a n
T e o r í a d e l a
C o m p u t a c i ó n
P r o f a . N e t z e y l e
A p ó d a c a R o d r í g u e z
C u a r t o S e m e s t r e
M a y o d e l 2 0 1 0

Breve ensayo sobre DECIBILIDAD.
Unidad V
“Decibilidad”
1
“INTRODUCCIÓN”
Como parte de la Carrera de Ingeniería en Sistemas
Computacionales, estudiamos loque es Decibilidad ya que se utiliza en
la Teoría de Autómatas y Lenguajes Formales, todo esto dentro de lo
que llamamos Teoría de la Computación. Por ello desarrollaremos este
ensayo, no tanto como un trabajo de la materia, sino para que tener
más claro este tema.
Vamos a Definir que es la Decibilidad, sus áreas y formas de aplicación,
para poder darnos una mejor idea de su utilidad. (Faltadefinir mejor).
Aunque para poder entender este tipo de textos se deben de tener
ciertos conocimientos previos, como saber que es y cómo funciona una
Maquina de Turing, y también conocimientos propios del lenguaje
técnico de Teoría de la Computación.
“LENGUAJES DECIDIBLES”
En este Ensayo citaremos algunas definiciones de Decibilidad para una
mayor comprensión de este texto:
•“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 si lafó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”.
2
•“DECIDIBLE: adj. Log .Mat .Dícese de las proposiciones de un
sistema axiomático cuya verdad o falsedad puede demostrarse
dentro del sistema”.
Según las Definiciones Anteriores, podemos llegar a concluir que setiene
Decibilidad si podemos encontrar una fórmula, método o algoritmo que
nos permita decidir si cierta cadena pertenece a una estructura.
Entrando en materia, los lenguajes decidibles son cadenas de palabras
calculables mediante funciones recursivas por lo cual también se les
llama lenguajes recursivos.
Un posible alfabeto sería {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 (ósea, la cadena de longitud cero) se permite en este
tipo de lenguajes, notándose frecuentemente A diferencia que ocurre
con el alfabeto (que es un conjunto finito) y con cada palabra (que
tieneuna longitud también finita).
Estos son algunos ejemplos de problemas de decisión expresados como
lenguajes:
· Frases del alfabeto {a, b} que contienen alternadas las letras a y
b.
· Frases del alfabeto {a, b, c} que contienen igual número de letras
a y b.
· 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 en un
tiempofinito al procesar esa entrada.
3
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.
También podríamos agregar que un Lenguaje decidible, es aquel para
el cual existe una máquina de Turing que puede aceptar cualquier
cadena (aba) y rechazar cualquier cadena (aba).
La máquina dice si una cadenapertenece al lenguaje o no, esto
implica reconocer el complemento del lenguaje. Existen lenguajes
aceptables que no son decidibles. En este caso, un lenguaje es
aceptable pero su complemento no.
Pero, Qué es un lenguaje aceptable? Es aquel para el cual no existe
ninguna máquina de Turing y puede aceptar y rechazar cualquier
cadena (abab). En dicho caso, La máquina separa al reconocer una...