FUNCIONES RECURSIVAS

Autor: CORDÓN FRANCO ANDRES.
Año: 2002.
Universidad: SEVILLA .
Centro de lectura: MATEMÁTICAS.
Centro de realización: FACULTAD DE MATEMÁTICAS.

Resumen: El presente trabajo se enmarca dentro del campo de estudio de los Modelos de la Aritmética de Peano: PA. En líneas generales, se desarrolla un estudios sistemático de Fragmentos de la Aritmética empleando como metodología el análisis de la complejidad de sus extensiones. Para medir la complejidad de una extensión, se consideran dos criterios: (--) La complejidad sintáctica de sus axiomas. (--) La complejidad descriptiva, desde el punto de vista computacional, del conjunto de sus axiomas. En la primera parte del trabajo, refinamos propiedades conocidas sobre estructuras de elemenos definibles, prestando especial atención a aquellos resultados que establecen que en dichas estructuras no son válidos esquemas de inducción o colección. Estos refinamientos son esenciales para obtener propiedades óptimas sobre existencia de extensiones de fragmentos de una cierta complejidad. En la parte central del trabajo, se obtienen resultados (en muchos casos óptimos) sobre la complejidad sintáctica y descriptiva de extensiones de framentos. Clásicos de la Aritmética (esto es, los obtenidos al restringir los principios de inducción, colección o minimización a fórmulas $\Sigma-n$ o $\Pi-n$). En la tercera parte del trabajo, se emplean los resultados sobre extensiones anteriores para estudiar Fragmentos Relativizados, es decir, los fragmentos de la Aritmética obtenidos al restringir los principios de inducción, colección, o minimización a fórmulas $\Delta-n(T)$ (esto es, fórmulas $\Sigma-n$ equivalentes a una fórmula $\Pi-n$ y tales que la teoría T demuestra dicha equivalencia). Dichos esquemas habían sido considerados previamente por Fernández Margarit y Lara Martín en relación al estudio del problema de Jeff Paris sobre la equivalencia de los fragmentos de inducción y minimización para fórmulas $\Delta-n$. Una de las aportaciones más novedosas del presente trabajo es que se proporciona una nueva metodología para el estudio de los Fragmentos Relativizados: el análisis de sus extensiones. En líneas generales, esta nueva metodología permite reducir el estudio de propiedades de Fragmentos Relativizados al estudio de extensiones de complejidad acotada de los Fragmentos Clásicos. Mediante el método propuesto, se desarrolla un estudio sistemático de Fragmentos Relativizados. Se estudian para estas teorias propiedades habituales en el estudio de Fragmentos de la Aritmética tales como: relaciones entre Fragmentos Relativizados, relaciones entre Fragmentos Clásicos y Fragmentos Relativizados, resultados de conservación, resultados de axiomatización (complejidad axiomática, teoráis finitamente axiomatizables), etc.

Autor: GALLEGO CASTAÑO ENRIQUE.
Año: 2001.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: FILOSOFIA.
Centro de realización: FACULTAD DE FILOSOFIA.

Resumen: El objetivo de esta memoria es analizar las tecnicas para la demostracion de la indecidibilidad de las teorias que aparecen habitualmente en Matematicas: teoria de grupos, teoria de anillos, teoria de grafos, etc. Los teoremas fundamentales de indecidibilidad se obtuvieron en la decada de 1930 por Church, TuringG, Godel y Rosser. Posteriormente se obtuvieron nuevos resultados de indecidibilidad utilizando la idea de Tarski de interpretar unas teorias en otras. Revisamos los conceptos fundamentales y presentamos formas refinadas de los principales resultados. Pero el metodo de Tarski no es adecuado para teorias con modelos finitos. Una alternativa es considerar la cuestion utilizando la nocion de inseparabilidad, mas general que la de no recursividad. El punto de partida es la inseparabilidad finita del calculo de predicados de primer orden. Simplificamos la demostracion de Buchi al utilizar maquinas de registros y un teorema de Minsky. Damos una forma fuerte de un teorema, utilizado por Rabin y Ershov, que nos permite demostrar la inseparabilidad finita de diversas teorias.

