Bukti ketidakpastian tidak dengan pengurangan dari masalah penghentian

Cara yang biasa untuk membuktikan ketidakpastian adalah dengan mereduksi dari masalah RE-complete seperti masalah penghentian, validitas dalam logika urutan pertama, kepuasan persamaan Diophantine, dll.

Diketahui bahwa ada masalah yang berulang secara berulang, tetapi tidak dapat dipastikan yang tidak menyelesaikan-RE, tetapi ini adalah konstruksi buatan (yaitu, set yang telah ditentukan hanya untuk menunjukkan hasil "kepadatan" ini).

Bagaimana seseorang mengatasi pembuktian ketidakpastian tanpa pengurangan dari masalah RE-complete? Diagonalisasi?

Seseorang dapat menunjukkan secara langsung bahwa kompleksitas Kolmogorov tidak dapat dihitung, lihat misalnya Sipser, edisi ke-3, masalah 6.23.

Pertimbangkan apa yang saya suka sebut sebagai masalah MENJADI KONSISTEN.

$M$

• $M$

• $M$

• $M$

(Tentu saja ini bukan bahasa, tetapi lebih seperti analog komputabilitas dari masalah janji.)

Sekarang, dengan modifikasi bukti asli Turing, cukup mudah untuk menunjukkan bahwa GUESSING KONSISTEN tidak dapat diputuskan (saya akan meninggalkan itu sebagai latihan untuk Anda).

$A$$A$

Jika yang Anda cari adalah bukti yang bukan a) pengurangan dari masalah lengkap yang diketahui, atau b) diagonalisasi langsung (yang ditunjukkan oleh berbagai komentar Anda), maka sejauh yang saya tahu Anda kurang beruntung. Semua bukti yang saya sadari bukan dengan reduksi - termasuk yang ada di jawaban luar biasa lainnya yang diberikan di sini oleh Aaronson dan Kjos-Hanssen - dilanjutkan dengan diagonalisasi langsung.

Dan semua diagonalisasi itu pada dasarnya adalah bukti yang sama . Beberapa dari mereka sedikit varian pada bukti yang menghasilkan pernyataan sedikit lebih kuat / lebih lemah, tetapi bukti itu sendiri biasanya hanya variasi yang sangat sedikit. (Dan semua bukti ini pada dasarnya sama dengan bukti asli Cantor tentang kardinalitas, yang sama dengan bukti ketidaklengkapan Godel dan Chaitin, yang merupakan semua versi teorema dari paradoks Russell ... Begitu banyak sehingga pada satu Poin saya bertanya-tanya apakah seseorang dapat memformalkan semacam teorema pembalikan matematika yang mengatakan bahwa pada dasarnya hanya ada satu bukti seperti itu.)

Akan tetapi, ada baiknya kita menunjukkan bahwa ada bukti dari pernyataan lain - biasanya dari rasa yang berbeda - yang merupakan diagonalisasi yang benar-benar, benar-benar berbeda dari diagonalisasi yang digunakan untuk membuktikan misalnya keraguan terhadap masalah penghentian.