Masalah Penentuan

Mengapa program bisa disebut sebagai decidable, undecidable, maupun semi-decidable? Apakah ada hubungannya dengan decision (penentuan)?

Benar sekali. Ketiga istilah tersebut sebetulnya merupakan istilah khusus dalam kategori permasalahan yang disebut sebagai masalah penentuan atau decision problem.

Masalah penentuan

Ada kategori permasalahan yang disebut sebagai masalah penentuan (decision problem). Masalah penentuan pada dasarnya adalah persoalan atau pertanyaan yang jawabannya hanya ya atau tidak. Misalnya pertanyaan-pertanyaan berikut ini:

1. Apakah 18 bilangan prima?
2. Apakah kata streptococcus mengandung huruf k?
3. Apakah di kelas 10-6 ada siswa bernama Bleki?

Pertanyaan-pertanyaan tersebut dapat dimodelkan sebagai program. Sebagai contoh, sebelumnya kamu telah melihat ada program primakah(), yang adalah program untuk menentukan apakah suatu bilangan adalah bilangan prima. Di bawah ini program primakah() ditulis ulang sebagai program P(), yang menjawab Ya dan Tidak. Jika benar prima P akan menghasilkan output Ya, dan jika tidak akan menghasilkan output Tidak.

jumlahFaktor = 0;
i = 1

while (i <= n and jumlahFaktor <= 2):
  if (n % i == 0):
    jumlahFaktor = jumlahFaktor + 1
  i = i + 1

if (jumlahFaktor == 2):
  return "Ya"
else:
  return "Tidak"

Beberapa contoh hasil yang dapat kamu peroleh:

Algoritma di atas akan memeriksa setiap bilangan asli dari 1 hingga input n yang diberikan. Jadi kita bisa yakin program ini pasti akan berhenti berapapun n-nya, asal masih berhingga.

Karena berhenti, maka program ini akan selalu dapat memberikan jawaban Ya maupun Tidak kepada kita. Dengan demikian, program akan selalu dapat menentukan (decide) jawabannya, sehingga disebut sebagai decidable.

Mencari huruf dalam kata

for huruf in kata:
  if huruf == hurufDicari:
    return "Ya"
    
return "Tidak"

Program ini juga akan selalu berhenti asalkan jumlah huruf dalam kata yang diberikan adalah berhingga. Dengan demikian program ini decidable.

Adakah sisi miring n?

Program di bawah ini akan berusaha menentukan apakah n dapat menjadi panjang sisi miring dalam segitiga siku-siku yang kedua sisi lainnya merupakan bilangan asli.

Dengan kata lain, ada bilangan asli a, b, dan n yang merupakan tripel Pythagoras.

k = 0
while(True):
  k += 1
  for a in range(1, k+1):
    for b in range(1, k+1):
      if (a*a + b*b == n*n):
        return "Ya"
        
return "Tidak"

Program ini tidak efektif, karena jika tidak berhasil menemukan bilangan a dan b yang mungkin, program akan terus mencari dan tak pernah berhenti. Jadi, ketika jawabannya Ya, program akan berhenti, tetapi jika jawaban yang seharusnya adalah Tidak, program tidak akan berhenti.

Karena program hanya dapat menentukan (decide) sebagian kemungkinan jawaban, program ini disebut sebagai semi-decidable.

Permasalahan Collatz

x = n

while True:
  if (x % 2 == 0):
    x = x / 2
  else:
    x = 3 * x + 1
  
  if (x == 1):
    return "Ya"
        
return "Tidak"

Berikutnya: Halting Problem