Qual è la rilevanza del calcolo quando si applica la diagonallizzazione?

Question

Quando si pensa alla diagonalizzazione, ho sempre sorvolato se l'enumerazione o meno la diagonale è calcolato o meno.Quando importa?

Dì ad esempio, che hanno un'enumerazione dei numeri razionali in un ordine non computabile, allora dovremmo presumere che sia un'enumerazione non computabile dei razionali, o la diagonale fornisce un numero non computabile? o supponiamo di avere un'enumerazione di un set numerabile ma non ricorsivo.Diagonalizzazione produrrebbe un numero non computabile?

o Se assumiamo che abbiamo un'enumerazione calcolabile dei numeri reali calcolabili, e facciamo la diagonalizzazione su di esso, allora dovremmo presumere che il numero sulla diagonale sia non computabile?Qualcosa sembra sbagliato qui.

In generale, quali sono le catture quando si eseguono la diagonale pertinere a Computabilità?

Answer 1

Non ci sono catture. La diagonale è una tecnica di prova molto generale che funziona in impostazione classica, costruttiva e calcolabile. È usato per dimostrare:

.
• che non vi è alcuna sorpresa da un set al suo powerset
• che i numeri reali non possono essere enumerati
• che i numeri reali calcolabili non possono essere enumerabili computabili
• che l'oracolo di arresto non esiste
• ecc.

Nella sua forma più generale è noto come Teorema del punto fisso del Lawvere .

chiedi cosa succede se diagonalizzi contro i numeri razionali. Non hai specificato in quale forma vengono dati i razionali, suppongo che tu intenda le loro espansioni decimali. La diagonale produrrà un numero reale che non è un membro dell'enumerazione (questo reale potrebbe essere razionale o irrazionale, a seconda di quale enumerazione hai iniziato con). Se si inizia con un'enumerazione non computabile, il risultato potrebbe non essere computabile. Se si avvia con un'enumerazione calcolabile, otterrai un risultato calcolato, poiché la diagonale conserva la calcurabilità.

Allo stesso modo, se si prende un'enumerazione calcolabile di numeri reali calcolabili (dati come sequenze infinite di cifre), il risultato della diazionalità sarà un numero reale calcolato che non è un membro dell'enumerazione iniziale.

Answer 2

Non sono sicuro di come rispondere alla domanda generale, ma per quelli specifici:

.

Dì ad esempio, che hanno un'enumerazione dei numeri razionali in un ordine non computabile, allora dovremmo presumere che sia un'enumerazione non computabile dei razionali, o la diagonale fornisce un numero non computabile?

Perché non solo un numero irrazionale?

.

o supponiamo di avere un'enumerazione di un set numerabile ma non ricorsivo.Diagonalizzazione produrrebbe un numero non computabile?

Per il set di tutti i numeri calcolabili sì.

.

O se presupponiamo di avere un'enumerazione calcolabile dei numeri reali calcolabili, e facciamo diagonalizzazione su di esso, allora dovremmo presumere che il numero sulla diagonale sia non computabile?

È chiaramente calcolabile, dimostrando che non è possibile avere un'enumerazione calcolabile di tutti i numeri reali calcolabili.