"Ahli logika terkenal telah membuat kesalahan yang memalukan di sini," sebuah garis dari SICP. Apa yang dimaksud dengan ini?

Berikut ini konteksnya ( Struktur dan Interpretasi Program Komputer , bagian 1.1.8, di bawah judul "Nama lokal"):

Parameter formal dari suatu prosedur memiliki peran yang sangat khusus dalam definisi prosedur, karena tidak peduli apa nama parameter formal tersebut. Nama seperti itu disebut variabel terikat , dan kami mengatakan bahwa definisi prosedur mengikat parameter formalnya. Arti definisi prosedur tidak berubah jika variabel terikat secara konsisten diganti namanya di seluruh definisi.

Di akhir baris terakhir, ada catatan kaki (26), yang mengatakan:

Konsep penggantian nama yang konsisten sebenarnya halus dan sulit untuk didefinisikan secara formal. Ahli logika terkenal telah membuat kesalahan yang memalukan di sini.

Apa atau siapa yang dimaksud teks? Mengapa mendefinisikan "penggantian nama yang konsisten" menjadi sulit, ahli logika mana yang membuat kesalahan saat mencoba mendefinisikan ini, dan kesalahan apa itu?

logic ubadub
sumber

Saya memberi tahu siswa saya bahwa satu-satunya cara untuk memahami "mengubah nama variabel terikat secara konsisten" adalah dengan mengimplementasikan hal itu dengan benar. Banyak buku logika menghindari masalah ini, memberikan prosedur penggantian nama yang tidak lengkap, atau setidaknya menghilangkan bukti bahwa prosedur penggantian nama yang diberikan adalah benar. Tapi saya tidak tahu gosip tertentu yang dirujuk buku itu.

Andrej Bauer

Tepatnya berurusan dengan penggantian nama variabel, nama baru, penggantian tangkap, dan sejenisnya, adalah salah satu hal paling sepele yang dengan cepat menjadi sangat rumit dalam definisi dan bukti. Untuk masalah sepele seperti itu, seseorang tidak ingin menghabiskan lebih dari jumlah siklus mental yang sepele, namun lebih dari itu diperlukan untuk menghindari banyak penangkapan / tabrakan rumit / dll. Seringkali, orang-orang PL berhati-hati dalam definisi, tetapi kemudian memanggil "konvensi Barendregt" dan mengabaikan masalah, agak menyalahgunakan "segar" di sana-sini, bila diperlukan.

chi

Saya akan menghargai jawaban yang lebih konkret, di bawah ini di kotak jawaban, jika memungkinkan. Komentar-komentar ini masih membuat masalah ini terdengar misterius karena Anda telah menulisnya untuk dibaca oleh seseorang yang sudah akrab dengan masalah yang sedang dihadapi, sedangkan saya tidak

ubadub

@chi khususnya saya sangat menghargai membaca rekomendasi yang berhubungan dengan topik ini, jika Anda punya. Terima kasih sebelumnya

ubadub

Ini adalah jawaban parsial: Saya tidak tahu kesalahan atau orang mana yang SICP rujuk. Saya hanya bisa memberikan beberapa petunjuk tentang "mengapa" penggantian nama variabel bisa menyakitkan untuk ditangani secara tepat.

Pertama-tama, tampaknya sepele untuk didefinisikan. Misalnya, kita bisa mengganti nama variabel terikat dalam jumlah yang diindeks

\sum_{x} e = \sum_{y} (e {y / x})

$\sum_x e = \sum_y (e\{y/x\})$

di mana $e$ adalah ekspresi apa pun, dan $e\{y/x\}$ menunjukkan penggantian sintaksis masing-masing $x$ dengan $y$ . Sepele, kan?

Nah, jika kita membabi buta menerapkan aturan di atas, kita dapatkan

\sum_{x} (x + y) = \sum_{y} (y + y)

$\sum_x (x+y) = \sum_y (y+y)$

Itu tidak baik. Kita perlu menambahkan persyaratan " $y$ tidak terjadi di $e$ ", atau kita mendapatkan bentrokan nama.

Sekarang, pertimbangkan penggantian nama yang benar ini

\sum_{x} \sum_{y} (x + y) = \sum_{x} \sum_{z} (x + z)

$\sum_x \sum_y (x+y) = \sum_x \sum_z (x+z)$

