Teori realisasi: perbedaan kekuatan antara kalkulus Lambda dan Mesin Turing

Saya memiliki tiga subquestions terkait, yang disorot oleh poin-poin di bawah ini (tidak, mereka tidak dapat dibagi, jika Anda bertanya-tanya). Andrej Bauer menulis, di sini , bahwa beberapa fungsi dapat diwujudkan melalui mesin Turing, tetapi tidak melalui lambda-calculus. Langkah utama dari alasannya adalah:

Namun, jika kita menggunakan kalkulus lambda, maka [program] c seharusnya menghitung angka yang mewakili mesin Turing dari istilah lambda yang mewakili fungsi f. Ini tidak dapat dilakukan (saya dapat menjelaskan mengapa, jika Anda mengajukannya sebagai pertanyaan terpisah).

• Saya ingin melihat penjelasan / bukti informal.

Saya tidak melihat bagaimana menerapkan teorema Rice di sini; itu akan berlaku untuk masalah "apakah mesin turing ini T dan lambda-istilah L ini setara?", karena menerapkan predikat ini ke istilah yang setara memberikan hasil yang sama. Namun, fungsi yang diperlukan mungkin menghitung TM yang berbeda, tetapi setara, untuk istilah lambda yang berbeda, tetapi setara.

• Terlebih lagi, jika masalahnya adalah dengan introspeksi terhadap istilah lambda, saya pikir bahwa meloloskan pengodean Gödel dari istilah lambda juga dapat diterima, bukan?

Di satu sisi, mengingat bahwa contohnya melibatkan komputasi, dalam kalkulus lambda, jumlah langkah yang dibutuhkan oleh Mesin Turing untuk menyelesaikan tugas yang diberikan, saya tidak terlalu terkejut.

• Tetapi karena di sini lambda-calculus tidak dapat menyelesaikan masalah yang berhubungan dengan mesin Turing, saya bertanya-tanya apakah seseorang dapat mendefinisikan masalah yang sama untuk lambda-calculus dan membuktikannya tidak dapat diselesaikan untuk mesin Turing, atau sebenarnya ada perbedaan kekuatan yang mendukung Mesin Turing (yang akan mengejutkan saya).

John Longley memiliki artikel survei yang sangat luas yang membahas masalah-masalah yang terlibat, "Pengertian tentang Komputasi pada Jenis yang Lebih Tinggi" .

