Kesalahpahaman zombie dalam ilmu komputer teoretis

• Komputabilitas dan NP-hard dalam ilmu komputer teoretis adalah konsep yang diterapkan pada fungsi, bahasa, dan barisan tak hingga, bukan pada bilangan bulat individual atau satu pertanyaan benar/salah
• Dalam contoh Sipser, “fungsi f yang selalu mengembalikan 1 jika Tuhan ada, dan selalu 0 jika tidak ada” adalah fungsi konstan dalam kedua kasus, sehingga dapat dihitung
• P vs NP bukanlah masalah yang menerima masukan, melainkan satu pertanyaan ya/tidak, sehingga tidak bisa disebut NP-hard atau tak dapat dihitung dengan sendirinya
• Fungsi Busy Beaver secara keseluruhan tidak dapat dihitung, tetapi nilai tertentu seperti BB(6) tidak bisa diperlakukan dengan cara yang sama, karena untuk bilangan bulat apa pun k selalu ada program print k
• Inti dari kebingungan yang terus berulang adalah menerapkan konsep untuk objek tak hingga pada masalah individual; kebiasaan mencampur ketakdapatdihitungan masalah berhenti dengan ketidaklengkapan Gödel juga termasuk dalam pola yang sama

---

Jangkauan komputabilitas yang diajarkan oleh contoh Sipser

• Dalam Introduction to the Theory of Computation karya Michael Sipser, ada soal latihan yang menyingkap definisi komputabilitas
  • Misalkan f:{0,1}*→{0,1} adalah fungsi yang selalu mengembalikan 1 jika Tuhan ada, dan selalu 0 jika tidak ada
  • Pertanyaannya adalah apakah f dapat dihitung, dan jawabannya tidak bergantung pada keyakinan agama
• f dapat dihitung
  • Fungsi konstan yang selalu mengembalikan 1 dapat dihitung
  • Fungsi konstan yang selalu mengembalikan 0 juga dapat dihitung
  • Jika f adalah salah satu dari keduanya, maka f juga dapat dihitung
• Pertanyaan paralel dengan struktur yang sama memberi intuisi serupa
  • Dalam pertanyaan “jika Tuhan ada maka n=3, jika tidak maka n=5; apakah n bilangan prima”, meski n tidak ditentukan sepenuhnya, hanya dengan informasi bahwa n adalah elemen dari {3,5} kita tetap bisa mengatakan bahwa n itu prima
  • Hal yang sama berlaku untuk f: hanya ada dua kemungkinan fungsi konstan, dan itu sudah cukup spesifik untuk menyimpulkan bahwa ia dapat dihitung

Komputabilitas bukan soal sulitnya menulis program, melainkan soal keberadaannya

• Komputabilitas adalah konsep yang diterapkan pada fungsi atau barisan tak hingga
• Pada pertanyaan ya/tidak individual atau bilangan bulat individual, komputabilitas tidak dilekatkan dengan cara yang sama
• Pertanyaan intinya adalah apakah ada program komputer yang memetakan masukan ke keluaran
• Seberapa sulit memilih, menemukan, atau menulis program itu tidak termasuk dalam definisi komputabilitas
  • Bahkan jika untuk menulis program tersebut kita harus menyelesaikan soal keberadaan Tuhan, penilaian komputabilitasnya sendiri tidak berubah

Mengapa P vs NP tidak bisa disebut NP-hard

• Pertanyaan “apakah pertanyaan P versus NP itu sendiri NP-hard sehingga tak bisa diselesaikan” telah berulang berkali-kali selama 25 tahun terakhir
• NP-hard diterapkan pada fungsi atau bahasa yang menerima masukan, seperti 3SAT, Independent Set, dan Clique
  • Masukannya berupa Boolean formula, graph, dan sebagainya
  • Keluarnya adalah jawaban untuk masukan tersebut
  • Suatu masalah disebut NP-hard jika, ketika masalah itu bisa diselesaikan dalam waktu polinomial, maka melalui reduksi semua bahasa atau fungsi dalam NP juga bisa diselesaikan dalam waktu polinomial
• P vs NP bukan fungsi atau bahasa, melainkan satu pertanyaan ya/tidak
  • Tidak tertutup kemungkinan bahwa jawabannya independen dari aksioma teori himpunan Zermelo-Fraenkel
  • Namun, pertanyaan ini sendiri tidak bisa disebut tak dapat dihitung atau NP-hard
