¿Es posible la metadecidibilidad?

9

Hay problemas que son decidibles, hay algunos que son indecidibles, hay semidecidabilidad, etc.

En este caso, me pregunto si un problema puede ser metadecidible. Esto significa (al menos en mi cabeza) que no podemos decir si es decidible o no.

Tal vez se sabe que la capacidad de decisión es indecidible (todo es metadecidible) y no existe un algoritmo para probar la capacidad de decisión para nada, por lo que la capacidad de decisión debe probarse a mano caso por caso.

Tal vez mi pregunta no tiene sentido. Tal vez supongo que somos máquinas de carbón que ejecutan algoritmos muy complejos y es por eso que la pregunta solo tiene sentido en mi cabeza.

Avíseme si la pregunta necesita más aclaraciones. Puede que lo necesite yo mismo en este momento.

Gracias.

Trylks
fuente
Consideremos la afirmación "la teoría monádica (de segundo orden) de todos los órdenes lineales es computable". Hay razones para creer (pero no estoy seguro de que se haya demostrado la independencia) de que esta declaración es independiente (es decir, indecidible) en ZFC. Se pueden encontrar más detalles sobre los motivos en books.google.es/books?id=y3YpdW-sbFsC&pg=PA397
boumol
1
Cuando dice "la capacidad de decisión es indecidible", ¿cuál es la entrada?
Mahdi Cheraghchi
2
También podría estar interesado en en.wikipedia.org/wiki/Turing_degree pero no está claro por cómo se plantea la pregunta. :)
Daniel Apon
1
@boumol Shelah ("La teoría monádica del orden", Ann. Math. 102 (3), 1975) demostró (suponiendo CH) que "la teoría monádica del orden es indecidible" (Teorema 7 (B), p. 409).
Yuval Filmus
1
L={halting problemif the continuum hypothesis holdsotherwise
sdcvvc

Respuestas:

8

Aquí hay un bosquejo rápido para mostrar que no hay una máquina de Turing para decidir si una clase arbitraria de problemas es decidible.

Debo aclarar lo que quiero decir con clase de problemas: una clase de problemas es una máquina de Turing que enumera los elementos (números naturales, por ejemplo) de un conjunto recursivamente enumerable uno tras otro, de modo que cada elemento en el conjunto finalmente se imprima . El problema captado intuitivamente por T ( n )TT(n) es: "¿es el número en este conjunto?". Esto captura los problemas habituales en el campo de la computabilidad, como "¿es el índice de una máquina de Turing que se detiene en una entrada vacía?".n

Supongamos que hay era máquina que, dada como entrada una clase de problemas T respondió t r u e si esa clase es decidible y f un lMTtruefalse

Ahora tome una máquina de Turing arbitraria . Construimos la siguiente clase de problemas T TT de la siguiente manera:

  1. Simular T
  2. Si T detiene, enumere los índices de las máquinas de Turing que se detienen en la entrada vacía.

TM(T)false

TTM(T)true

M(T)trueTfalseMT

cody
fuente
¡Hola, Cody! Espero que lo estás haciendo bien. ¿Estarás en Pittsburgh este verano?
Michael Wehar
¡Oye! No estoy seguro. ¡Envíame un correo electrónico!
cody
1

Muy buena idea!

Idea: Podemos explotar el axioma de comprensión en la teoría de conjuntos ZF para definir un lenguaje que depende de una declaración independiente.

Paso 1: tome su declaración favorita que sea independiente de ZF, como AC, el axioma de elección.

Paso 2: Defina un idioma L = {x en {0,1} | x = 0 si AC yx = 1 si NO AC}. Observe que L es {0} o {1}. Ahora, L es decidible, pero no podemos proporcionar con certeza un programa que decida L. Podríamos proporcionar el programa que decide {0} o podríamos proporcionar el programa que decide {1}, pero no sabemos con certeza cual decide L.

Paso 3: Use esta idea para definir un lenguaje que sea decidible si es AC e indecidible si NO es AC. Sea H el conjunto de detención que es indecidible. Definir L = {x | x es una cadena si AC yx está en H si NO AC}. Si AC, entonces L = el conjunto de todas las cadenas y L es decidible. Si NO es AC, entonces L = H y L es indecidible. Si L es decidible o no es independiente de ZF.

Michael Wehar
fuente