Estructuras desde el punto de vista de la teoría de la computabilidad
Date
2021-02
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
“La teoría de la computabilidad se centra en el estudio de la complejidad de los objetos matemáticos en función de la dificultad de dar un algoritmo para calcularlos. Después del trabajo fundacional en el área de Turing en 1936, hubo desarrollos de Kleene, Post, Turing, Church y Markov que sirvieron de base a la teoría. Algunos de estos resultados se pueden encontrar en [Dav]. En este trabajo tomamosalgunas de las definiciones básicas de allí y las modificamos para darle al lecto una mirada más completa. Otro enfoque que usa un tipo diferente de máquina se puede encontrar en [Cut]. En este trabajo modificamos una máquina de Turing añadiéndole direccionamiento indirecto y así convirtiéndola en una máquina de acceso aleatorio. También presentamos de manera formal las principales definiciones y resultados dados en [Cut]. Nuestros propósitos principales son: el mostrar la existencia de un programa universal, mostrar ejemplos explícitos de conjuntos no computables, introducir la noción de que un conjunto sea enumerado por una unción computable e introducir los grados de Turing.”
Description
Keywords
Citation
Collections
Document Viewer
Select a file to preview:
Can't see the file? Try reloading