• Secara formal, memang ada program cepat yang menjawab pertanyaan P vs NP dengan tepat
  • Jika P=NP, maka ada program yang mencetak “P=NP”
  • Jika P≠NP, maka ada program yang mencetak “P≠NP”

Kebingungan yang sama berulang pada Busy Beaver

• Dalam komentar pada tulisan tentang nilai Busy Beaver 5 yang telah diputuskan, pertanyaan serupa juga terus muncul
  • “Nilai n terkecil berapa sehingga BB(n) menjadi tak dapat dihitung?”
  • “Apakah BB(6) mungkin sudah tak dapat dihitung?”
• Fungsi Busy Beaver tidak dapat dihitung
• Tetapi pada bilangan bulat individual seperti BB(6), konsep komputabilitas tidak diterapkan seperti itu
  • Apa pun bilangan bulat k yang ternyata merupakan BB(6), selalu ada program print k
  • Program ini akan mencetak bilangan bulat tersebut
• Sebaliknya, pertanyaan yang bisa diajukan adalah: untuk n tertentu, apakah nilai BB(n) tidak dapat dibuktikan dalam sistem aksioma seperti teori himpunan ZF
  • Aaronson dan Adam Yedidia membahas pertanyaan ini pada 2016
  • Rekor saat ini adalah n=745, yang merupakan perbaikan atas n=8000 dari Aaronson dan Adam
• Setiap bilangan bulat tertentu dapat dianggap “dapat dihitung”, dan yang tak dapat dihitung adalah seluruh fungsi BB

Mengapa “kesalahpahaman zombie” terus hidup

• Inti kebingungan yang berulang adalah salah menerapkan konsep yang dirancang untuk barisan tak hingga dan fungsi pada bilangan bulat individual serta masalah terbuka
• Kasus mencampur ketakdapatdihitungan masalah berhenti dengan ketidaklengkapan Gödel juga termasuk kebingungan sejenis
  • Keduanya memang berhubungan erat
  • Gödel memungkinkan kita berbicara tentang proposisi individual
  • Komputabilitas Turing adalah konsep absolut, bukan sesuatu yang relatif terhadap sistem aksioma tertentu
• Penjelasan ini berfungsi sebagai titik rujukan yang bisa ditautkan ketika kesalahpahaman edukatif yang sama muncul lagi
• Pertanyaan terakhir diarahkan pada bagaimana menenangkan kesalahpahaman yang seperti “zombie” ini

[GN⁺]

Komentar Hacker News

