TC Trabajo de investigación.

Realizar una investigación del Estado del Arte de las Teorías de DECIBILIDAD Y REDUCIBILIDAD así como la aplicación de las mismas en la Teoría de la Computación (Lenguajes y Autómatas).
Entregar una carpeta digital conteniendo: una subcarpeta con el material investigado (archivos html, pdf, doc, etc.), una síntesis en Word 2003 y una presentación multimedia en power-point 2003.

Unidad 5.- Decibilidad.

5.1 Lenguajes Decidibles.
5.2 El problemas de Halting.
5.3 Decidibilidad de Teorías Lógicas.

Introducción:

Decidibilidad (Introducción)
De Wikipedia, la enciclopedia libre

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 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 la fórmula es válida o no en el sistema.

Ejemplo: La Lógica proposicional 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á 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 (ver cálculo de predicados monódicos). Si se incluyen predicados con dos o más argumentos, no es decidible.

Toda teoría completa recursivamente enumerable es decidible. Por otro lado, toda teoría que incluya aritmética básica es no decidible.

Lenguajes decideibles: http://webdiis.unizar.es/~elvira/lengForm.pdf
Lógica y Computación: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm
Lenguajes decidibles por una Máquina de Turing: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm
Problemas de decisión:
http://www2.ing.puc.cl/~jabaier/iic2212/decision.pdf
http://es.wikipedia.org/wiki/Problema_de_decisión
Demostración del problema del paro: http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf
Algoritmo de Inferencia Gramatical: http://www.uv.es/hmr/Tesis/HTML/

Unidad 6.- Reducibilidad.

6.1 Problemas insolubles para la teoría de
lenguajes.
6.2 Un problema simple insoluble.
6.3 Funciones computables.
6.4 Reducibilidad de Turing.

Complejidad Computacional: https://www.unoweb-s.uji.es/0304/IS17/ficheros0/theList/tema10.pdfIntroducciòn a la TCC: http://www3.uji.es/~martine/DOC/E45/apuntes/node47.htmlEnsayo TCC: http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/N1_2004/a14.pdfComo ganar a la Ruleta en 21 dias: http://www-2.dc.uba.ar/materias/plp/20052C/download/charla_figueira.pdfNP-Completitud: https://www.fdi.ucm.es/profesor/csegura/mtp0304/apuntes/NPcompletitud.pdf
Computabilidad y Algoritmos: http://juanfc.lcc.uma.es/EDU/EP/2.DescrAlgoritmos.pdf
Clases Polinómiales: http://delta.cs.cinvestav.mx/~gmorales/complex/node149.html
Presentación uniforme de la teória descriptiva de la complejidad computacional: http://www2.scielo.org.ve/scielo.php?script=sci_arttext&pid=S0001-55042002000200003&lng=pt...&nrm=iso

Otros enlaces de interes:
Sitio general de IA y Sistemas: http://pub.ufasta.edu.ar/ohcop/mapa.html