Martínez Ruíz, IvánMARTINEZ RUIZ, IVAN; 205993Altamirano Fernández, Luis Fernando2021-08-172021-08-172021-02https://hdl.handle.net/20.500.12371/14007“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.”pdfspaCIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRAOptimización matemáticaProgramación (Matemáticas)Algoritmos computacionalesFunciones computablesTesis de licenciaturaopenAccess