• Fakta bahwa konsep komputabilitas niscaya mencakup ketakterhinggaan bisa terasa cukup berlawanan dengan intuisi
  Misalnya, jika ditanya apakah ada algoritma yang menghitung kompleksitas Kolmogorov K(s) untuk sembarang string s, jawabannya, seperti yang sudah dikenal, adalah “tidak ada”. Tidak ada mesin Turing yang menerima string dengan panjang sembarang sebagai masukan lalu menghitung K(s), dan pembuktiannya singkat dengan menggunakan masalah penghentian
  Namun jika ditanya apakah ada algoritma yang menghitung K(s) untuk sembarang string s yang panjangnya kurang dari n, jawabannya adalah “ada”. Untuk n apa pun, algoritma seperti itu memang ada
  Caranya, meski mengecewakan, cukup membuat mesin Turing dengan tabel lookup raksasa yang berisi nilai K(s) untuk semua 2^n string yang mungkin. Bagaimana memperoleh tabel itu dalam praktik adalah urusan lain; implementasi tertentu memiliki deskripsi berhingga dan K(s) juga berhingga untuk semua s, jadi algoritmanya ada
  Karena itu, pertanyaan berhingga tentang objek berhingga bisa jadi tidak terlalu menarik dari sudut pandang komputabilitas. Sebab kita selalu bisa menulis program yang mencetak semua jawabannya, dan baru ketika pertanyaan diperluas ke himpunan objek tak berhingga, menjadi menarik apakah sesuatu yang berhingga dapat menjawab pertanyaan-pertanyaan tak berhingga

  • Penjelasan seperti ini bisa membuat sebagian besar ilmu komputer terdengar seperti permainan konyol yang tidak bermakna
    Pada kenyataannya, ketakterhinggaan semacam menggantikan “perilaku aproksimatif, ultimate, atau keadaan tunak pada N yang cukup besar dibanding trik sekali pakai apa pun”
    Di dunia nyata, trik seperti itu juga penting, dan konstanta serta suku berorde rendah yang diabaikan dalam perbandingan Big-O juga penting bagi kinerja nyata. Selalu ada ketegangan antara “masalah yang cukup besar hingga faktor konstanta tidak berarti” dan “masalah yang cukup kecil hingga masuk dalam rentang yang secara implisit dimaksud oleh kata konstanta”. Contohnya ketika integer 32-bit berpura-pura menjadi bilangan bulat
  • Tentu saja n menurut definisi adalah bilangan berhingga, jadi algoritma seperti itu ada
    Dari sudut pandang tak hingga, semua bilangan berhingga sebenarnya sangat kecil. Jika duduk di kursi di ujung alam semesta, 1 mil pun tidak berbeda dari 1 milimeter
    Skenario ini pada dasarnya seperti “hotel tak hingga Hilbert di atas komputer”. Jika program-program yang ada digeser satu kamar, program baru bisa ditambahkan, dan ukuran tabel yang dibutuhkan untuk komputasi tetap sama
    Secara lebih umum, kebanyakan orang memiliki intuisi yang lemah tentang cara kerja tak hingga, alef, dan matematika transfinit. Relevansinya dengan keseharian juga rendah, dan ia terjalin dalam dengan sifat-sifat emergen matematika, teori kategori, dan teori himpunan. Bukan hanya bahwa tak hingga lebih besar daripada bilangan berhingga mana pun, tetapi juga bahwa sebagian ketakterhinggaan bisa lebih besar daripada ketakterhinggaan lain; hal ini tidak langsung tampak bagi intuisi yang masih berada pada konsep “tak hingga” ala sekolah dasar
    Pertanyaan yang lebih menarik adalah apakah ada suatu n < ∞ yang memungkinkan algoritma itu dihitung, dan tentu saja jawabannya tidak, sehingga Penghargaan Turing pun melayang
  • Ini mirip dengan fakta bahwa semua komputer nyata juga hanya memiliki keadaan berhingga, sehingga lebih dekat ke mesin keadaan berhingga daripada mesin Turing
  • Bisa juga dikatakan bahwa ada algoritma sederhana untuk menghitung K(s) bagi satu s tertentu, dan karena itu juga mungkin untuk himpunan berhingga dari masukan-masukan seperti itu
    Caranya dengan mengenumerasi semua mesin Turing yang mungkin mulai dari yang panjangnya pendek, lalu mencari yang mencetak s. Jika semua mesin yang lebih pendek sudah dicoba dan tidak mencetak s, berarti kita telah menemukan mesin terpendek yang mencetak s, sehingga panjangnya adalah K(s). Mesin lain dengan panjang sama atau lebih panjang mungkin juga mencetak s, tetapi K(s) adalah nilai untuk panjang minimum, jadi tidak berubah
  • Ini mengingatkan pada kekuatan tambahan yang mungkin dimiliki P/Poly dibanding P. Sepertinya ada nama umum untuk hierarki kompleksitas sirkuit ketika sirkuit itu sendiri harus dikeluarkan oleh mesin Turing sederhana, tetapi saya tidak langsung ingat

