Decibilidad y Reductibilidad

INGENIERÍA EN SISTEMAS COMPUTACIONALES

Teoría de la Computación

INVESTIGACIÓN

“Decibilidad Y Reducibilidad”

Asesor:

Presenta:

Cuarto Semestre

Tuxtepec, Oaxaca a 27 de mayo de 2011.
Índice

Introducción 3

UNIDAD 5
• 5 Dicibilidad 4

5.1 Lenguajes Decidibles. 5

5.2 El problema de Halting.
7

5.3 Decidibilidad de Teorías Lógicas.
9UNIDAD 6
• 6 Reducibilidad 10

6.1 Problemas insolubles para la teoría de lenguajes.

11

6.2 Un problema simple insoluble.
12

6.3 Funciones computables.
12

6.4 Reducibilidad de Turing.
14

Conclusión
15

Referencias Bibliográficas
15


Introducción

El presente trabajo, es una investigación a manera de ensayo de los temas de Decibilidad YReducibilidad; contando con todos los conceptos que estos conllevan para lograr su comprensión y práctica dentro de la vida cotidiana.
Ahora bien la Decibilidad es un conjunto de formulas dentro de un sistema lógico; el conjunto de formulas lleva pasos finitos, para llegar a resolver un problema, con simple lógica continua, como se realiza en un algoritmo en general en cualquier situación, tanto teóricamentecomo prácticamente.
Dentro de la Decibilidad, existe el lenguaje o la sintaxis y las teorías lógicas, que se utiliza para resolver dichos problemas lógicos, como el problema de Halting.

La Reducibilidad, en términos generales es reducir el problema generando otro problema a partir del primero y con su solución se resuelve también el primero, para la comprobación de estos se utilizan otrosconceptos, también los problemas insolubles y solubles de las teorías de lenguajes, funciones computables y reducibilidad de turing.

5.0 Decibilidad
• ¿Qué es la decibilidad?
Es 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 finitode pasos si la fórmula es válida o no en el sistema.
Ejemplo: La Lógica proposicional (se define una proposición como 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 formulasatómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos el algoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.
La lógica de primer orden es decidible si se limita a predicados con un solo argumento. Si se incluyen predicados con dos o más argumentos, no es decidible. Toda teoría completarecursivamente enumerable es decidible. Por otro lado, toda teoría que incluya aritmética básica es no decidible.
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 una cadena cualquiera es unteorema o no lo es.
También hay que mencionar que en 1936, un matemático británico, Alan Turing, publica un ensayo titulado: “Acerca de Números Computables con una Aplicación al Problema de le Decidibilidad” (de Hilbert). En ese ensayo, introduce su máquina “pensante” primitiva, madre de la ciencia de la computación.
Turing demuestra que problemas computables pueden ser resueltos por una máquina conuna cinta infinitamente larga, subdividida en pequeñas celdas cuadradas y con un dispositivo con un número definido de estados capaz de “leer” los símbolos “escritos” sobre esa cinta. En función del símbolo leído y del “estado” de la máquina, se puede escribir otro símbolo y modificar el estado de la máquina. Trivialmente, la máquina puede desplazarse sobre la cinta en ambos sentidos

5.1...