Ide dasarnya adalah bahwa tesis Church-Turing hanya tentang fungsi dari - dan ada lebih banyak perhitungan dari itu! Secara khusus, ketika kita menulis program, kita menggunakan fungsi dengan tipe yang lebih tinggi (seperti ).$\mathbb{N} \to \mathbb{N}$$(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$

Untuk mendefinisikan sepenuhnya model perhitungan tipe yang lebih tinggi, kita perlu menentukan konvensi pemanggilan fungsi, untuk memungkinkan satu fungsi memanggil fungsi lain yang diterimanya sebagai argumen. Dalam kalkulus lambda, konvensi pemanggilan standar adalah bahwa kami mewakili fungsi dengan istilah lambda, dan satu-satunya hal yang dapat Anda lakukan dengan lambda dalam kalkulus lambda adalah menerapkannya. Dalam penyandian khas dengan mesin Turing, kami meneruskan fungsi sebagai argumen dengan memperbaiki penyandian Godel tertentu, dan kemudian string yang mewakili indeks mesin yang ingin Anda sampaikan sebagai argumen.

Perbedaan dalam pengkodean berarti bahwa Anda dapat menganalisis sintaks argumen dengan pengkodean gaya-TM, dan Anda tidak bisa dengan representasi lambda-kalkulus standar. Jadi, jika Anda menerima istilah lambda untuk fungsi ketik , Anda hanya dapat menguji perilakunya dengan meneruskannya khusus - Anda tidak dapat menganalisis struktur istilah dengan cara apa pun. Ini hanya informasi yang tidak cukup untuk mengetahui kode istilah lambda.$\mathbb{N} \to \mathbb{N}$$n$

Satu hal yang perlu diperhatikan adalah bahwa dengan jenis yang lebih tinggi, jika suatu bahasa kurang ekspresif pada satu urutan, itu lebih ekspresif pada satu urutan, karena fungsi bersifat contravarian. Demikian pula ada fungsi yang dapat Anda tulis dalam LC yang tidak dapat Anda gunakan dengan pengkodean gaya TM (karena mereka bergantung pada fakta bahwa Anda dapat melewati argumen fungsional dan tahu bahwa penerima tidak dapat melihat ke dalam fungsi yang Anda berikan) .

EDIT: Berikut adalah contoh fungsi yang dapat didefinisikan dalam PCF, tetapi tidak dalam penyandian TM + Goedel. Saya akan mendeklarasikan isAlwaysTruefungsinya

 isAlwaysTrue : ((unit → bool) → bool) → bool

yang harus mengembalikan true jika argumennya mengabaikan argumennya dan selalu mengembalikan true, harus mengembalikan false jika argumennya mengembalikan false pada input apa pun, dan masuk ke loop jika argumennya masuk ke loop pada input apa pun. Kita dapat mendefinisikan fungsi ini dengan cukup mudah, sebagai berikut:

isAlwaysTrue p = p (λ(). true) ∧ p (λ(). false) ∧ p (λ(). ⊥)

di mana ⊥adalah penghitungan looping dan ∧adalah dan operator pada boolean. Ini berhasil karena hanya ada tiga penghuni unit → booldi PCF, dan karenanya kami dapat menyebutkannya secara mendalam. Namun, dalam model gaya penyandian TM + Goedel, pdapat menguji berapa lama argumennya untuk mengembalikan jawaban, dan mengembalikan jawaban yang berbeda berdasarkan itu. Jadi implementasi isAlwaysTruedengan TM akan gagal memenuhi spesifikasi.

Apa kata Neel, dan juga yang berikut.

Saya ingin menekankan ( lagi , lagi dan lagi ) bahwa representasi masalah input dan output. Jika kita diizinkan untuk mengubah representasi, kita dapat mencapai apa saja (misalnya, membuat fungsi yang diberikan dapat dikomputasi). Jadi, beralih dari representasi fungsi oleh -terms ke representasi oleh angka Gödel tidak dapat diterima jika model perhitungan kami adalah -calculus (karena dengan demikian operasi currying menjadi tidak bisa dihitung oleh -calculus).$\mathbb{N} \to \mathbb{N}$$\lambda$$\lambda$$\lambda$

Pernyataan yang dapat diwujudkan dalam model -term tetapi tidak dalam model mesin Turing adalah "tidak setiap fungsi memiliki kode Gödel", yang agak konyol. Saya akan mencoba membuat yang lebih baik dan mengedit jawaban ini.$\lambda$$\mathbb{N} \to \mathbb{N}$

Edit pada 2013-10-07: Inilah yang saya maksud dengan "currying menjadi uncomputable". Misalkan kita menggunakan -calculus yang tidak diketik sebagai model komputasi kita, tetapi kemudian kita memutuskan bahwa kita harus mewakili peta dengan kode Gödel (dari mesin Turing, dikodekan sebagai angka Gereja). Kedengarannya tidak berbahaya, bukan? Bagaimanapun kami percaya mantra "Mesin Turing dan calculus adalah sama".$\lambda$$\mathbb{N} \to \mathbb{N}$$\lambda$

Nah, agar representasi baru ini benar-benar menjadi representasi valid dari , kita juga perlu merealisasikan aplikasi dan currying (karena "mewakili fungsi" berarti hal yang sama dengan "untuk mewakili suatu objek eksponensial "). Secara khusus, kita perlu sebuah -istilah seperti itu, setiap kali Gereja angka merupakan maka diwakili oleh . (Di sini saya menulis untuk angka Gereja yang mewakili angka .) Seperti$\mathbb{N} \to \mathbb{N}$$\lambda$$\mathtt{app}$$\overline{n}$$f : \mathbb{N} \to \mathbb{N}$$f(k)$$\mathtt{app} \; \overline{n} \; \overline{k}$$\overline{n}$$n$$\mathtt{app}$sudah tersedia karena jumlah penerjemah untuk mesin Turing, diimplementasikan dalam -calculus.$\lambda$

Tapi bagaimana dengan kari? Untuk itu kita perlu yang berikut ini. Misalkan adalah himpunan yang diwakili. Diberikan peta apa saja dihitung oleh a -term , kita perlu menunjukkan bahwa transposisi juga dikomputasi oleh beberapa -term . Tetapi perhatikan contoh di mana adalah himpunan o fmaps diwakili oleh -terms, dan adalah aplikasi. Maka akan menjadi peta yang bertindak sebagai identitas padaf : X × N → N λ t ˜ f : X → ( N → N ) λ s X N → N λ f ˜ f N → N λ λ N → N$X$$f : X \times \mathbb{N} \to \mathbb{N}$$\lambda$$t$$\tilde{f} : X \to (\mathbb{N} \to \mathbb{N})$$\lambda$$s$$X$$\mathbb{N} \to \mathbb{N}$$\lambda$$f$$\tilde{f}$$\mathbb{N} \to \mathbb{N}$, tetapi realizer-nya adalah -term yang mengonversi -terms yang mewakili peta menjadi kode Gödel yang sesuai. Seperti -term tidak ada (misalnya karena itu akan terputus dalam model semantik topologis).$\lambda$$\lambda$$\mathbb{N} \to \mathbb{N}$$\lambda$

Anda dapat mencoba menolak bahwa saya seharusnya tidak menggunakan set peta diwakili khusus diwakili oleh -terms, karena kami "setuju" bahwa semua itu harus diwakili oleh kode Gödel . Tapi kamu salah. Pertama-tama, saya bisa menggunakan berbeda dengan bukti yang lebih rumit yang akan menghindari Anda tetapi masih mencapai hasil yang sama. Kedua, ada dalam kategori dan definisi eksponensial mensyaratkan bahwa pekerjaan kari sehubungan dengan semua objek. Anda harus menghormati kategorinya. Anda tidak bisa hanya membantai secara acak dan mengambil beberapa objek (well, Anda bisa tetapi kemudian Anda adalah tukang daging).N → N λ X $X$$\mathbb{N} \to \mathbb{N}$$\lambda$$X$$X$