Síntesis del programa, capacidad de decisión y el problema de la detención.

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 descargo de responsabilidad fuera del camino ...

Es un resultado bien conocido en la teoría de la computabilidad que el problema de detención no se puede decidir para TMs. Sin embargo, esto no excluye la posibilidad de que existan máquinas que puedan resolver el problema de detención para ciertas clases de máquinas (solo que no todas).

Considere el conjunto de todos los problemas decidibles. Para cada problema, existen infinitas TM que deciden ese idioma. ¿Podría ser posible lo siguiente?

Hay una TM que decide el problema de detención para un subconjunto de máquinas Turing; y $S$
Todos los problemas decidibles son decididos por al menos una máquina de Turing en ? $S$

Por supuesto, encontrar la máquina de Turing en puede no ser computable en sí mismo; Pero ignoramos ese problema. $S$

EDITAR: Basado en la respuesta de Shaull a continuación, parece que (a) esta idea está demasiado mal especificada para ser significativa o (b) mi intento anterior no fue del todo correcto. Mientras trato de elaborar en los comentarios a la respuesta de Shaull, mi intención no es que se tiene la garantía de que el TM de entrada está en . Lo que realmente quise decir con mi pregunta es si podría existir una tal , que la membresía en sea un problema decidible . El programa para resolver el problema de detención para , presumiblemente, escribiría "entrada no válida" en la cinta o algo así cuando se le dé una entrada que reconoce que no está en $S$ $S$ $S$ $S$ $S$ . Cuando lo formulo así, no estoy seguro de si esto nos permite resolver el problema de detención o no, o si se aplica el teorema de Rice (¿la capacidad de decisión es una propiedad semántica de un lenguaje con el teorema de Rice?)

turing-machines undecidability halting-problem Patrick87
fuente

cree que hay una pregunta legítima / significativa en los límites de la teoría que acecha aquí en algún lugar pero no en la forma actual, sin embargo, +1 por intentar [y ese descargo de responsabilidad al principio es sorprendente teniendo en cuenta su estado de representante / moderador] ... tal vez esto es la pregunta que estabas leyendo? algoritmo para resolver el problema de detención de turings

vzn 05 de

posiblemente otra forma de formular la pregunta, no sé si esta fue la intención (lo que la hace muy avanzada). considere todos los "cuasialgoritmos" posibles y sus conjuntos reconocidos asociados . [ver otra pregunta para defns]. ¿La unión de todos estos conjuntos reconocidos igual al conjunto de todos los TM recursivos / decidibles?

S_{n}

$S_n$

S_{n}

$S_n$

vzn

Respuestas:

Creo que puede haber un problema con la formulación del problema.

Considere el conjunto es un decisor de su idioma . El problema de detención es decidible para este conjunto (es decir, si se nos promete que la entrada está en este conjunto). De hecho, es trivial (las máquinas en siempre se detienen). $S=\{M: M$ $\}$ $S$

También, claramente todos los idiomas decidable está en . $S$

EDITAR: Según los cambios en la pregunta, de hecho, la pertenencia a sería indecidible: si contiene una máquina para cada lenguaje decidible, entonces . Por lo tanto, por el teorema de Rice, si es decidible entonces contiene todas las máquinas, pero entonces el problema de la parada es indecidible en . $S$ $S$ $S\neq \emptyset$ $S$ $S$ $S$

Shaull
fuente

En otras palabras, contesta trivialmente la pregunta positivamente.

S = {⟨ A ⟩ ∣ \forall x . A (x) ↓, L (A) \in R}

$S = \{\langle A \rangle \mid \forall x. A(x) \downarrow, L(A) \in \mathrm{R}\}$

Raphael

@Raphael: no, porque mientras , no implica que sea decisivo. Es por eso que explícitamente tomamos decisiones.

L (A) \in R

$L(A)\in R$

A

$A$

Shaull

Ah bien. Corregido el comentario.

Raphael

+1 No estoy seguro de haber comunicado claramente mi significado. Lo que realmente me refiero a preguntar era si es posible que un tal existe, y podemos comprobar una arbitraria TM para ver si está en . No sabemos a priori que esté en ; solo que está formulado de tal manera que podamos verificarlo. En otras palabras, ¿es posible que exista una tal que la membresía en sea decidible? Además, su última oración es algo confusa; es un conjunto de máquinas de Turing (bueno, sus representaciones); no de los idiomas que deciden los TM ... pero creo que sé lo que quieres decir.

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

Patrick87

(PD: Perdón por haber equivocado tu nombre en mis ediciones. Es demasiado pronto para que yo haga CS.SE está empezando a parecer cada vez más probable)

Patrick87 05 de