La máquina de Turing es un modelo fundamental de computación, especialmente en trabajos teóricos.
¿Existe una relación entre la Máquina de Turing y el cálculo Lambda, o simplemente surgieron al mismo
Tengo tres preguntas secundarias relacionadas, que se destacan con viñetas a continuación (no, no se pueden dividir, si se lo pregunta). Andrej Bauer escribió, aquí , que algunas funciones son realizables a través de una máquina de Turing, pero no a través del cálculo lambda. Un paso clave de su...
Tengo entendido que el modelo de Turing se ha convertido en el "estándar" al describir el cálculo. Me interesa saber por qué este es el caso, es decir, por qué el modelo TM se ha vuelto más utilizado que otros modelos teóricamente equivalentes (que yo sepa), por ejemplo, μ-Recursion de Kleene o el...
Las computadoras reales tienen memoria limitada y solo un número finito de estados. Por lo tanto, son esencialmente autómatas finitos. ¿Por qué los informáticos teóricos usan las máquinas de Turing (y otros modelos equivalentes) para estudiar computadoras? ¿Cuál es el punto de estudiar estos...
¿Se pueden calcular todas las funciones que es computable en el tiempo en una máquina Turing de una sola cinta usando un alfabeto de tamaño tiempo en una máquina de Turing de una sola cinta usando un alfabeto de tamaño (digamos, y en blanco)?t k = O ( 1 ) O ( t ) 3 0 , 1 ,F: { 0 , 1 }∗→ { 0 , 1...
Estoy buscando una respuesta definitiva sobre si la generación de números "verdaderamente aleatorios" es computable por Turing. No sé cómo expresar esto con precisión. Esta pregunta de StackExchange sobre "algoritmos eficientes para la generación de números aleatorios" se acerca a responder mi...
Paul Wegner y Dina Goldin han publicado durante más de una década documentos y libros argumentando principalmente que la tesis de la Iglesia-Turing a menudo se tergiversa en la comunidad de Teoría del CS y en otros lugares. Es decir, se presenta como que abarca todo el cómputo cuando, de hecho,...
En la introducción y explicación, las clases de complejidad P y NP a menudo se dan a través de la máquina Turing. Uno de los modelos de computación es el cálculo lambda. Entiendo que todos los modelos de computación son equivalentes (y si podemos introducir algo en términos de máquina de Turing,...
Si se restringe Turing Machines a una cinta finita (es decir, para usar el espacio limitado ), entonces el problema de detención es decidible, esencialmente porque después de varios pasos (que pueden calcularse a partir del número de estados Q y S , y el tamaño del alfabeto), se debe repetir una...
Quiero codificar una máquina simple de Turing en las reglas de un juego de cartas. Me gustaría convertirlo en una máquina universal de Turing para demostrar su integridad. Hasta ahora, he creado un estado de juego que codifica la máquina Turing de 2 estados y 3 símbolos de Alex Smith . Sin...
Una computadora que recibe un flujo infinito de bits verdaderamente aleatorios es más poderosa que una computadora sin una. La pregunta es: ¿es lo suficientemente potente como para resolver el problema de detención? Es decir, ¿puede una computadora probabilística determinar si un programa...
Si seguimos el libro (o cualquier otra versión de la especificación del lenguaje si lo prefiere), ¿cuánta potencia computacional puede tener una implementación de C? Tenga en cuenta que "implementación C" tiene un significado técnico: es una instanciación particular de la especificación del...
En este artículo de Wikipedia sobre la integridad de Turing establece que: El cálculo lambda no tipificado es Turing completo, pero muchos cálculos lambda tipificados, incluido el Sistema F, no lo son. El valor de los sistemas mecanografiados se basa en su capacidad para representar la mayoría...
Sabemos que (véanse, por ejemplo, los Teoremas 1 y 3 de [1]), en términos generales, en condiciones adecuadas, las funciones que pueden calcularse eficientemente por la máquina de Turing en tiempo polinómico ("eficientemente computable") pueden expresarse mediante redes neuronales polinómicas con...
Supongamos que quisiera formalizar la prueba de Turing sobre el problema de detención para que una máquina pueda verificarlo. Algunos de los sistemas de prueba de teoremas automatizados conocidos incluyen Mizar, Coq y HOL4. Descargué y experimenté con Coq, pero no tiene una biblioteca para máquinas...
Arreglemos una codificación sin prefijo de máquinas de Turing y una máquina universal de Turing que en la entrada (codificada como el código sin prefijo de seguido de ) emite salidas de en la entrada (posiblemente ambos corriendo para siempre). Defina la complejidad de Kolmogorov de , , como la...
No puedo pensar en ningún modelo de este tipo, ¿tal vez alguna forma de cálculo lambda mecanografiado? algún autómata celular elemental? Esto casi refutaría el "Principio de equivalencia computacional" de Wolfram: Casi todos los procesos que obviamente no son simples pueden verse como cálculos...
Una pregunta muy específica, lo sé, y dudo que sea respondida por alguien que no esté familiarizado con las reglas de Magic. Publicación cruzada en Draw3Cards . Aquí están las reglas integrales para el juego Magic: the Gathering . Vea esta pregunta para obtener una lista de todas las cartas...
Tengo dificultades para enseñar el concepto de funciones computables. Traté de desarrollar la idea de por qué investigadores como Hilbert / Ackermann / Godel / Turing / Church / ... inventaron la noción de 'computabilidad'. Los estudiantes inmediatamente preguntaron: "¿Qué significa la...
Al leer algunos subprocesos recientes sobre computación cuántica ( aquí , aquí y aquí ), me hace recordar una pregunta interesante sobre el poder de algún tipo de máquina de preservación ℓpℓp\ell_p -norm. Para las personas que trabajan en la teoría de la complejidad que van a la complejidad...