Kami belajar tentang konsep enumerasi fungsi. Dalam praktiknya, mereka berhubungan dengan bahasa pemrograman.
Dalam komentar yang lewat, profesor menyebutkan bahwa kelas semua fungsi total (yaitu fungsi yang selalu berakhir untuk setiap input) tidak dapat dihitung. Itu berarti bahwa kita tidak dapat merancang bahasa pemrograman yang memungkinkan kita untuk menulis semua fungsi total tetapi tidak ada yang lain --- yang akan menyenangkan untuk dimiliki!
Jadi bagaimana mungkin kita (tampaknya) harus menerima potensi non-terminasi jika kita menginginkan kekuatan komputasi yang layak?
Karena diagonalisasi. Jika adalah pencacahan dihitung dari semua fungsi total dihitung dari N ke N , sehingga setiap f e adalah total, maka g ( i ) = f i ( i ) + 1 juga akan menjadi komputasi Total fungsi, tetapi itu tidak akan di enumerasi. Itu akan bertentangan dengan asumsi tentang urutan. Dengan demikian, tidak ada penghitungan fungsi yang dapat dikomputasi dengan tepat dari total fungsi yang dapat dihitung.(fe:e∈N)NNfeg(i)=fi(i)+1
Misalkan kita berpikir tentang fungsi komputasi universal , di mana "universal" berarti h adalah fungsi biner yang dapat dihitung dan bahwa untuk setiap total fungsi unary yang dapat dihitung f ( n ) ada beberapa e sehingga f ( i ) = h ( e , i ) untuk semua i . Maka harus ada beberapa e sehingga g ( n ) = h ( e , n )h(e,i)hf(n)ef(i)=h(e,i)ieg(n)=h(e,n)bukan fungsi total, karena paragraf sebelumnya. Kalau tidak, akan memberikan penghitungan yang dapat dihitung dari total fungsi unary yang dapat dihitung yang mencakup semua fungsi unary yang dapat dihitung total.h
Dengan demikian persyaratan bahwa setiap fungsi adalah sistem fungsi adalah total tidak sesuai dengan keberadaan fungsi universal dalam sistem itu. Untuk beberapa sistem yang lemah, seperti fungsi rekursif primitif, setiap fungsi adalah total tetapi tidak ada fungsi universal. Sistem yang lebih kuat yang memiliki fungsi universal, seperti Turing computability, harus memiliki fungsi parsial untuk memungkinkan adanya fungsi universal.
Saya hanya ingin menambahkan bahwa seseorang menemukan apa yang tampak sebagai celah dalam diagonalisasi. Jika Anda menggunakan representasi yang diketik untuk program, Anda dapat menggunakan sistem tipe untuk melarang diagonalisasi dan membuat penerjemah mandiri total. Lihat Menerobos Penghalang Normalisasi: Penerjemah Mandiri untuk F-omega untuk detail.
menetas22
Tentu saja, Sistem F bukan sistem lengkap Turing. Makalah yang Anda tautkan menarik; tampaknya mereka berhasil memanfaatkan ketidaklengkapan-Turing dengan cara yang menarik.
Carl Mummert
Saya tidak mengerti mengapa "maka juga akan menjadi fungsi total yang dapat dihitung". Jika g adalah fungsi komputasi total maka then k , f k =g(i)=fi(i)+1g , maka mengevaluasi g ( k ) memerlukan evaluasi g ( k ) = f k ( k ) + 1 = g ( k ) + 1∃ k , fk= gg( k )g( k ) = fk( k ) + 1 = g( K ) + 1: kontradiksi. Jadi tampaknya jika ada penghitungan total fungsi yang dapat dihitung, kita bahkan tidak dapat membangun , sehingga kita tidak dapat mencapai kontradiksi untuk menyangkal hipotesis awal (Kita dapat mencapai kontradiksi, tetapi itu hanya membuktikan g menjadi total yang dapat dihitung). gg
agemO
Dan bahkan menggunakan diagonal bergeser untuk menghindari masalah ini tampaknya mengarah pada kontradiksi.
agemO
10
Hanya untuk memperjelas, kita perlu membedakan fungsi matematika (saya akan menyebutnya fungsi dan sering ada banyak dari mereka sehingga mereka sama sekali tidak dapat dihitung) dan fungsi yang dapat Anda tulis: Saya akan memanggil mereka program atau juga fungsi yang dapat dihitung .
Subset dari himpunan yang dapat dihitung ESE disebut dihitung jika ada program yang, mengingat unsur dari E merespon "ya" jika x ∈ S dan "tidak" jika x ∉ S . (Dan dia selalu harus merespons sesuatu). Suatu set disebut berulang-ulang enumerable jika program berwenang untuk tidak merespons alih-alih mengatakan "tidak". (Ini setara dengan mengharuskan program harus mencetak semua elemen S dalam urutan apa pun)xEx ∈ Sx ∉ SS
Himpunan semua program yang total pada himpunan terbatas dapat dihitung karena Anda dapat menulis penerjemah yang menjalankan program pada semua elemen himpunan terbatas dan mengembalikan "ya" jika semuanya berakhir. (Tapi tidak bisa melihat apakah ada di antara mereka yang tidak)
Dosen Anda mengatakan bahwa himpunan semua program yang total pada suatu himpunan tak terhingga ini tidak enumerable karena Anda tidak bisa hanya menjalankan program Anda pada jumlah tak terbatas elemen.
Tetapi ini tidak berarti ini buruk:
Misalnya kumpulan jika semua program yang terbukti total dapat dihitung karena Anda dapat menghitung semua bukti dan memeriksa secara mekanis apakah mereka membuktikan program Anda total.
Bahkan satu set enumerable tidak akan praktis, karena Anda mungkin harus menunggu selamanya tanpa yakin apakah prosedur akan berakhir suatu hari. Saya tidak melihat cara menggunakan program yang menghitung semua fungsi total ...
Ada beberapa bahasa pemrograman di mana semua yang Anda tulis dijamin akan berakhir hanya dengan mengetik statis! Bahkan ada beberapa yang menjamin Anda terikat polinomial. Mereka sebagian besar bersifat akademis untuk saat ini, menulis dengan huruf-huruf itu mungkin akan membuat Anda lebih merasakan kendala daripada menulis dengan Python, tetapi ada banyak peneliti yang mengerjakan ini.
Jadi untuk menjawab pertanyaan Anda: dalam arti tertentu, ya. Potensi non-terminasi diperlukan untuk Turing-complete (kekuatan komputasi tertinggi untuk saat ini). Tetapi saya tidak menemukan ini secara langsung relevan dengan fakta bahwa fungsi total dapat dihitung atau tidak. Anda masih dapat menulis semua program total!
"karena Anda tidak bisa hanya menjalankan program Anda pada jumlah elemen yang tak terbatas" - ini adalah argumen yang lemah karena saya mungkin tidak perlu melakukan ini jika saya dapat menyelamatkan semua informasi yang saya butuhkan dari program itu sendiri. Lihat di sini untuk pertanyaan yang menggambarkan bahaya dari alasan Anda.
Raphael
Memang. Saya tidak mengklaim itu adalah bukti (seperti biasa Anda harus membangun argumen diagonal) dan mungkin saya seharusnya tidak menggunakan kata "karena". Saya mencoba menjawab pertanyaan Anda yang (saya pikir) bukan tentang bukti pernyataan profesor Anda tetapi tentang mengapa pemutusan konflik dengan kekuatan komputasi.
Hanya untuk memperjelas, kita perlu membedakan fungsi matematika (saya akan menyebutnya fungsi dan sering ada banyak dari mereka sehingga mereka sama sekali tidak dapat dihitung) dan fungsi yang dapat Anda tulis: Saya akan memanggil mereka program atau juga fungsi yang dapat dihitung .
Subset dari himpunan yang dapat dihitung ES E disebut dihitung jika ada program yang, mengingat unsur dari E merespon "ya" jika x ∈ S dan "tidak" jika x ∉ S . (Dan dia selalu harus merespons sesuatu). Suatu set disebut berulang-ulang enumerable jika program berwenang untuk tidak merespons alih-alih mengatakan "tidak". (Ini setara dengan mengharuskan program harus mencetak semua elemen S dalam urutan apa pun)x E x ∈ S x ∉ S S
Himpunan semua program yang total pada himpunan terbatas dapat dihitung karena Anda dapat menulis penerjemah yang menjalankan program pada semua elemen himpunan terbatas dan mengembalikan "ya" jika semuanya berakhir. (Tapi tidak bisa melihat apakah ada di antara mereka yang tidak)
Dosen Anda mengatakan bahwa himpunan semua program yang total pada suatu himpunan tak terhingga ini tidak enumerable karena Anda tidak bisa hanya menjalankan program Anda pada jumlah tak terbatas elemen.
Tetapi ini tidak berarti ini buruk:
Misalnya kumpulan jika semua program yang terbukti total dapat dihitung karena Anda dapat menghitung semua bukti dan memeriksa secara mekanis apakah mereka membuktikan program Anda total.
Bahkan satu set enumerable tidak akan praktis, karena Anda mungkin harus menunggu selamanya tanpa yakin apakah prosedur akan berakhir suatu hari. Saya tidak melihat cara menggunakan program yang menghitung semua fungsi total ...
Ada beberapa bahasa pemrograman di mana semua yang Anda tulis dijamin akan berakhir hanya dengan mengetik statis! Bahkan ada beberapa yang menjamin Anda terikat polinomial. Mereka sebagian besar bersifat akademis untuk saat ini, menulis dengan huruf-huruf itu mungkin akan membuat Anda lebih merasakan kendala daripada menulis dengan Python, tetapi ada banyak peneliti yang mengerjakan ini.
Jadi untuk menjawab pertanyaan Anda: dalam arti tertentu, ya. Potensi non-terminasi diperlukan untuk Turing-complete (kekuatan komputasi tertinggi untuk saat ini). Tetapi saya tidak menemukan ini secara langsung relevan dengan fakta bahwa fungsi total dapat dihitung atau tidak. Anda masih dapat menulis semua program total!
sumber