• Berdasarkan pengalaman saya, di sini matematika konstruktivis lebih cocok dengan intuisi orang dibanding ilmu komputer klasik
  Misalnya, belum ada pembuktian konstruktif bahwa ada program yang mencetak jawaban untuk masalah P=NP
  Dalam makalah saya juga, saya membahas masalah ini terkait himpunan Julia yang dapat dihitung. Mark Braverman membuktikan bahwa semua himpunan Julia kuadratik dapat dihitung, tetapi ia sendiri menjelaskan bahwa pembuktian itu tidak dapat dihitung secara seragam. Sebagai gantinya, ia membuat 5 mesin yang menerima parameter himpunan Julia yang diinginkan dan mencoba menggambar berbagai himpunan pada resolusi yang diinginkan, dan untuk setiap himpunan Julia, salah satu dari mesin-mesin itu menggambarnya dengan benar
  Dalam matematika konstruktivis, konsep konstruktif dari himpunan kompak kira-kira berpadanan dengan himpunan yang dapat dihitung dalam arti yang dibutuhkan untuk himpunan Julia yang dapat dihitung. Namun, bahwa semua himpunan Julia kuadratik bersifat kompak tidak dapat dibuktikan secara konstruktif; kita harus membagi bidang kompleks parameter yang mungkin ke dalam beberapa wilayah, lalu membuktikan bahwa himpunan-himpunan Julia terkait bersifat kompak di dalam masing-masing wilayah
  Dalam matematika klasik, gabungan wilayah-wilayah ini adalah seluruh bidang kompleks, tetapi dalam konstruktivisme hasil ini tidak berlaku. Demikian pula, dalam matematika klasik gabungan bilangan real positif dan bilangan real yang tidak positif adalah seluruh garis real, tetapi dalam konstruktivisme hal itu juga tidak berlaku
  Pendekatan konstruktivis memberi tahu secara tepat informasi tambahan apa yang diperlukan untuk benar-benar merealisasikan komputasi. Artinya, kita harus mengetahui parameter yang diberikan termasuk ke wilayah mana di bidang kompleks, sehingga bisa tahu mesin mana dari 5 mesin yang harus dijalankan untuk memperoleh gambar yang diinginkan. Ini terasa seperti jawaban yang jauh lebih memuaskan

  • Dalam kasus P=?NP yang dikemukakan Aaronson pun, jawabannya bukan jawaban klasik seperti “P=NP”, melainkan harus berupa fungsi aktual NP→P
    Orang secara naluriah tahu bahwa mereka harus mengetahui berada di sisi mana dari pernyataan bercabang, dan bukan berarti mereka dilatih dalam logika klasik lalu melupakan fakta itu
  • Menarik bahwa “untuk setiap himpunan Julia, salah satu dari 5 mesin menggambarnya dengan benar”. Saya penasaran apakah ini pada dasarnya setara dengan pembuktian bahwa probabilitas menghitung himpunan yang benar setidaknya 1/5
    Saya juga penasaran apakah pertanyaan “mana dari 5 yang benar” dianggap memiliki pembuktian yang belum ditemukan, atau dianggap tidak dapat diputuskan seperti di dalam ZFC

• Saya melihat ini sebagai salah satu faktor yang membuat ketidakmungkinan memutuskan masalah penghentian sulit dipahami
  Kita ingin mengatakan, “Ada mesin-mesin yang terlalu rumit sehingga tidak bisa ditentukan apakah suatu mesin akan berhenti atau tidak,” tetapi di antara program sepele return true dan return false, salah satunya akan selalu memberikan jawaban yang benar untuk mesin dan input apa pun
  Mungkin kita ingin membantah, “Program-program itu tidak tahu apa-apa tentang mesin Turing, jadi harus dikecualikan,” tetapi decidability bukan membicarakan hal seperti itu. Bisa juga berpikir, “Yang tidak dapat diputuskan adalah mencari tahu program mana dari keduanya yang benar,” tetapi itu pun punya jawaban yang sudah ditentukan, benar atau salah. Masalahnya baru bisa menjadi tidak dapat diputuskan ketika diperluas ke himpunan tak hingga dari kombinasi mesin/input

  • Masalah-masalah lain yang hanya muncul pada keluarga objek juga bisa sama sulitnya dipahami pemula
    Misalnya, ruang vektor berdimensi hingga sembarang isomorfik dengan ruang dual dan ruang bidualnya dalam berbagai cara, tetapi untuk yang terakhir kita bisa memilih isomorfisme “alami” yang konsisten di seluruh ruang seperti itu, sedangkan untuk yang pertama tidak bisa
    Ini menimbulkan kebingungan seperti “Mengapa tidak isomorfik secara alami? Panjang basisnya sama! Mengapa peduli bergantung pada basis atau tidak? Bukankah bukti-bukti lain memilih basis, lalu mengapa itu boleh?”

