Preguntas sobre la simulación de un modelo en otro. Esto incluye simular la realidad en cualquier modelo o simular un modelo de máquina con máquinas de Turing.
Estoy buscando una explicación sobre cómo se podría probar que dos modelos de cálculo son equivalentes. He estado leyendo libros sobre el tema, excepto que se omiten las pruebas de equivalencia. Tengo una idea básica sobre lo que significa que dos modelos de computación sean equivalentes (la vista...
Según este artículo de Wikipedia , las gramáticas sin restricciones son equivalentes a las máquinas de Turing. El artículo señala que puedo convertir cualquier máquina de Turing en una gramática sin restricciones, pero solo muestra cómo convertir una gramática en una máquina de Turing. ¿Cómo puedo...
Sea una función fija construible en el tiempo.fff El clásico resultado de la simulación universal para TMs (Hennie y Stearns, 1966) establece que hay una TM dos cintas tal queUUU la descripción de un TM , y⟨M⟩⟨M⟩\langle M \rangle una cadena de entrada ,xxx corre por pasos y devuelve la...
En esta pregunta sobre el recuento de inversiones , encontré un documento que demuestra un límite inferior en la complejidad del espacio para todos los algoritmos de transmisión (exactos) . He afirmado que este límite se extiende a todos los algoritmos de tiempo lineal. Esto es un poco audaz ya...
El objetivo es crear DFA a partir de una expresión regular y usar "Exp. Regular> NFA> Conversión de DFA" no es una opción. ¿Cómo debería uno hacer eso? Le hice esta pregunta a nuestro profesor, pero él me dijo que podemos usar la intuición y amablemente se negó a dar ninguna explicación....
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
¿Existe un autómata celular (en 2D) que simula una fuerza entre partículas?1/r1/r1/r Más específicamente, me gustaría saber si es posible, con reglas de actualización estrictamente locales, que dos objetos (definidos dentro del modelo) se atraigan entre sí con una fuerza de , donde es la distancia...
Estoy leyendo Sipser y me resulta difícil entender cuál es el proceso, de modo que si me das k máquinas Turing con k cintas, puedo escupir una máquina Turing equivalente con una sola cinta. Un ejemplo sería bueno. En realidad, lo que realmente estoy buscando es un ejemplo resuelto que muestre cómo...
La pregunta es el ejercicio 1.9 del libro de Arora-Barak Complejidad computacional: un enfoque moderno : Defina una máquina RAM Turing para que sea una máquina Turing que tenga memoria de acceso aleatorio. Formalizamos esto de la siguiente manera: la máquina tiene una matriz infinita A que se...
Estoy tratando de encontrar las respuestas de dos preguntas sobre la máquina Universal Turing. ¿Cómo puede la máquina Universal Turing simular una máquina Turing si la que se está simulando tiene un mayor número de estados? ¿Cómo puede la máquina de Turing universal simular una máquina de Turing...
¿Es una máquina de Turing que puede leer y escribir símbolos de un alfabeto infinito más poderosa que una TM normal (esa es la única diferencia, la máquina todavía tiene un número finito de estados)? La intuición me dice que no, ya que necesitas un número infinito de estados para diferenciar cada...
¿Existe algún conjunto de reglas o métodos para convertir cualquier gramática libre de contexto en un autómata push down? Ya encontré algunas diapositivas en línea, pero no pude entenderlas. En la diapositiva 10 habla sobre algunas reglas, ¿alguien podría explicar
Se sabe que las lógicas temporales LTL, CTL, CTL * se pueden traducir / incrustar en el cálculo . En otras palabras, el cálculo (modal) subsume estas lógicas (es decir, es más expresivo).μμ\muμμ\mu ¿Podría por favor explicarme / señalarme artículos / libros que detallen este asunto? En particular,...
Tengo un pequeño problema para entender la prueba del Teorema de la Jerarquía del Tiempo (Hennie y Stearns, 1966) que asegura la existencia de un lenguaje aceptable en pero no aceptable en para cualquier función , de modo que sea construible en el tiempo yU( n )U(norte)U(n)T( n )T(norte)T(n)T( n...
Cuando leí sobre la tesis de la Iglesia-Turing, parece ser una afirmación común de que "la realidad física es computable por Turing". ¿Cuál es la base de este reclamo? ¿Hay algún resultado teórico en este sentido? Por contexto, soy un investigador que trabaja en simulaciones físicas, así que, por...