Feto, si no has oído hablar de él, puedes leerlo aquí . Utiliza un sistema de 'matrices de llamadas' y 'gráficos de llamadas' para encontrar todos los 'comportamientos de recursividad' de llamadas recursivas en una función. Para mostrar que una función termina, muestra que todos los comportamientos...
Estoy buscando una prueba de que la complejidad de Kolmogorov es indiscutible utilizando una reducción de otro problema incontestable. La prueba común es una formalización de la paradoja de Berry en lugar de una reducción, pero debe haber una prueba reduciendo algo como el Problema de detención o...
Las funciones recursivas primitivas se definen sobre los números naturales. Sin embargo, parece que el concepto debería generalizarse a otros tipos de datos, permitiéndole hablar sobre funciones recursivas primitivas que mapean listas a árboles binarios, por ejemplo. Por analogía, las funciones...
En el artículo Relativizaciones de la P =? Pregunta NP , Baker et al. demostró que existen mundos relativizados en los que se mantiene P = NP o P ≠ NP. Todos los oráculos en su configuración eran conjuntos recursivos. En otro artículo relativo a un Oráculo aleatorio , P A ≠ N P A ≠ co- N P A con...
Un Quine es un programa de computadora que produce una copia de su propio código fuente como su única salida. ¿Hay algún programa de Quine que pueda imprimirse n veces, con n especificado de alguna manera en el
¿Podría recomendar un artículo de encuesta o un capítulo de libro de texto que presente la teoría de las funciones recursivas?
Estoy tratando de desarrollar algunas nociones de un cálculo de diferencia entre una máquina ideal de Turing ideal concebida por un desarrollador (por ejemplo, lo que sea que pretenda un desarrollador de software), llámelo y las máquinas que representan el software que realmente se diseñó y...
Muchos resultados en criptografía dependen de resultados / conjeturas imposibles en la teoría de la complejidad. Por ejemplo, se cree que la criptografía de clave pública que usa RSA es posible debido a la conjetura sobre la inviabilidad de la factorización (y los problemas de búsqueda de raíz...
El lenguaje de los whileprogramas puede expresar las funciones computablemente enumerables. (Esto es cierto incluso si las únicas operaciones aritméticas en variables son, por ejemplo, incremento y decremento). Si whilese reemplaza por forhacer bucles siempre delimitados, el lenguaje solo puede...
¿Existe una generalización del juego GO que se sabe que está completa? En caso negativo, ¿tiene alguna sugerencia sobre reglas razonables (de generalización) que puedan usarse para tratar de demostrar que está completa? La obvia es que el juego debe jugarse en un tablero infinito (cuadrante...
Me he estado preguntando por un tiempo sobre el origen de los nombres "inmunes" y "simples". También le hice la misma pregunta a Andrea Sorbi, quien a su vez involucró a algunos colegas más en la discusión. Sobre "simple" tenemos algunas conjeturas. Martin Davis sugiere que el nombre deriva de una...
En Computabilidad, si queremos demostrar que un problema no es recursivo o recursivamente enumerable, podemos usar, por ejemplo, reducciones de otros problemas no recursivos o no re, el teorema de Rice, el teorema de Rice-Shapiro, etc. Estas técnicas funcionan gracias a , o se basan directamente en...