• Menurut saya masalah dalam frasanya adalah bahwa ia membutuhkan logika modal
  “Jika Tuhan ada, tetapkan f:{0,1}*→{0,1} sebagai fungsi konstan 1; jika Tuhan tidak ada, tetapkan sebagai fungsi konstan 0. Apakah f dapat dihitung? Petunjuk: jawabannya tidak bergantung pada keyakinan agama”
  Pertanyaan yang tepat adalah apakah f akan dapat dihitung, yakni apakah ada mesin Turing M yang memenuhi f(x)=M(x) untuk semua x
  Jawabannya ya. Sebab di dunia mana pun ada mesin Turing sepele M=1_M atau M=0_M. Sebaliknya, ungkapan aslinya, “apakah f dapat dihitung,” adalah pertanyaan yang salah secara modal, lebih dekat ke pertanyaan yang secara tata bahasa tidak tepat seperti paradoks Sleeping Beauty atau Red Envelope
  Dari sudut pandang lain, ketergantungan pada Tuhan atau pada suatu fakta yang mungkin merupakan kenyataan lebih mirip direktif compiler atau pragma yang akan diisi belakangan tetapi ditentukan sebelum digunakan. Jika ditanyakan dengan benar, ini hanya soal menguraikan definisi ketat fungsi dan computability, dan keduanya didefinisikan secara eksplisit di Sipser

  • Reaksi saya juga serupa, dan saya menuliskannya di komentar tulisan Aaronson. Pertanyaan ini bukan tentang fungsi f yang dapat memanggil fungsi konstan 1 atau fungsi konstan 0 bergantung pada apakah Tuhan ada
    Ini mengatakan bahwa referen dari label nama f menjadi fungsi konstan 1 jika Tuhan ada, dan fungsi konstan 0 jika Tuhan tidak ada; kita hanya tidak tahu yang mana sebelum mengetahui apakah Tuhan ada. Karena computability kedua fungsi konstan itu jelas, sebenarnya ini lebih merupakan masalah label nama daripada masalah computability
  • Paradoks Sleeping Beauty atau Red Envelope tampaknya tidak terlalu terkait dengan ini. Paradoks-paradoks semacam itu hanya menunjukkan bahwa menerapkan konsep probabilitas matematis murni ke realitas nyata kadang tidak sederhana
    Itu tidak mengejutkan jika mengingat fakta bahwa probabilitas bekerja saat diterapkan pada realitas sendiri sangat misterius, dan telah menjadi objek banyak penyelidikan ilmiah dan filosofis
    Solusi bergaya “would f be” yang diusulkan juga tampaknya tidak banyak menyelesaikan. Tujuan pertanyaan “Tuhan” adalah membuat pembaca keluar dari masalah P-NP tertentu dan memahami bahwa untuk fungsi konstan, konsep computability tidak berguna. Agar usulan ini membantu, ia harus bisa diterapkan juga pada pertanyaan P-NP asli, tetapi saya belum melihat bagaimana pendekatan modal masuk ke dalam pertanyaan matematika yang terdefinisi dengan baik
  • Sepertinya jika kalimat ini ditulis sedikit lebih panjang, kesalahan parsing akan berkurang
    “Jika Tuhan ada, tetapkan f:{0,1}→{0,1} sebagai fungsi konstan 1; jika Tuhan tidak ada, tetapkan f:{0,1}→{0,1} sebagai fungsi konstan 0”
  • Apa pun predikat yang dimasukkan di tempat “Tuhan”, implikasinya secara ketat benar dalam logika orde pertama klasik, dan mungkin juga benar dalam banyak sistem logika lain. Analogi pragma itu tepat
    Apakah predikat semacam itu sesuai dengan konsep Tuhan seseorang adalah masalah nonmatematis yang terpisah
    Ini mirip dengan orang-orang yang terkejut ketika mempelajari bahwa dalam logika klasik, proposisi yang salah mengimplikasikan segala sesuatu. Dalam matematika ada aturan formal yang ketat, dan penting untuk melepaskan prasangka tentang makna sehari-hari kata-kata seperti “mengimplikasikan” atau “jika”
  • Versi yang bergantung pada waktu jauh lebih menarik
    Misalnya G:t∈ℝ⁺->{0,1} didefinisikan bernilai 1 jika Tuhan ada pada waktu t, dan 0 jika tidak
    Tentu saja menganalisis G dalam kerangka acuan non-inersia akan menjadi lebih menarik

