Hay teoría algorítmica de grafos / teoría de números / combinatoria / teoría de la información / teoría de juegos. ¿Existe un análisis matemático algorítmico? Según wiki, el análisis matemático incluye las teorías de diferenciación, integración, medida, límites, series infinitas y funciones...
¿Alguien sabe de un conjunto de problemas que varían uniformemente y abarcan una de las jerarquías "interesantes" de complejidad y computabilidad? Por interesante, quiero decir, por ejemplo, la Jerarquía Polinómica, la Jerarquía Aritmética o la Jerarquía Analítica. O tal vez (N) P, (N) EXP, 2 (N)...
Pregunta : ¿Es tan difícil predecir (como se define a continuación) las secuencias computables como el problema de detención? Elaboración : "Predecir" significa predecir con éxito, lo que significa cometer solo un número finito de errores en la tarea de intentar predecir el enésimo bit de la...
Harvey Friedman demostró que hay un claro resultado de punto fijo que no se puede probar en ZFC (la teoría de conjuntos Zermelo-Frankel habitual con el Axioma de Elección). Muchas lógicas modernas se basan en operadores de punto fijo, así que me preguntaba: ¿hay alguna consecuencia conocida del...
Considere el siguiente juego de 2 jugadores: La naturaleza elige un programa al azar Cada jugador juega un número en [0, infinito] inclusive en respuesta al movimiento de la naturaleza Tome el mínimo de los números de los jugadores y ejecute el programa durante (hasta) tantos pasos (a menos que...
A menudo escuché decir que no se puede escribir un programa para detectar errores en un navegador web, procesador de texto o sistema operativo, debido al Teorema de Rice: cualquier propiedad semántica para un lenguaje completo de Turing es indecidible. Sin embargo, no estoy seguro de hasta qué...
Deje HALTnHALTnHALT_n denotar la cadena de longitud 2n2n2^n correspondiente a la tabla de verdad del problema de detención para entradas de longitud nnn . Si la secuencia de las complejidades de Kolmogorov K(HALTn)K(HALTn)K(HALT_n) fuera O(1)O(1)O(1) , una de las cadenas de consejos se usaría...
¿Existe una noción de computabilidad en conjuntos distintos de los números naturales? En aras de la discusión, digamos en los conjuntos que se biject con .NSSSNN\mathbb{N} Es tentador decir "sí, son aquellas funciones de la forma donde es cualquier biyección y es cualquier función computable "....
Esta pregunta es acerca de si hay alguna lona de Turing reversible conocida, donde "reversible" significa en el sentido de Axelsen y Glück , y "tarpit" es un concepto mucho más informal (y podría no ser una muy buena elección de palabra), pero haré todo lo posible para explicar lo que quiero decir...
Los problemas han sido, en su conjunto, clasificados, gracias a la Complejidad Computacional. Pero, en ecuaciones diferenciales, ¿es posible clasificar las ecuaciones diferenciales en función de su estructura computacional? Por ejemplo, si una ecuación no homogénea de primer orden es...
Cerrado. Esta pregunta está fuera de tema . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que sea sobre el tema para el intercambio teórico de pila de informática. Cerrado hace 3 años . ¿Existe...
Del teorema de Rice se deduce que no se puede determinar si dos máquinas de Turing deciden o no el mismo idioma. Mi pregunta es: ¿Esto también se aplica en configuraciones de complejidad descriptiva, particularmente cuando se trata de probar un par de consultas SO-Horn para ver si describen el...
Ejemplos bien conocidos de computación inspirada en fenómenos naturales son las computadoras cuánticas y las computadoras de ADN. ¿Qué se sabe sobre el potencial y / o las limitaciones de la informática con las leyes o la gravedad de Maxwell? Es decir, ¿incorporar las soluciones "rápidas" de la...
Tengo una pregunta, cuya respuesta es probablemente conocida, pero parece que no puedo encontrar nada significativo después de un poco de búsqueda, por lo que agradecería un poco de ayuda. Mi pregunta es si se sabe que decidir si un número es trascendental es indecidible. Posiblemente, uno asume...
Supongamos que no conocemos el resultado de Joe B. Wells de 1994 de que tanto la tipificación como la verificación de tipo son indecidibles en el Sistema F (AKA ). En los cálculos Lambda con tipos de Barendregt (1992) encontré una prueba debido a Malecki 1989 de que la verificación de tipos implica...
Intrigado por la interesante pregunta de Chris Pressey sobre funciones recursivas elementales , estaba explorando más y no pude encontrar una respuesta a esta pregunta en la web. Las funciones recursivas elementales corresponden muy bien a la jerarquía exponencial,
Encontré la siguiente pregunta, que es un ejercicio fácil (spoiler a continuación). Se nos dan instancias del problema de detención (es decir ), y debemos decidir exactamente cuál de ellas se detendrá en . Es decir, necesitamos generar . Se nos da un oráculo para el problema de detención, pero...
Hay problemas que son decidibles, hay algunos que son indecidibles, hay semidecidabilidad, etc. En este caso, me pregunto si un problema puede ser metadecidible. Esto significa (al menos en mi cabeza) que no podemos decir si es decidible o no. Tal vez se sabe que la capacidad de decisión es...
¿Existe algún sistema similar al cálculo lambda que sea fuerte normalizando, sin la necesidad de agregar un sistema de tipo
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...