Teoria de la computacion

INSTITUTO TECNOLOGICO CIUDAD VICTORIA

INGENIERIA EN SISTEMAS COMPUTACIONALES

Teoría de la Computación

Prof. : Ricardo Saldivar Espinoza

TEMA.-Unidad 5 & 6

RAUL DANIEL RAMIREZ CASTILLO 08380667

CIUDAD VICTORIA TAMAULIPAS 6 Junio de 2010

Índice del Contenido

Unidad 5 DECIBILIDAD…………………………………... | 4 |
5.1.-LenguajesDecidibles……………………………………….. | 5 |
5.2.-Los problemas de Halting………………………………….. | 7 |
5.3.-Decibilidad de Teorias Logicas……………………………. | 9 |
Unidad 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 |

Introduccion
La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas de acuerdo a su grado dedificultad.
Esta teoría explora los límites de la posibilidad de solucionar problemas mediante algoritmos. Gran parte de las ciencias computacionales están dedicadas a resolver problemas de forma algorítmica, de manera que el descubrimiento de problemas imposibles es una gran sorpresa. La teoría de la computabilidad es útil para no tratar de resolver algorítmicamente estos problemas, ahorrando asítiempo y esfuerzo.

UNIDAD 5 DECIBILIDAD
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 dedecidir en un número finito de pasos si la fórmula es válida o no en el sistema.
Por otra parte, una teoría decidible semánticamente, es un sistema axiomático donde existe un método para evidenciar que toda proposicion verdadera en un modelo es decidible o no en el sistema en concreto.
Ejemplo: La Lógica proposicional es decidible, porque existe para ella un algoritmo; la tabla de verdad tal quepara 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á 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 sintácticamente decidible si se limita a predicados con un solo argumento (ver cálculo de predicadosmonódicos). Si se incluyen predicados con dos o más argumentos, no es decidible.
Toda teoría completa recursivamente enumerable es decidible sintácticamente. Por otro lado, toda teoría que incluya aritmética básica es no decidible sintácticamente.

5.1 Lenguajes Decidibles
Un lenguaje decidible es aquel lenguaje L para el cual existe una maquina de Turing que le puede aceptar cualquier cadenawL.
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 los lenguajes 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. Por otro lado, pese a que lenguajes formales más...