• Sipser memanfaatkan fakta bahwa kebanyakan orang tidak begitu memahami perbedaan antara komputasi dan penyelidikan empiris
  “Apakah Tuhan ada” mungkin merupakan pertanyaan yang tidak dapat dijawab, tetapi itu bukan intinya. Mencari jawabannya sejak awal bukan ranah komputasi. Komputasi hanyalah prosedur yang memetakan input ke output, dan dalam kasus ini ada-tidaknya Tuhan adalah salah satu input
  Yang membuat bingung adalah karena kita tidak bisa benar-benar mengetahui nilai inputnya, tetapi programnya tetap ada dan merupakan program sepele. Ini juga bisa diganti dengan pertanyaan empiris biner lain
  Misalnya, anggap f:{0,1}* -> {0,1} adalah “1 jika di Paris ada setidaknya satu toilet portabel, 0 jika tidak.” Ini dapat dihitung dan juga dapat benar-benar dijalankan dengan input yang benar. Fungsi tentang Tuhan juga dapat dihitung, hanya saja hanya bisa dijalankan dengan input yang ditebak. Meski tidak ada jaminan bahwa outputnya berkorespondensi secara bermakna dengan alam semesta tempat kita hidup, ia tetap fungsi yang dapat dihitung
  Bahkan bisa lebih sederhana dengan hanya memikirkan f:{0,1}* -> {0,1}. “Tuhan ada” dan “Tuhan tidak ada” masing-masing adalah bit string yang mungkin. Jika pertanyaannya apakah bisa ada program yang menerima salah satu dari keduanya sebagai input lalu mengeluarkan 0, dan untuk yang lain mengeluarkan 1, tentu saja bisa. Apakah input itu benar secara empiris atau tidak tidak relevan

  • Sebenarnya fungsi-fungsi dalam pertanyaan sama sekali tidak menggunakan input. Lebih baik didefinisikan saja sebagai fungsi dari himpunan kosong ke {0, 1}
    f dalam pertanyaan bukan fungsi, melainkan label nama. Jika Tuhan ada, referen f adalah f1 yang selalu mengeluarkan 1; jika Tuhan tidak ada, referennya adalah f0 yang selalu mengeluarkan 0. Jadi sebenarnya ini bukan masalah computability, melainkan masalah label nama

• Hal seperti ini terus terjadi karena matematikawan dan ilmuwan komputer menggunakan ungkapan singkat yang menghilangkan detail demi kemudahan percakapan
  Ini tidak berbeda dengan mengatakan “mengalikan kedua sisi dengan dx.” Pertanyaan “apakah masalah wiraniaga keliling NP-hard?” merujuk pada keluarga masalah, bukan satu instance tertentu. Kalau kita menetapkan satu graf tertentu, tentu saja itu tidak NP-hard karena tidak ada N
  Kalau sudah tahu hal ini, rasanya terlalu jelas sampai tidak layak disebut, tetapi bagi orang yang tidak tahu arti istilahnya, ini benar-benar sulit dijangkau
  Dulu aku juga pernah punya salah paham dengan bentuk serupa di bidang lain. Aku memandang DNA seperti kode, dan percaya bahwa hal-hal yang bertukar pesan melalui substrat secara langsung atau dengan memodifikasi DNA sedang menjalankan kode itu. Secara keseluruhan itu bukan model yang sepenuhnya tidak berguna, tetapi aku perlu tahu kapan tidak boleh kecanduan model tersebut
  Bagi biolog yang punya latar matematika, memandang DNA apa adanya sebagai model eksekusi mesin Turing jelas salah, tetapi bagiku tidak begitu. Pada akhirnya ini masalah yang muncul dari keasingan terhadap pengetahuan dasar

• Decidability, computability, existence, bahkan kata seperti buah pun punya makna berbeda dalam konteks akademis dan konteks sehari-hari. Kalau intuisi dari makna sehari-hari dibawa ke konteks akademis, muncullah “pertanyaan bodoh” semacam ini
  Sebuah bilangan besar yang ada di Wikipedia “ada” dan “dapat dihitung” dalam makna akademis, tetapi jumlah digitnya tidak bisa muat di alam semesta kita

