Material académico dígital en pdf gratuito para estudiantes y profesores

LA REDUCCIÓN COMO JERARQUÍA ENTRE CONJUNTOS PDF TEORÍA Y EJEMPLOS RESUELTOS DE MATEMÁTICAS

Con algunos pasos que se realizan de manera mecánica y otros no tanto. Partiendo de un problema A cuya indecidibilidad queremos demostrar:
1. Tomamos un problema que sabemos indecidible (hasta ahora ha sido H en todos los casos) y sospechamos puede ser reducible a A.
2. Planificamos la construcción de un programa Q que resuelva el problema H, utilizando la supuesta computabilidad de A. Para ello Q debe determinar si un programa arbitrario Px converge sobre un dato cualquiera y.
Reducibilidad
Aunque los pasos que vamos a dar restringen algo el campo de aplicación del método, vamos a comprobar que si las funciones implicadas (tanto la incomputable de Partida como aquella cuyo estatuto desea ser probado) son predicados de un solo argumento12, podemos introducir algo de maquinaria teórica que nos permita enfocar el problema de encontrar una reducción en la consecución de la función h.

Related Posts Plugin for WordPress, Blogger...