Soal komputabilitas mengajar

Saya mengalami kesulitan mengajarkan konsep fungsi yang dapat dihitung. Saya mencoba mengembangkan ide mengapa para peneliti seperti Hilbert / Ackermann / Godel / Turing / Church / ... menciptakan gagasan 'kemampuan komputasi'. Para siswa segera bertanya: "apa artinya komputasi?" dan saya tidak bisa menjawab kecuali saya mengajari mereka mesin Turing, dan kemudian menjawab "suatu fungsi dapat dihitung jika mesin Turing menghitungnya."

Begitu,

Apakah ada deskripsi komputabilitas yang tidak mengharuskan beralih ke mesin Turing, kalkulus-λ, atau model komputasi yang serupa? Bahkan deskripsi yang intuitif akan cukup.

75 tahun yang lalu tidak ada komputer di sekitarnya. Jadi orang harus menjelaskan dengan sangat hati-hati ide matematika dari komputer.

Hari ini semua orang tahu apa itu komputer, dan mungkin membawa komputer hampir sepanjang waktu. Ini dapat digunakan dengan sangat sukses dalam mengajar karena Anda dapat melewatkan ide yang agak ketinggalan zaman tentang mesin dengan selotip. Maksud saya, siapa yang menggunakan kaset? (Saya tahu, saya tahu, Anda merasa terhina dan Turing adalah pria yang hebat dan semua itu, dan saya setuju dengan Anda).

Anda masuk saja ke kelas dan bertanya: jadi apakah ada yang tidak bisa dihitung oleh iPhone Anda? Ini segera membawa Anda ke pertanyaan tentang sumber daya terbatas. Lalu Anda berkata: yah seandainya mesin Anda benar-benar memiliki memori tidak terbatas, adakah yang tidak bisa dihitung? Dan Anda menjunjung sedikit lebih banyak dan membatasi perhatian pada fungsi-fungsi teori angka (karena Anda tidak tertarik pada Facebook saat ini). Anda harus menjelaskan sedikit bagaimana komputer bekerja (seperti yang disebutkan dalam komentar, ada baiknya jika siswa tahu bahasa pemrograman karena Anda dapat menggunakannya daripada mendeskripsikan perangkat keras), tetapi setelah itu Anda dapat menggunakan semua argumen klasik komputabilitas. teori untuk memperoleh hasil. Tidak masalah bahwa gambaran mental siswa Anda tentang sebuah mesin adalah iPhone. Bahkan, itu penting:lebih relevan bagi mereka untuk mengetahui bahwa iPhone mereka tidak dapat melakukan hal-hal tertentu.

"Suatu fungsi dapat dihitung jika ada 'prosedur efektif' untuk beralih dari input ke output." Ketika memperkenalkan topik ini, di masa lalu saya telah menunjukkan bagaimana mereka (para siswa) memiliki prosedur yang efektif untuk menyelesaikan persamaan kuadrat, tetapi tidak memiliki satu untuk menyelesaikan persamaan derajat 5 atau lebih. Ini dapat memisahkan ke dalam diskusi tentang bagaimana seseorang dapat memformalkan 'prosedur yang efektif', tetapi diskusi itu adalah sesuatu yang Anda inginkan terjadi, jadi saya pikir itu adalah fitur, bukan bug.

Mungkin intinya adalah bahwa semua model ini bertujuan untuk menangkap apa konsep komputabilitas. Fakta bahwa mereka semua setara, berarti bahwa gagasan yang mereka coba tangkap adalah kuat. Jadi, meskipun ini tidak luput dari dilema Anda, ketahanan ini memberikan kepercayaan pada anggapan bahwa "suatu fungsi dapat dihitung jika ada mesin Turing yang menghitungnya".

Saya mulai bertanya, "adakah pertanyaan yang tidak bisa dijawab oleh komputer dengan meyakinkan?" dan memimpin diskusi ke arah pertanyaan filosofis seperti "jika pohon tumbang di hutan apakah itu bersuara?" atau "apakah ada kehidupan setelah kematian?" Kami dengan cepat mendapatkan konsensus bahwa bahasa manusia dapat mengekspresikan pertanyaan ya / tidak yang melibatkan paradoks atau konsep yang tidak dapat diungkapkan secara matematis, dan, ya, ada pertanyaan yang tidak dapat dihitung.

Lalu saya bertanya secara retoris apakah ada pertanyaan yang tidak dapat dihitung tentang konsep yang bisa direpresentasikan dalam komputer, misalnya integer dan grafik. Saya mengatakan bahwa ya, salah satu contohnya adalah masalah penghentian yang terkenal, yaitu tentang memeriksa deskripsi suatu program dan mengatakan apakah ia memiliki loop yang tidak terbatas. Secara intuitif, ternyata loop tak terbatas seperti lubang hitam, dan program apa pun yang mengamati loop tak terbatas bisa terjebak dalam loop tak terbatas itu sendiri. Jadi setiap prosedur yang menjawab masalah itu dapat berjalan selamanya, jadi dengan definisi "algoritma" tidak ada algoritma yang bisa menjawab masalah yang terputus.

Lalu saya menyelam kembali ke bukti pada mesin Turing.

Nah, suatu fungsi dapat dihitung jika ia menerima input yang dibentuk atau dihasilkan oleh pola tertentu. Pola spesifik berarti semua input harus memiliki relasi, input tertentu dapat dihasilkan oleh input sebelumnya atau berikutnya. Jika input tidak memiliki jenis urutan ini, maka tidak ada kemungkinan untuk mengembangkan model atau fungsi yang dapat menerima. Satu hal lagi yang ingin saya katakan adalah bahwa ada perbedaan mendasar antara mesin dan manusia. Mesin tidak dapat dibentuk untuk input non-sekuensial tetapi manusia. Juga ini adalah gangguan besar membuat robot berperilaku manusia yang sebenarnya.