Kesalahpahaman Zombi dalam Ilmu Komputer Teoretis

Kesalahpahaman Zombi dalam Ilmu Komputer Teoretis

Pendahuluan

• Dalam buku teks Michael Sipser, "Introduction to the Theory of Computation", ada soal yang sempurna
• Soal: "Ketika fungsi f:{0,1}*→{0,1} mengembalikan 1 atau 0 tergantung pada ada atau tidaknya Tuhan, apakah f dapat dihitung?"
• Jawaban: "Ya, f dapat dihitung" (karena fungsi konstan dapat dihitung)

Konsep keterhitungan

• Keterhitungan berlaku pada fungsi atau barisan tak hingga
• Tidak berlaku pada pertanyaan ya/tidak individual atau bilangan bulat individual
• Tingkat kesulitan menulis program tidak berkaitan dengan keterhitungan

Masalah P versus NP

• Masalah P versus NP adalah pertanyaan ya/tidak individual
• NP-hardness berlaku pada fungsi atau bahasa
• Masalah P versus NP tidak bisa tak dapat dihitung ataupun NP-hard

Fungsi Busy Beaver

• Fungsi Busy Beaver tidak dapat dihitung
• Bilangan bulat individual seperti BB(6) dapat dihitung
• Seluruh fungsi BB tidak dapat dihitung

Kesalahpahaman zombi dalam ilmu komputer teoretis

• Salah menerapkan konsep yang berlaku pada barisan tak hingga dan fungsi ke bilangan bulat individual dan masalah terbuka
• Mencampuradukkan ketakterhitungan masalah halting dengan ketaklengkapan Gödel

Pertanyaan untuk pembaca

• Penulis bertanya kepada pembaca bagaimana mencegah kesalahpahaman zombi ini

Ringkasan GN⁺

• Artikel ini membahas kesalahpahaman yang sering muncul dalam ilmu komputer teoretis
• Keterhitungan berlaku pada fungsi atau barisan tak hingga, dan tidak berlaku pada bilangan bulat individual atau pertanyaan ya/tidak
• Masalah P versus NP adalah pertanyaan individual, sehingga tidak berkaitan dengan konsep NP-hardness
• Fungsi Busy Beaver tidak dapat dihitung, tetapi nilai individualnya dapat dihitung
• Artikel ini akan membantu memahami dengan jelas konsep dasar dalam ilmu komputer teoretis

[GN⁺]

Komentar Hacker News

• Ada/tidaknya algoritme untuk menghitung kompleksitas Kolmogorov berkaitan dengan ketakhinggaan

  • Tidak ada algoritme untuk menghitung kompleksitas Kolmogorov string dengan panjang sembarang
  • Namun, ada algoritme untuk menghitung kompleksitas Kolmogorov string yang panjangnya kurang dari n
  • Ini dimungkinkan dengan membuat tabel pencarian raksasa untuk semua string yang mungkin
  • Masalah hingga selalu bisa diselesaikan dengan program, tetapi masalah tak hingga tidak demikian

• Pendapat bahwa matematika konstruktif lebih sesuai dengan intuisi orang

  • Belum ada bukti bahwa ada program untuk persoalan P=NP
  • Mark Braverman membuktikan bahwa semua himpunan Julia (kuadratik) dapat dihitung, tetapi tidak dapat dihitung secara seragam
  • Dalam matematika konstruktif, bidang kompleks dibagi ke beberapa wilayah lalu dibuktikan bahwa himpunan Julia di setiap wilayah bersifat kompak

• Alasan sulit memahami ketakdapatdiputuskan dari masalah berhenti

  • Salah satu dari program return true dan return false selalu memberikan jawaban yang benar
  • Kemungkinan untuk diputuskan baru menjadi tak dapat diputuskan saat diperluas ke kombinasi mesin/masukan yang tak hingga

• Ekspresi masalah yang memerlukan logika modal

  • Pertanyaan "apakah f dapat dihitung?" adalah pertanyaan yang salah secara modal
  • Pertanyaan "mungkinkah f dapat dihitung?" lebih akurat
  • Ini mirip dengan direktif compiler atau pragma

• Representasi fungsi f yang membingungkan

  • Fungsi f tidak bercabang berdasarkan nilai "God exists"
  • Baik f bernilai 0 maupun 1, keduanya dapat dihitung
  • Kebingungan muncul ketika variabel bebas didorong masuk ke kondisi percabangan

• Perbedaan makna keterputusan, keterhitungan, dan keberadaan

  • Maknanya berbeda antara konteks akademik dan konteks sehari-hari
  • Bilangan besar ada dan dapat dihitung secara akademik, tetapi dalam praktiknya tidak muat di alam semesta

• Masalah pada pertanyaan yang berkaitan dengan "God exists"

  • Tidak jelas apakah "God exists" bernilai benar atau salah
  • Ini adalah masalah yang muncul saat bahasa alami dan matematika dicampur

• Alasan ilmu komputer teoretis dan teori kompleksitas sulit bagi mahasiswa S1 CS

  • Istilah seperti NP-hard digantikan oleh analogi dan imajinasi yang lebih populer

• Keluhan tentang cara blog menyorot teks

  • Warna latar teks yang dipilih tidak berubah sehingga tidak intuitif

• Usulan untuk mengganti "God exists" dengan proposisi matematika lain

  • "God exists" harus didefinisikan dengan jelas sebagai benar atau salah