noncomputable
/ˌnɒnkəmˈpjuːtəbl/
🇬🇧Bahasa InggrisMatematikaIlmu KomputerLogikaNetral
Ringkasan Makna
Sifat suatu masalah atau fungsi yang tidak dapat diselesaikan atau dihitung oleh algoritma apa pun dalam waktu terbatas.
Penjelasan & Konteks Penggunaan
Dalam teori komputabilitas, istilah noncomputable merujuk pada masalah keputusan atau fungsi matematika yang tidak memiliki algoritma yang dapat menghasilkan jawaban yang benar untuk setiap input dalam jumlah langkah yang terbatas. Masalah ini sering dikaitkan dengan 'masalah penghentian' (halting problem) yang dibuktikan oleh Alan Turing sebagai sesuatu yang tidak dapat dipecahkan oleh mesin Turing.
Contoh Penggunaan dalam Kalimat
“The halting problem is a classic example of a noncomputable function.”
→Masalah penghentian adalah contoh klasik dari fungsi yang tidak dapat dihitung.
“There are many noncomputable sets in formal logic.”
→Terdapat banyak himpunan yang tidak dapat dihitung dalam logika formal.
Asal-usul & Konteks Budaya
Istilah ini berasal dari pengembangan teori komputasi pada tahun 1930-an oleh matematikawan seperti Alan Turing dan Alonzo Church untuk mendefinisikan batasan fundamental dari apa yang bisa dilakukan oleh mesin komputasi.