Decibilidad

INSTITUTO TECNOLOGICO SUPERIOR DE SAN ANDRES TUXTLA
CARRERA
ING SISTEMAS COMPUTACIONALES
UNIDAD VI
SEMESTRE 404
GRUPO B
PROFRA:
LILY ALEJANDRA MENDOZA MEDRANO
ALUMNA:
BRISIA CHACHA ARIAS

SANTIAGO TUXTLA VER

INTRODUCCION
Como parte de la Carrera de Ingeniería en Sistemas Computacionales, estudiamos lo que es Decibilidad ya que se utiliza en la Teoría de Autómatas y LenguajesFormales, todo esto dentro de lo que llamamos Teoría de la Computación. Por ello desarrollare este ensayo, para tener más claro este tema., para empezar definire que es la Decibilidad, sus áreas y formas de aplicación, para poder darnos una mejor idea de su utilidad. Aunque para poder entender este tipo de textos se deben de tener ciertos conocimientos previos, como saber que es y cómo funciona unaMaquina de Turing, y también conocimientos propios del lenguaje técnico de Teoría de la Computación.
•“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, existeun algoritmo tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema”. •“En otras palabras se puede decir que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito (quiere decir que deben estar establecidos cada uno de los estados que lo forman, en otras palabras el tiempo debe estar señalado) si unacadena cualquiera es un teorema o no lo es.
Según definición un sistema lógico o teoría es decidible si el conjunto de todas las fórmulas válidas en el sistema es decidible. Es decir, existe un algoricto tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
Ejemplo: La Lógica proposicional (se define una proposicióncomo un enunciado declarativo que puede ser verdadero o falso, y Las proposiciones se representan mediante variables proposicionales simbolizadas mediante letras) es decidible, porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula que combina M formulas atómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos el algoritmo siempre decidirá sila fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.
El concepto de problema indecidible o irresoluble se aplica a problemas de decisión, es decir, problemas a los que podemos decir si tienen solución o no. Dentro de estos problemas, existe un conjunto al que no le podemos asignar una respuesta, ni afirmativa ni negativa: no existe unalgoritmo que nos permita determinar si el problema tiene solución.
Una de las razones por la que es importante conocer que el problema de la parada no tiene solución, es que nos permite decidir si otros problemas son resolubles o no. El razonamiento a seguir sería: si suponiendo que un problema es decidible, podemos demostrar que el problema de la parada tiene solución, entonces podemos llegar a laconclusión de que el problema en cuestión no la tiene, por reducción al absurdo.

PROBLEMA DE HALTING
El problema de “Halting” es el primer problema indecidible mediante maquinas de Turing. Equivale a construir un programa que te diga si un problema de ordenador finaliza alguna vez o no (entrando a un bucle infinito, por ejemplo)
Básicamente, Turing definió las bases de las computadoras modernas yplanteo un problema sobre ellas, llegando a la conclusión de que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (Halting problem); el problema de saber si un problema se cuelga cuando corre en la computadora. Turing demostró que el problema de la detención es indicidible, es decir, demostró que había problemas que una maquina no podía resolver.
Es meritorio el hecho...