Me dijeron que las computadoras cuánticas no son computacionalmente más poderosas que las máquinas de Turing. ¿Podría alguien ayudarme amablemente a dar algunas referencias de literatura que expliquen este
Se ha demostrado que el problema de decidir si una entrada es un palíndromo o no requiere espacio en una máquina Turing. Sin embargo, incluso almacenar la entrada ocupa espacio ¿no significa eso que todas las máquinas de Turing requieren espacio ?Ω ( logn )Ω(Iniciar sesiónnorte)\Omega(\log...
¿Aceptar significa que el TM leerá y reconocerá un carácter de la celda de la que está leyendo actualmente? ¿Y es el caso de que una TM se detenga si la entrada es
En el análisis de algoritmos, asumimos una máquina de acceso aleatorio (RAM) genérica de un procesador. Hasta donde yo sé, la máquina RAM no es más eficiente que la máquina Turing. Todos los algoritmos se pueden implementar en la máquina Turing. Entonces mis preguntas son: Si la máquina de Turing...
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...
Bien, aquí hay una pregunta de una prueba anterior en mi clase de Teoría de la computación: Un estado inútil en una TM es uno que nunca se ingresa en ninguna cadena de entrada. Deje que Demuestre que es indecidible.U S E L E S S T MUSELESSTM={⟨M,q⟩∣q is a useless state...
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...
Las máquinas de Turing y las gramáticas sin restricciones son dos formalismos diferentes que definen los lenguajes RE. Algunos lenguajes RE son decidibles, pero no todos lo son. Podemos definir los idiomas decidibles con las máquinas de Turing diciendo que un idioma es decidible si hay una TM para...
He visto sitios web que pretenden "probar" que HTML5 + CSS es Turing Complete. He visto sitios web que pretenden "probar" que SQL está Turing completo. He visto un montón de sitios web que pretenden "explicar" lo que significa ser Turing completo. ¡Suficiente! ¿Dónde puedo encontrar un libro?...
Tengo el siguiente problema algorítmico: Determine el espacio Turing complejidad de reconocer cadenas de ADN que son palíndromos de Watson-Crick. Los palíndromos de Watson-Crick son cuerdas cuyo complemento invertido es la cuerda original. El complemento se define en forma de letra, inspirado...
Recibo la prueba de pasar de un enumerador a una máquina de Turing (sigo ejecutando el enumerador y ver si coincide con la entrada) pero no veo cómo funciona la otra manera. Según mis notas y el libro (Introducción a la teoría de la computación - Sipser), para obtener el enumerador de Turing de...
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...
¿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...
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 este sitio hay muchas variantes sobre la cuestión de si las TM pueden decidir el problema de detención, ya sea para todas las otras TM o ciertos subconjuntos. Esta pregunta es algo diferente. Pregunta si el problema de detención se aplica a todas las TM puede ser decidido por una TM. Creo que...
Una declaración del teorema de Rice se da en la página 35 de "Complejidad computacional: un enfoque moderno" (Arora-Barak): Una función parcial de { 0 , 1 }∗{0,1}∗\{0,1\}^* a { 0 , 1 }∗{0,1}∗\{0,1\}^* es una función que no está necesariamente definida en todas sus entradas. Decimos que una TM...
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...
En la década de 1950 se inventaron varios métodos para la minimización de circuitos para funciones booleanas . ¿Existe una extensión de esos métodos o algo similar para optimizar el tiempo o la complejidad espacial de los algoritmos? Por ejemplo, una implementación de clasificación de burbujas...
¿Por qué los números computables (en el sentido de Turing) son enumerables? Debe ser muy obvio, pero actualmente no lo estoy
Deje una cadena de entrada como . Luego, si un NFA se encuentra actualmente en el estado r (y ha leído la entrada hasta el alfabeto w i ), antes de leer el siguiente símbolo de entrada, el NFA se divide en dos NFA, uno en el estado r y otro en s , si hay una transición del tipo r ϵ → s . Si hay un...