jika kita ingin mengganti nama $x$ menjadi $y$ , dengan aturan di atas kita dapat melakukannya di sisi kanan, tetapi tidak di sisi kiri. Itu merepotkan, karena keduanya hanya berbeda dengan penggantian nama, jadi mereka harus ditangani dengan cara yang sama.

Pendekatan khas di sini adalah untuk menggunakan mendefinisikan kembali $e\{y/x\}$ sebagai "substitusi penangkapan-hindari", dan mengendurkan persyaratan " $y$ tidak terjadi di $e$ " dan menggunakan sebagai gantinya " $y$ tidak terjadi gratis di $e$ ".

Kami kemudian mendefinisikan kejadian gratis:

f r e e (x) = {x} f r e e (e + t) = f r e e (e) \cup f r e e (t) f r e e (\sum_{x} e) = f r e e (e) ∖ {x}

$free(x)=\{x\} \qquad free(e+t) = free(e)\cup free(t) \qquad free(\sum_x e) = free(e)\setminus\{x\}$

Akhirnya, tangkap menghindari subtitusi:

$x\{t/y\}$ adalah $t$ jika $x=y$ , dan $x$ sebaliknya.
$(e+e')\{t/y\} = e\{t/y\} + e'\{t/y\}$ (huruf mudah)
$(\sum_x e)\{t/y\} = ??$

Kasus terakhir menyakitkan. Jika $x=y$ , substitusi adalah no-op, karena kami ingin itu hanya mempengaruhi variabel bebas, dan $x$ terikat. Jadi hasilnya hanya $\sum_x e$ .

Jika $y\neq x$ , kami ingin mengatakan itu $(\sum_x e)\{t/y\} = \sum_x (e\{t/y\})$ . Namun ini salah, secara umum, karena jika $x$ terjadi gratis di $t$ kita mendapatkan tangkapan.

Mendesah. Jadi, kita membiarkan $z$ menjadi "pertama" variabel yang 1) tidak $y$ , 2) tidak bebas dalam $t$ , dan 3) tidak bebas dalam $\sum_x e$ . Di sini, "pertama" berarti bahwa kita perlu mengatur urutan nama-nama variabel dengan baik (misalnya dengan memilih penambangan antara nama dan alami). Kemudian, kami akhirnya membiarkan $(\sum_x e)\{t/y\} = \sum_z (e\{z/x\}\{t/y\})$ .

Saya harap saya melakukannya dengan benar. (Omong-omong upaya pertama saya salah)

$z$ $z$

$\alpha$ $\lambda x$

Sekarang, bayangkan harus berurusan dengan definisi rumit ini setiap kali kita ingin membuktikan sesuatu dalam teori PL. Kita bisa, tetapi kita tidak mau. Membosankan, membosankan, rentan kesalahan, mengacaukan buktinya dan tidak memberikan wawasan kepada pembaca. Untuk alasan ini, banyak penulis PL hanya melewatkan detail dengan mengatakan (atau bahkan menerima begitu saja!) Bahwa istilah harus diambil "hingga penggantian nama variabel", bahwa semua variabel terikat dianggap berbeda dari apa pun yang mereka perlukan untuk membedakan, bahwa kita menganggap "konvensi Barendregt", atau sesuatu dengan efek yang sama.

Jujur saja, ini curang dalam bukti. Kita juga bisa menambahkan "wink wink, nudge nudge, say no more!" dalam semangat yang sama. Kami pada dasarnya meminta belas kasihan dan memberi tahu pembaca: "lihat, ini membosankan, saya tidak ingin melakukannya, Anda tidak ingin membacanya - kami berdua tahu bahwa, dengan upaya besar, kami dapat menulis ulang bukti ini untuk sertakan semua detail ".

Secara teknis, itu adalah mungkin untuk mengeksploitasi shortcut ini untuk membuktikan pernyataan palsu. Namun, reviewer bukti yang berpengalaman tahu apa yang "baik secara moral" dan bisa menjadi sempurna (dengan usaha keras), dan apa yang mencurigakan. Yang terakhir dapat mencakup sesuatu yang tergantung pada pilihan sebenarnya dari nama terikat (jadi kami tidak benar - benar bekerja "hingga" seperti yang dijanjikan!). Dalam kasus tersebut, ulasan akan meminta rincian lebih lanjut, sehingga dia dapat diyakinkan.

chi
sumber

"Ahli logika terkenal telah membuat kesalahan yang memalukan di sini," sebuah garis dari SICP. Apa yang dimaksud dengan ini?

Jawaban: