Se sabe que el lenguaje de las palabras que contienen el mismo número de 0 y 1 no es regular, mientras que el lenguaje de las palabras que contienen el mismo número de 001 y 100 es regular ( ver aquí ). Dadas dos palabras , ¿es decidible si el lenguaje de las palabras que contienen el mismo número...
Me pregunto si decidir la capacidad de decisión del problema es un problema decidible. Supongo que no, pero después de las búsquedas iniciales no puedo encontrar ninguna literatura sobre este
He leído en Wikipedia y algunos otros textos que El problema de detención es [...] decidible para autómatas lineales (LBA) [y] máquinas deterministas con memoria finita. Pero antes se escribe que el problema de detención es un problema indecidible y, por lo tanto, TM no puede resolverlo. Dado...
Sin embargo, muchos problemas indecidibles "famosos" son al menos semidecidibles, y su complemento es indecidible. Un ejemplo sobre todo puede ser el problema de detención y su complemento. Sin embargo, ¿alguien puede darme un ejemplo en el que tanto un problema como su complemento sean...
Estaba revisando la definición de Wikipedia de lenguaje sensible al contexto y encontré esto: Cada categoría de idiomas es un subconjunto apropiado de la categoría directamente encima de ella. Cualquier autómata y cualquier gramática en cada categoría tiene un autómata o gramática equivalente en...
Estaba leyendo una respuesta a una pregunta reciente, y una especie de pensamiento extraño y efímero vino a mi mente. Si pregunto esto, podría traicionar que mis habilidades teóricas faltan seriamente (en su mayoría ciertas) o que es demasiado pronto para que yo lea este sitio. Ahora, con el...
¿Existen idiomas indecidibles tales que su lenguaje de unión / intersección / concatenado sea decidible? ¿Cuál es la interpretación física de tal ejemplo porque, en general, los lenguajes indecidibles no están cerrados bajo estas operaciones? ¿Qué podemos decir sobre el cierre de Kleene? ¿Tenemos...
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...
Entiendo que la mayoría de los problemas son triviales si hay un oráculo de detención disponible (o, creo, equivalentemente, hipercomputación). Sin embargo, aplicar el argumento que muestra que el problema de detención es imposible para una máquina de Turing también muestra que es imposible que un...
¿La existencia de problemas indecidibles implica inmediatamente la no previsibilidad de los sistemas físicos? Consideremos el problema de detención, primero construimos un UTM físico, digamos usando la construcción basada en circuito habitual. Entonces no puede haber una teoría física decidible que...
Lo siento si esta pregunta tiene alguna respuesta trivial que me falta. Cada vez que estudio algún problema que se ha demostrado que es indecidible, observo que la prueba se basa en una reducción a otro problema que se ha demostrado que es indecidible. Entiendo que crea algún tipo de orden sobre el...
Deje que ¿Hay una máquina de Turing R que decida (no quiero decir que reconozca) el idioma ?L ∅L∅= { ⟨ M⟩ ∣ M es una máquina de Turing y L ( M) = ∅ } .L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and...
¿Existe un algoritmo para el siguiente problema: Dada una máquina de Turing que decide un lenguaje L , ¿hay una máquina de Turing M 2 que decide L de modo que t 2 ( n ) = o ( t 1 ( n ) ) ?METRO1M1M_1LLLMETRO2M2M_2LLLt2( n ) = o ( t1( n ) )t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Las funciones y t 2...
Una de las definiciones de un conjunto computablemente enumerable (ce, equivalente a recursivamente enumerable, equivalente a semidecidable) es la siguiente: A⊆Σ∗A⊆Σ∗A \subseteq \Sigma^* es ce si hay un lenguaje decidible (llamado verificador) st para todos , x ∈ Σ ∗V⊆Σ∗V⊆Σ∗V\subseteq...
Me he encontrado con el siguiente problema interesante: dejemos que sean polinomios sobre el campo de los números reales, y supongamos que sus coeficientes son todos enteros (es decir, hay una representación exacta finita de estos polinomios). Si es necesario, podemos suponer que el grado de ambos...
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...
En el problema de detención, nos interesa saber si hay una máquina Turing que pueda decir si una máquina Turing detiene o no en una entrada dada . Por lo general, la prueba comienza asumiendo que tal existe. Luego, consideramos un caso en el que restringimos a , y luego derivamos una contradicción...
¿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
¿Es necesario que sea infinito para ser indecidible?L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* Quiero decir, ¿qué sucede si elegimos un idioma? será una versión limitada finita de , es decir , ( ), con . ¿Es posible que sea un lenguaje indecidible? L′L′L' L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^*|L′|≤N|L′|≤N|L'|\leq...
Supongamos que tengo dos funciones y y estoy interesado en determinar siFFFGGG F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Supongamos que mis funciones están compuestas de funciones elementales (polinomios, exponenciales, registros y funciones trigonométricas), pero no, digamos, series de...