Autor: FERNANDEZ-COMBARRO ALVAREZ ELIAS.
Año: 2000.
Universidad: OVIEDO.
Centro de lectura: MATEMATICAS .
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: En esta memoria se usan conceptos algebraicos para estudiar objetos de la teoria de la computabilidad. Asi, se construyen numeraciones (es decir, codificaciones de conjuntos mediante numeros naturales cuyo semigrupo de endomorfismos es minimo en algun sentido y se caracterizan las numeraciones negativas mediante una clase de sistemas de ecuaciones. Tambien se estudian los automorfismos de la funcion universal computable, mostrando que todos ellos son recursivos.

Autor: LARA MARTIN FRANCISCO FELIX.
Año: 1999.
Universidad: SEVILLA .
Centro de lectura: MATEMATICAS.
Centro de realización: FACULTAD DE MATEMATICAS.

Resumen: En este trabajo se realiza un analisis de la conjetura de Friedman-Paris, acerca de la equivalencia entre los fragmentos de la Aritmetica de Peano obtenidos al restringir los esquemas de induccion y minimacion a Formula An+1. Para ello se consideran varias versiones de la conjetura y se estudian condiciones suficientes( y en ocasiones tambien necesarias) para que se de la equivalencia buscada en cada caso. Se estudian diversas relativizaciones de los esquemas axiomáticos para fórmulas An+1, en los que se exige que la equivalencia entre las Formulas n+1 y n+1 se pruebe en una teoria dada(con esto se sustituye la parte semántica de los esquemas que describen la conjetura de Friedman-Paris, por una condición sintactica). Como una segunda aproximacion a la conjetura se estudian las n+2 conscuencias de una teoria, considerando la posibilidad de describirlas mediante una familia de funciones no decrecientes de grafo in-definible.

Autor: GAVILANES FRANCO ANTONIO.
Año: 1989.
Universidad: COMPLUTENSE DE MADRID.
Centro de lectura: MATEMATICAS.
Centro de realización: FACULTAD DE MATEMATICAS DE LA UNIVERSIDAD COMPLUTENSE DE MADRID.

Resumen: EL OBJETIVO DE LA TESIS ES DAR UNA NUEVA FUNDAMENTACION LOGICA A LAS FUNCIONES PARCIALES COMPUTABLES. EN EL CAPITULO PRIMERO SE INTRODUCE UN NUEVO VALOR BOOLEANO INDEFINIDO CON EL QUE SE EXTIENDEN LAS NOCIONES CLASICAS DE VALOR DE UNA FORMULA Y DE CONSECUENCIA LOGICA. EN EL CAPITULO SEGUNDO SE PRESENTA LA LOGICA LFP (LOGICA DE PRIMER ORDEN PARA FUNCIONES PARCIALES CON TERMINOS CONDICIONALES), Y SE ESTUDIA LA COMPLETITUD DE LOS CALCULOS DE SECUENCIAS DE ESTA LOGICA POR EL METODO DE LOS TABLEAUX CON LA CONSTRUCCION DE UN MODELO "AL ESTILO DE HINTIKKA". EN EL CAPITULO TERCERO SE EXTIENDE LFP A LFRP (LOGICA DE PRIMER ORDEN PARA FUNCIONES RECUSRIVAS PARCIALES). SE EMPLEA EL METODO DE LOS TABLEAUX PARA OBTENER CONDICIONES DE COMPLEETITUD DE UN MODO SEMEJANTE AL DEL CAPITULO ANTERIOR. EN ESTE CASO LOS CALCULOS SON INFINITARIOS Y LA LOGICA PIERDE UNA PROPIEDAD IMPORTANTE DE LA LOGICA DE PRIMER ORDEN AL NO SATISFACER EL TEOREMA DE FINITUD. EN EL CAPITULO CUARTO SE APLICA LFRP AL ESTUDIO DE LA SEMANTICA DE UN LENGUAJE IMPERATIVO, DE TIPO ALGOL, Y SE MUESTRA COMO LFRP TIENE TANTA POTENCIA EXPRESIVA COMO OTRAS LOGICAS USADAS PARA PROGRAMAS IMPERATIVOS.

Autor: CAMPOS ROSELLO FRANCISCO JOSE.
Año: 1982.
Universidad: VALENCIA.
Centro de lectura: FILOSOFIA Y CIENCIAS DE LA EDUCACION.

Resumen: SE ESTABLECEN LA CONDICIONES QUE HA DE SATISFACER UN ALGORITMO; SE INTRODUCEN LOS CONCEPTOS BASICOS DE LA TEORIA DE FUNCIONES RECURSIVAS; SE DESARROLLAN DOS PROCEDIMIENTOS (ALGORITMO) DE RECURSION (AKLGOREC I II) PARA LA DECISION DE SI UNA FUNCION DADA (CATALOGADA O NO) ES O NO RECURSIVA.