Entradas “problemáticas” que no se detienen para las máquinas de Turing

Question

Comencemos esta pregunta definiendo para una máquina de Turing el conjunto de palabras que no detenerse.Definir: $P(M)=\{w\in\Sigma^*|M$ no se detiene $w \}$

Sabemos que el $ DETENER $ el problema es $RE\setmenos R$ - así cada MT $M$ que calcula $ DETENER $ tiene una palabra en la que no se detiene, es decir $P(M) e\emptyset$.

De esto surge la (simple) pregunta:

$Q(1):$ "es un problema indecidible si y sólo si cada MT que lo calcula tiene un conjunto 'problemático' no vacío $P(M)$?" $ ^{Q\espacio(1)}$

Además, observemos que para el $ DETENER $ problema sabemos que dado $M$ que lo calcula, hay infinitas entradas en las que nunca se detendrá (te animo a pensar por qué es así, antes de continuar con la publicación)

Entonces, de manera similar, podríamos plantearnos la versión (un poco) más difícil de la primera pregunta.

$Q(2):$ "Es un problema indecidible si cada MT $M$ que calcula que tiene $|P(M)|=\aleph_0$?" $ ^{Q\espacio(2)}$

Además, hagamos una pregunta aún más fuerte:

$Q(3):$ "si $l$ es indecidible, ¿seremos todavía capaces de encontrar una finito conjunto de máquinas de turing $M_1,...,M_n$ que computa $l$ y tiene $\bigcap_{k\space=\space0}^nP(M_k)$ ¿finito?¿Qué pasa con un infinito conjunto de máquinas de Turing que satisfagan eso?" $ ^{Q\espacio(3)}$

Y nuestra pregunta final (y medio abierta) será:

$Q(4):$ "¿Qué más podemos entender sobre las máquinas de Turing y sus conjuntos problemáticos?"

Answer 1

Entonces, comencemos a abordar esos problemas.Como nota al margen, he organizado las preguntas de manera que cada pregunta utilice la respuesta de la anterior (y de esta manera, casi parecen demasiado triviales para empezar). $:$PAG).

$A(1):$ es bastante trivial por definición.Si $l$ es indecidible entonces no hay ninguna máquina de Turing que lo calcule y siempre se detiene, por lo tanto todas las máquinas de Turing que lo calculan $l$ tener $P(M) e\emptyset$.La otra dirección también es tan simple como ésta.

$A(2):$ asumamos $l$ es indecidible.Si hubiera una máquina de Turing $M$ que calcula $l$ y tiene finito $P(M)$, entonces construyamos una nueva máquina $\sombrero M$ tal que tendrá $P(\sombrero M)=\emptyset$ como sigue (en la entrada $w$):

• rechazar si $w \en P(M)$ (esto es posible ya que $P(M)$ es finito)
• de lo contrario, regrese $M(w)$

esta nueva máquina, se detendrá por cada $w\en P(M)$, pero ya que por cada $w otin P(M)$ correrá $M$, y está garantizado que se detendrá (ya que de lo contrario habría estado en $P(M)$), tenemos que el nuevo $\sombrero M$ siempre se detiene y acepta $l$ - contradiciendo así la suposición.La otra dirección se deriva simplemente de $A(1)$.

$A(3)$:para finito conjuntos de máquinas de Turing, $M_1,...M_n$ mostraremos que es imposible tener finitos $\bigcap_{k\space=\space0}^nP(M_k)$ pero indecidible $l$.Supongamos que, por contradicción, esto no es válido.justo en $A(2)$, construiremos $\sombrero M$ - pero ahora es suficiente construirlo de tal manera que $P(\sombrero M)=\bigcap_{k\space=\space0}^nP(M_k):$

• Correr $M_1(w), M_2(w), ...,M_n(w)$ en paralelo
• Aceptar si alguno de ellos aceptó.

Ahora, es obvio por qué $\sombrero M$ acepta $l$.Dejar $w otin P(\hat M)$, entonces hay algo $1\le k\le n$ tal que $M_k(w)$ detenido, por lo tanto $w otin\bigcap_{k\space=\space0}^nP(M_k)$.dejar $w\en P(\sombrero M)$, entonces no se detuvo en ningún $M_k$, de este modo $w\en P(M_k)$ para todos $k$.Concluyendo que $P(\sombrero M)=\bigcap_{k\space=\space0}^nP(M_k)$ es finito y por lo tanto de $A(2)$ no puede existir.

Acerca de infinito conjuntos de máquinas de Turing, esto definitivamente es posible.Solo define para cada $w\en \Sigma^*$ la máquina $M_w$ que acepta $l$ pero también se detiene $w$ (de manera similar a la construcción en $A(2)$).entonces $w otin P(M_w)$ por lo tanto $w otin \bigcap_{\hat w} P(M_\hat w)$ y por tanto no solo eso $\bigcap_{\hat w} P(M_\hat w)$ es finito, también está vacío.

$A(4):$ dejar $l$ es indecidible y $M_1,M_2...$ Son máquinas de Turing las que aceptan $l$ y su intersección del "conjunto problemático" es finita.Si miramos la función $f:\mathbb{N} ightarrow\Sigma^*$ definido por $f(k)=\langle M_k angle$ , entonces es no calculable.Esto se desprende de $A(2)$ ya que si esa función fuera computable, habríamos podido crear una máquina de Turing $\sombrero M$ con $P(\sombrero M)=\bigcap_k P(M_k)$

Otra idea en la que he empezado a pensar es qué pasa cuando hablamos de dos idiomas o más, en lugar de uno a la vez.Dejar $M_1$ ser una máquina para $L_1$ y $M_2$ para $L_2$.Entonces, podemos definir una máquina. $M$ para $L_1\gran capitalización L_2$ o $L_1 aza grande L_2$ con:

$P(M) = P(M_1)\gran taza P(M_2)$ (tenga en cuenta que esto también puede probar las propiedades de cierre en $\mathcal R$)

o si $L_1\Delta L_2$ es finito, entonces los conjuntos problemáticos de máquinas para los lenguajes son más o menos los mismos (para cada máquina $M$ en cualquiera de ellos podemos encontrar máquinas $M'_1,M'_2$ para los otros dos idiomas con el mismo conjunto problemático)

Aunque todavía tengo que escribir una prueba formal de lo anterior.(Honestamente, no tengo energía para escribir más pruebas como esa en esta gran publicación). ¡Aún te animo a que intentes demostrarlo en casa!

¡Finalmente!Creo (pero aún no estoy seguro) que podemos obtener resultados similares (pero con más restricciones) para el análisis de complejidad temporal si definimos $P(M,t)$ para construir en el tiempo $t(n)\ge log(n)$ como el grupo de palabras $M$ no se detiene en el interior $t(n)$ pasos.En esta definición existe el complicado problema de las constantes, por lo que es más difícil mostrar teoremas definiendo nuevas máquinas (ya que podrían hacer un trabajo un poco más constante que hará que alguna palabra entre en el conjunto problemático, y la notación con O grande aquí es algo sin sentido para diferentes constantes)

Si cree que algo está incorrecto o simplemente desea agregar más, estaré encantado de realizar cambios.