¿Cuál es la relevancia de la computabilidad al aplicar la diagonalización?

Question

Cuando piense en la diagonalización, siempre he glosado por si la enumeración, o la diagonal es computable o no.¿Cuándo importa?

Diga, por ejemplo, que tienen una enumeración de los números racionales en un orden no comprable, entonces tendríamos que asumir que una enumeración no comprable de las racionales no existe, o la diagonal le da un número innecesable?

o supongamos que tuvimos una enumeración de un conjunto contable pero no recursivo.¿La diagonalización produciría un número inacutable?

O si asumimos que tenemos una enumeración computable de los números reales computables, y hicimos la diagonalización en ella, entonces tendríamos que asumir que el número en la diagonal es inpacuable?Algo parece mal aquí.

En general, ¿cuáles son las capturas al realizar la diagonalización relacionada con la computabilidad?

Answer 1

No hay capturas. La diagonalización es una técnica de prueba muy general que funciona en el entorno clásico, constructivo y computable. Se utiliza para probar:

• que no hay Sección de un set a su Powerset
• que los números reales no se pueden enumerar
• que los números reales computables no se pueden enumerar computarralmente
• que el oráculo de hallo no existe
• etc.

En su forma más general, se conoce como Teorema de punto fijo de Lawvere .

Preguntas qué sucede si diagonalizas contra los números racionales. No especificaste en qué forma se dan las racionales, asumo que usted significa sus expansiones decimales. La diagonalización producirá un número real que no es miembro de la enumeración (este real puede ser racional o irracional, dependiendo de la enumeración con la que comenzó). Si comienza con una enumeración no computable, el resultado puede ser no computable. Si comienza con una enumeración computable, obtendrá un resultado computable, ya que la diagonalización conserva la computabilidad.

Asimismo, si toma una enumeración computable de números reales computables (dadas como secuencias infinitas de dígitos), el resultado de la diagonalización será un número real computable que no es miembro de la enumeración de partida.

Answer 2

No estoy seguro de cómo responder a la pregunta general, pero para los específicos:

Diga, por ejemplo, que tienen una enumeración de los números racionales en un orden no comprable, entonces tendríamos que asumir que una enumeración no comprable de las racionales no existe, o la diagonal le da un número innecesable?

¿Por qué no solo un número irracional?

o supongamos que tuvimos una enumeración de un conjunto contable pero no recursivo.¿La diagonalización produciría un número inacutable?

Para el conjunto de todos los números computables, sí.

O si asumimos que tenemos una enumeración computable de los números reales computables, y hicimos la diagonalización en ella, entonces tendríamos que asumir que el número en la diagonal no es necesario?

Es claramente computable, lo que demuestra que no puede tener una enumeración computable de todos los números reales computables.