decidable
/dɪˈsaɪdəbəl/
🇬🇧Bahasa InggrisMatematikaIlmu KomputerLogikaNetral
Ringkasan Makna
Dapat diputuskan; sifat suatu masalah yang dapat diselesaikan oleh mesin turing atau algoritma dalam waktu berhingga.
Penjelasan & Konteks Penggunaan
Dalam teori komputabilitas dan ilmu komputer teoretis, sebuah masalah disebut 'decidable' (dapat diputuskan) jika terdapat algoritma (atau mesin Turing) yang dapat memberikan jawaban ya atau tidak untuk setiap masukan yang valid dalam waktu berhingga dan berhenti (tidak mengalami perulangan tak terbatas).
Contoh Penggunaan dalam Kalimat
“The problem of determining whether a number is prime is decidable.”
→Masalah untuk menentukan apakah suatu angka adalah bilangan prima dapat diputuskan.
“Every context-free language is decidable.”
→Setiap bahasa bebas konteks adalah dapat diputuskan.
Asal-usul & Konteks Budaya
Berasal dari bahasa Inggris 'decide' dengan akhiran '-able', istilah ini dipopulerkan dalam logika matematika dan ilmu komputer oleh para pionir seperti Alan Turing melalui studi tentang masalah keputusan (Entscheidungsproblem).