¿Hay propiedades indecidibles de autómatas no completos?

15

¿Hay propiedades indecidibles de autómatas lineales delimitados (evitando el truco del lenguaje de conjunto vacío)? ¿Qué pasa con un autómata finito determinista? (Deje de lado la intratabilidad).

Me gustaría obtener un ejemplo (si es posible) de un problema indecidible que se define sin utilizar explícitamente máquinas de Turing .

¿Es necesario que Turing esté completo de un modelo para soportar problemas inconfesables?

computability automata undecidability Hernan_eche
fuente

"¿Hay alguna solución para este sistema de ecuaciones diofantinas?" ¿Es esto lo que estás preguntando? No me queda claro lo que quieres. Pero, el problema que di es indecidible y no menciona TM, por lo que, estrictamente hablando, parece satisfacer los requisitos de su segundo párrafo.

rgrig

Decidir si dos autómatas pushdown reconocen las mismas palabras es indecidible, así como otros problemas sobre los autómatas pushdown . No puedo pensar en problemas indecidibles relacionados con DFA.

jmad

1

La respuesta a la pregunta "¿Es posible construir un problema indecidible para un autómata menos potente que una máquina de Turing" es sí . De hecho, para cada tipo de autómata siempre se puede identificar un problema indecidible.

Amelio Vazquez-Reina

1

Dada la respuesta aceptada, reformulé la pregunta para preguntar qué quiere el OP (aparentemente).

Raphael

15

Problemas indecidibles sobre gramáticas libres de contexto y, por lo tanto, también aceptadores de pushdown, que son TM restringidos de Wikipedia ...

Dado un CFG, ¿genera el lenguaje de todas las cadenas sobre el alfabeto de los símbolos terminales utilizados en sus reglas?
Dados dos CFG, ¿generan el mismo idioma?
Dados dos CFG, ¿puede el primero generar todas las cadenas que el segundo puede generar?

Hay muchos otros sobre CFG / PDA, así como CSG / LBA y muchos otros modelos "más simples que TM".

David Lewis
fuente

+1, gracias, todavía tengo la tentación de preguntar sobre un CFG más simple, y así sucesivamente ... para descubrir cuál es el primer (más simple) problema de autómatas + más simple que no se puede

decidir

3

Para encontrar un problema "más simple" o "más simple" que sea indecidible, o que tenga alguna propiedad, necesitaría una definición precisa de "simple", de la cual muchos son posibles. Pero el clásico en autómatas y lenguajes formales es "nivel en la jerarquía de Chomsky" (que en realidad no es una gran jerarquía, matemáticamente hablando; originalmente se propuso para las gramáticas del lenguaje natural). La FSA es la más baja, y estoy bastante seguro de que cualquier problema indecidible para las FSA tendría que referirse de alguna manera "esencial" a formalismos "menos simples" (todos necesitan una definición precisa). CFL / CFG es el siguiente más alto, así que elegí eso.

David Lewis

+1 Estoy de acuerdo, encontrar que lo mínimo también es indecidible, sorprendentemente no es posible construir un problema indecidible para FSA, luego es posible para CFG, es tentador encontrar algo intermedio, gracias

Hernan_eche

1

@Hernan_e: existe una estructura muy rica de modelos e idiomas sub-CFL, por ejemplo, el pda / family de 1 contador, que utiliza un "contador" entero positivo en lugar de un pda; el n-turn pda, que permite solo turnos de aumento a disminución de la pila, y generalizaciones de esos. Y hay muchos problemas indecidibles sobre ellos, así como preguntas abiertas sobre las estructuras, por ejemplo: ¿existe una CFL no "mínima" no regular en alguna noción precisa de "mínimo"? Pero estas cosas suelen ser a nivel de graduado y / o investigación.

David Lewis

7

No está claro lo que está preguntando en la parte posterior de la pregunta, principalmente porque "un problema sobre un modelo de máquina" no está definido.

Me gustaría obtener un ejemplo (si es posible) de un problema indecidible sin necesidad de Turing Machine

Sea una clase de máquinas y usemos como código de . Podemos interpretar también como el código de th TM y luego preguntar que dado ¿se detiene th TM? Y este problema sobre s es indecidible. $\{M_i\}$ $i$ $M_i$ $i$ $i$ $M_i$ $i$ $M_i$

Un idioma es solo un conjunto de cadenas, la interpretación que asigna a las cadenas no tiene ningún efecto sobre la capacidad de decisión del idioma. A menos que defina formalmente lo que quiere decir con un modelo de máquina y un problema sobre esas máquinas, sus preguntas posteriores no podrán ser respondidas.

¿Turing completa la maquinaria mínima para soportar un problema indecidible?

De nuevo, se aplica el punto que mencioné anteriormente. Una pregunta más razonable sería: ¿todas las pruebas de indecidibilidad pasan por algo similar a la indecidibilidad del problema de detención para TMs? (La respuesta es: hay otras formas).

Otra posible pregunta es: ¿cuál es el subconjunto más pequeño de TMs donde el problema de detención para ellos es indecidible? Obviamente, tal clase debe contener problemas que no se detengan (de lo contrario, el problema es decididamente trivial). Podemos crear fácilmente subconjuntos artificiales de TMs donde el problema de detención no es decidible sin poder calcular nada útil. Una pregunta más interesante es acerca de grandes conjuntos de TMs decidibles donde la detención es decidible para ellos.

