Parece recordar de una clase de pregrado que para una máquina de Turing con una cinta finita siempre existirán los autómatas estatales finitos correspondientes, pero no he podido encontrar esto confirmado en ningún lugar de Internet. ¿Es este realmente el caso o estoy recordando...
Al leer esta pregunta " Problemas naturales indecidibles de RE pero no completos de Turing ", me vino a la mente el siguiente lenguaje: Si es la función de castor ocupado (puntaje máximo alcanzable entre todas las máquinas Turing de 2 símbolos de estado n detenidas del tipo descrito anteriormente,...
En una pregunta anterior ¿ Qué es exactamente un algoritmo? , Pregunté si tener un "algoritmo" que devuelve el valor de una función basada en una matriz de valores calculados previamente era un algoritmo. Una de las respuestas que me llamó la atención fue esta: El ejemplo factorial se introduce...
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...
Acabamos de terminar nuestra clase de "Construcibilidad de tiempo" en clase la semana pasada y, por el bien de nosotros, mostramos que nk,2nnk,2nn^k, 2^n son completamente construibles en el tiempo, es decir, existe una máquina de Turing (determinista de múltiples cintas) que para nnn dado, se...
En primer lugar, me disculpo si se me ha preguntado esto, pero realmente no encontré nada. Me he topado con este artículo . Dice que hay un problema que solo las computadoras cuánticas pueden resolver. Según tengo entendido, esto debería significar, intuitivamente, que este problema es...
Por ejemplo, podemos decir que tenemos un programa abstracto que, dada una cadena binaria finita como entrada, elimina todos los ceros (es decir, 0010001101011 se evalúa como 111111), que definitivamente es una función computable de Turing. ¿Cómo puede un sistema de etiquetas cíclicas calcular...
Estoy tratando de vincular circuitos lógicos combinacionales (computadoras basadas solo en puertas lógicas) con todo lo que aprendí recientemente en Teoría de la Computación. Me preguntaba si los circuitos lógicos combinacionales pueden implementar cálculos de la misma manera que las máquinas de...
Sea un conjunto no trivial de lenguajes recursivamente enumerables ( ) y L sea el conjunto de codificaciones de máquinas Turing que reconocen algún lenguaje en C : L = \ {\ langle M \ rangle \ mid L (M) \ en C \}CCC∅⊊C⊊RE∅⊊C⊊RE\emptyset \subsetneq C \subsetneq
¿Nuestra PC funciona como máquina de Turing? El modelo de una máquina de Turing consiste en una cinta de memoria infinita, que significa estados infinitos. Pero supongamos que si nuestra PC tiene 128 MB de memoria y 30 GB de disco, tendría 256 ^ 30128000000 estados y, por lo tanto, tiene estados...
Quiero determinar si este problema de decisión es decidible. He intentado establecer reducciones de Alto y "Acepta cadena vacía", pero aún no he encontrado una solución. ¿Alguien me puede
En los últimos dos años, construí una computadora mecánica impulsada por canicas e hice un juego con ella. Es similar al antiguo Digi-Comp II, excepto por dos diferencias clave: Las piezas son reposicionables en el tablero. Puede conectar múltiples 'bits' juntos usando engranajes. Cuando uno de...
Estoy tratando de atacar a TAOCP una vez más, dada la gran pesadez literal de los volúmenes que tengo problemas para comprometerme en serio. En TAOCP 1 Knuth escribe, página 8, conceptos básicos :: Dejar AAAser un conjunto finito de letras. DejarA∗A∗A^* ser el conjunto de todas las cadenas en...