Preguntas relacionadas con la teoría de la computabilidad, también conocida como teoría de la recursividad
No entiendo por qué el problema de detención se usa con tanta frecuencia para descartar la posibilidad de determinar si un programa se detiene. La Wikipedia [artículo] [1] explica correctamente que una máquina determinista con memoria finita detendrá o repetirá un estado anterior. Puede usar el...
Nos dieron el siguiente ejercicio. Dejar f(n)={100n occurs in the decimal representation of πelsef(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}...
Sabemos que el problema de detención (en máquinas de Turing) es indecidible para las máquinas de Turing. ¿Hay alguna investigación sobre qué tan bien la mente humana puede manejar este problema, posiblemente ayudado por las máquinas de Turing o las computadoras de uso general? Nota : Obviamente,...
¿Existe un conjunto de construcciones de lenguaje de programación en un lenguaje de programación para que pueda considerarse Turing Complete? Por lo que puedo decir de Wikipedia , el lenguaje debe admitir la recursividad o, al parecer, debe poder ejecutarse sin detenerse. ¿Es esto todo lo que hay...
La coincidencia de patrones de alto orden es un problema indecidible. Eso significa que no existe un algoritmo que, dada una ecuación a => b, donde ay bson términos abiertos en el cálculo lambda simplemente tipeado, encuentre una sustitución Stal que aS => bS, donde =>significa "tiene la...
Me encontré con un problema extraño al escribir un intérprete que (debería) engancharse a programas / funciones externas: las funciones en 'C' y 'C ++' no pueden conectar funciones variadas , por ejemplo, no puedo hacer una función que llame a 'printf' con exactamente los mismos argumentos que...
He estado viendo todo el desbordamiento de la pila, por ejemplo, aquí , aquí , aquí , aquí , aquí y algunos otros que no me importa mencionar, que "cualquier programa que use la recursión puede convertirse en un programa usando solo la iteración". Incluso hubo un hilo muy votado con una respuesta...
En esta respuesta se menciona Un lenguaje normal puede ser reconocido por un autómata finito. Un lenguaje sin contexto requiere una pila, y un lenguaje sensible al contexto requiere dos pilas (lo que equivale a decir que requiere una máquina Turing completa) . Quería saber sobre la verdad de...
En la teoría de la computabilidad y la complejidad (y quizás en otros campos), las reducciones son ubicuas. Hay muchos tipos, pero el principio sigue siendo el mismo: demuestre que un problema es al menos tan difícil como otro problema al mapear instancias de a soluciones equivalentes en ....
Estaba tratando de explicarle a alguien que C es Turing completo, y me di cuenta de que en realidad no sé si es, de hecho, técnicamente Turing completo. (C como en la semántica abstracta, no como en una implementación real). La respuesta "obvia" (más o menos: puede abordar una cantidad arbitraria...
¿Hay máquinas teóricas que excedan la capacidad de las máquinas de Turing en al menos algunas
Resumen: Según el teorema de Rice, todo es imposible. ¡Y sin embargo, hago cosas supuestamente imposibles todo el tiempo! Por supuesto, el teorema de Rice no dice simplemente "todo es imposible". Dice algo más específico: "Cada propiedad de un programa de computadora no es computable". (Si...
Sé que Idris tiene tipos dependientes pero no está completo. ¿Qué no puede hacer al renunciar a la integridad de Turing, y esto está relacionado con tener tipos dependientes? Supongo que esta es una pregunta bastante específica, pero no sé mucho sobre los tipos dependientes y los sistemas de tipos...
Al ver que en la Jerarquía de Chomsky, los lenguajes Tipo 3 pueden ser reconocidos por una máquina de estado sin memoria externa (es decir, un autómata finito), el Tipo 2 por una máquina de estado con una sola pila (es decir, un autómata pushdown) y el Tipo 0 una máquina de estados con dos pilas...
Este programa de 579 bits en el cálculo binario de Lambda tiene un estado de detención
Estoy planeando enseñar un curso de invierno sobre un número variable de temas, uno de los cuales será compiladores. Ahora, me encontré con este problema mientras pensaba en tareas para dar durante el trimestre, pero me tiene perplejo, por lo que podría usarlo como un ejemplo. public class...
¿Existe algún cálculo lambda tipificado completo de Turing? Si es así, ¿cuáles son algunos
Me pregunto si hay un buen ejemplo para un problema NP-Hard fácil de entender que no sea NP-Complete y no sea indecidible. Por ejemplo, el problema de detención es NP-Hard, no NP-Complete, pero es indecidible. Creo que esto significa que es un problema que puede verificarse una solución, pero no...
Estaba pasando por la discusión sobre la pregunta ¿Cómo definir las máquinas cuánticas de Turing? y siento que la TM cuántica y la TM no determinista son lo mismo. Las respuestas a la otra pregunta no tocan eso. ¿Son estos dos modelos uno y el mismo? Si no, ¿Cuáles son las diferencias entre...
El teorema de Rice nos dice que las únicas propiedades semánticas de las máquinas de Turing (es decir, las propiedades de la función calculada por la máquina) que podemos decidir son las dos propiedades triviales (es decir, siempre verdaderas y siempre falsas). Pero hay otras propiedades de las...