Aquí es otro punto: tan pronto como tiene muy pequeña capacidad de manipular los bits (por ejemplo, un tamaño polinomio ) puede crear una máquina de con tres entradas: , , y de tal manera que la salida 1 si y sólo si es una detener aceptar el cálculo de TM en la entrada . Luego puede preguntar los problemas como: ¿hay un st es 1? que es un problema indecidible $\mathsf{CNF}$ $N$ $e$ $x$ $c$ $c$ $M_e$ $x$ $c$ $N(e,x,c)$

Kaveh
fuente

5

Existe un problema indecidible muy simple para los autómatas de estado finito. Divide el alfabeto en dos mitades , donde las letras en son copias "prohibidas". Ahora, dado un autómata de estado finito sobre decida si acepta una cadena tal que la parte sin barra sea igual a la parte con barra (si ignoramos las barras). Por ejemplo, cadena estaría bien (ambas partes deletrean ). $\Sigma \cup \bar\Sigma$ $\bar\Sigma$ $A$ $\Sigma\cup\bar\Sigma$ $a a \bar a \bar a b\bar b \bar aa$ $aaba$

Sí, este es un problema de correspondencia posterior oculto en un autómata de estado finito. La integridad de Turing está lejos de ser obvia en la pregunta. Está allí, en el fondo, cuando las dos copias (sin barra y sin barra) juntas codifican una cola, que en sí misma tiene el poder de Turing.

Hendrik Jan
fuente

¿tienes un referente en esto? No es obvio cómo convertir PCP a esto. Para su información, también hay algunos problemas indecidibles con los "transductores" FSM.

vzn

1

(1) Tiene razón, de hecho está relacionado con un problema de dos cintas , las barras indican la segunda cinta. (2) Relación con PCP de la siguiente manera. La instancia de PCP consta de dos listas de palabras

,

. Ahora el lenguaje normal que codifica PCP es

, donde

es la copia prohibida de

(u_{1}, \dots, u_{n})

$(u_1,\dots,u_n)$

(v_{1}, \dots, v_{n})

$(v_1,\dots,v_n)$

{u_{1} {\bar{v}}_{1}, \dots, u_{n} {\bar{v}}_{n}}^{+}

$\{ u_1\bar v_1, \dots, u_n\bar v_n \}^+$

\bar{v}

$\bar v$

. Me temo que no tengo una referencia.

v

$v$

Hendrik Jan

3

"¿Es posible construir un problema indecidible para un autómata menos potente que una máquina de Turing?"

Si. Un autómata es una formulación axiomática coherente de la teoría de números (por ejemplo, ver (1) ) y, por lo tanto, según el primer teorema de incompletitud de Gödel , debe incluir proposiciones indecidibles.

Ejemplo:

Cualquier problema que sea indecidible para una TM también lo es para cualquier autómata que una TM pueda simular. ¿Por qué? Porque si un autómata que es menos poderoso que un TM podría decidir un lenguaje que un TM no puede decidir, un TM debería poder decidirlo simulando el autómata con una contradicción.

Amelio Vazquez-Reina
fuente

2

La cuestión de si un LBA se detiene o no también es decidible para un TM, por lo que no fue parte de los ejemplos que proporcioné en mi respuesta. Cualquier problema que sea indecidible para un TM también es indecidible para un LBA.

Amelio Vazquez-Reina

1

{T | T M T h a l t s o n i n p u t T}

$\{T|TM T halts on input T\}$ que claramente no es decidible, pero eso es artificial. Eso probablemente se puede formalizar.

David Lewis

1

{T | TM T (T) halts}

$\{T|\text{ TM } T(T) \text{ halts}\}$

1

@DavidLewis roseck no está afirmando que un problema indecidible sobre TMs todavía no se pueda resolver si lo reinterpretas como si se tratara de LBA. roseck simplemente afirma que si hay un problema que no puede ser resuelto por TMs, entonces el mismo problema sin reinterpretación tampoco puede ser resuelto por nada que una TM pueda simular. El problema de detención de TM y el problema de detención de LBA son dos problemas diferentes.

Ben

1

@Ben - si es así, entonces "... indecidible para cualquier autómata que ..." tendría que ser " por ". Pero esa es una declaración trivial.

David Lewis

1

Emil Post quería encontrar la respuesta exactamente a esta pregunta: ¿Existe un conjunto no recursivo (no computable) que no resuelva el problema de detención. Tuvo éxito solo en parte, pero lo que hizo fue crear lo que se llama conjuntos simples .

De Wikipedia:

Un subconjunto de los naturales se llama simple si es infinito y recursivamente enumerable, pero cada subconjunto infinito de su complemento no se enumera recursivamente. Los conjuntos simples son ejemplos de conjuntos enumerables recursivamente, que no son recursivos. Eche un vistazo al artículo de Wikipedia para obtener más información y referencias, conjunto simple .

Pål GD
fuente

¿Hay propiedades indecidibles de autómatas no completos?

Respuestas: