Jerarquía aritmética de Kleene
Este trabajo está organizado en tres capítulos, en el primer capítulo, revisamos algunos conceptos fundamentales como las funciones primitivas, utilizadas por Godel en 1930 en su Teorema de incompletitud, la noción de funciones primitiva-recursivas, funciones básicas, predicados primitivo-recursivos...
| Autor Principal: | Martínez V., Iveth Verónica |
|---|---|
| Formato: | Tesis |
| Idioma: | Español |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: |
http://up-rid.up.ac.pa/272/ http://up-rid.up.ac.pa/272/2/iveth%20martinez |
| Sumario: |
Este trabajo está organizado en tres capítulos, en el primer capítulo, revisamos algunos conceptos fundamentales como las funciones primitivas, utilizadas por Godel en 1930 en su Teorema de incompletitud, la noción de funciones primitiva-recursivas, funciones básicas, predicados primitivo-recursivos, la enumeración de Godel importante para el desarrollo del trabajo y las funciones recursivas en algunos casos Ramada funciones computables. Fuertemente asociado con las funciones recursivas, están los conceptos de los conjuntos recursivamente innumerables y los conjuntos recursivos revisados en el segundo capítulo. Además definimos la reducibilidad de conjuntos, revisamos las relaciones entre los conjuntos completos, productivos, creativos, cilindros, inmunes y simples. Se presenta los conjuntos de índices que corresponden a problemas naturales indecidibles relacionados con las funciones recursivas: K, Ko, Kl, Inf, Fin, Rec, Con, Cof, Ext, Subset y Tot y un interés en el grado de irresolubilidad de los conjuntos Crea, Simp y Comp. La clasificación de los conjuntos definidos en el segundo capítulo, es desarrollada en el tercer capítulo, momento en que la lógica juega un papel importante para el logro del mismo. Además se establece la noción de Turing-reducible y los grados de irresolubilidad asociados. Importante para este tema es el estudio de los métodos "finite-infinite injury priority", creado por Shoenfield (1961) y Sacks (1963-1964) de forma independientemente. |
|---|