Para depositar en Docta Complutense, identifícate con tu correo @ucm.es en el SSO institucional: Haz clic en el desplegable de INICIO DE SESIÓN situado en la parte superior derecha de la pantalla. Introduce tu correo electrónico y tu contraseña de la UCM y haz clic en el botón MI CUENTA UCM, no autenticación con contraseña.
 

Tecnicas de demostración de indecibilidad e inseparabilidad en teorías formales

Loading...
Thumbnail Image

Official URL

Full text at PDC

Publication date

2004

Defense date

2001

Advisors (or tutors)

Editors

Journal Title

Journal ISSN

Volume Title

Publisher

Universidad Complutense de Madrid, Servicio de Publicaciones
Citations
Google Scholar

Citation

Abstract

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

Research Projects

Organizational Units

Journal Issue

Description

Tesis de la Universidad Complutense de Madrid, Facultad de Filosofía, Departamento de Lógica y Filosofía de la Ciencia, leída el 23-11-2001

Unesco subjects

Keywords

Collections