• Kalau tidak dibaca dengan hati-hati, redaksinya bisa membingungkan
  Dalam “Jika Tuhan ada, tetapkan f:{0,1}*→{0,1} sebagai fungsi konstan 1; jika Tuhan tidak ada, tetapkan sebagai fungsi konstan 0. Apakah f dapat dihitung?”, alternatifnya bukan bagian dari fungsi
  Fungsi f tidak bercabang berdasarkan nilai dari “Tuhan ada”; percabangannya ada di dalam metabahasa. Kita tidak tahu apakah f=0 atau f=1, tetapi karena kedua fungsi yang mungkin itu sama-sama computable, f juga computable
  Lebih jauh lagi, sekalipun f benar-benar memuat percabangan itu, dan domain f adalah 0 (Tuhan tidak ada) dan 1 (Tuhan ada), itu tetap merupakan fungsi yang dapat dihitung dalam arti hasilnya dapat dihitung untuk setiap nilai dalam domain
  Inti kebingungannya adalah mendorong variabel bebas yang nilainya dianggap tidak diketahui ke dalam f sebagai kondisi percabangan

• Aku dengan senang hati akan mengajukan keberatan terhadap contoh “Jika Tuhan ada, misalkan n=3; jika Tuhan tidak ada, misalkan n=5. Apakah n bilangan prima?”
  Di sini digunakan hukum excluded middle untuk menyatakan bahwa n adalah 3 atau 5, tetapi tidak ada pembenaran bahwa hukum excluded middle berlaku untuk proposisi “Tuhan ada”

  • Dalam logika klasik, hukum excluded middle valid
    Dalam kasus ini, jika mau mempermasalahkan apakah hukum excluded middle dibenarkan, perlu juga dibenarkan mengapa hanya hukum excluded middle yang dipersoalkan. Mengapa tidak sekalian membuang prinsip ledakan dan bekerja dalam paraconsistent logic? Kolmogorov juga melihat ada masalah serius pada aksioma ini, dan pada awalnya menganggapnya tidak kompatibel dengan logika konstruktivis
    Selain itu, bergantung pada formalisasi persis proposisi ini, hukum excluded middle belum tentu diperlukan
  • Sebagai catatan, versi buku teks mengatakan untuk mengasumsikan pertanyaannya sebagai masalah biner yang jelas (Sipser edisi ke-2, hlm. 162). Cukup tajam bisa menangkap itu
  • “Apakah n bilangan prima” juga bergantung pada kehendak Tuhan jika Tuhan ada
    Tuhan belum tentu terikat pada hukum fisika atau keniscayaan logis dasar. Konsep Tuhan seperti itu berasal dari rangkaian penalaran teologis tertentu, bukan kasus umum
    Jika mau, Tuhan juga bisa membuat 6 menjadi ganjil. Ia bisa mengubah seluruh matematika, konsistensi logis, dan seluruh alam semesta, atau menciptakan dunia tempat hanya 77 yang genap dan semua bilangan lain ganjil, lalu membuat semua matematikawan menganggap susunan itu sepenuhnya konsisten dan selalu benar
    Jadi jawabannya bisa dibilang sampai taraf tertentu bergantung pada keyakinan agama

• Ilmu komputer teoretis dan teori kompleksitas tampaknya menempati posisi bagi mahasiswa S1 CS atau orang di industri yang berdekatan, mirip dengan posisi fisika partikel bagi orang awam
  Seperti orang awam pernah mendengar kata entanglement, kita pernah mendengar kata NP-hard, lalu alih-alih mengikuti pengembangan matematisnya sendiri, kita menggantinya dengan analogi populer yang buruk dan khayalan

  • Meski begitu, tidak ada alasan untuk menganggap semua orang harus memakai kata “computable” hanya dengan definisi yang sangat ketat. Definisi sehari-hari, yaitu “bisa dilakukan komputer”, juga masuk akal
    Penulis mungkin, karena pelatihan panjang, telah memilih definisi computability miliknya sendiri yang sangat ketat, lalu menulis seluruh artikel tentang definisi tertentu dari kata itu, kemudian menuduh orang-orang di dunia yang memakai kata yang sama dengan definisi lain sebagai orang yang mengajukan pertanyaan bodoh
    Saat berbicara dengan akademisi di tempat kerja atau dengan orang awam, hal seperti ini benar-benar sering terjadi. Menetapkan istilah bersama itu sulit, dan cara menarik garis berdasarkan istilah versi sendiri lalu menyuruh orang lain mengikutinya terasa melelahkan