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.

Sistem deduktif dan masalah penentuan

Ketika kamu mempelajari sistem deduktif, kamu berhadapan dengan berbagai pertanyaan yang termasuk dalam kategori penentuan:

1. Apakah m(A,B)?
2. Apakah m(B,C) salah?
3. Apakah m(B,B) adalah teorema?

Karena pertanyaan-pertanyaan tersebut memiliki batasan jawaban ya atau tidak, maka pertanyaan tentang teorema sistem deduktif merupakan masalah penentuan.

Ketika pertanyaan tersebut dapat dijawab dan dibuktikan, pertanyaan tersebut disebut sebagai decidable. Jika dalam sistem yang diberikan hal tersebut tak dapat ditunjukkan dengan langkah-langkah pembuktian, pertanyaan tersebut adalah undecidable.

Contoh-contoh lainnya

Mencari huruf dalam kata

Di atas ada sebuah pertanyaan, Apakah huruf k terkandung dalam kata 'streptococcus'? Program Python untuk menjawab persoalan tersebut adalah seperti di bawah ini.

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

Permasalahan Collatz adalah salah satu permasalahan matematika yang hingga tulisan ini dibuat belum dapat dipecahkan.

Permasalahannya seperti ini:

Input adalah bilangan asli n.

1. Jika n genap, bagi n dengan 2.
2. Jika n ganjil, hitung 3n + 1.
3. Ulangi terus dengan n = bilangan baru hasil perhitungan.

Pertanyaannya: Jika proses ini diulang terus, apakah bilangan yang dihasilkan adalah 1?

x = n

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

Cobalah berbagai macam input, kamu akan mendapatkan jawaban Ya. Namun apakah ada bilangan yang ketika kamu masukkan sebagai input, jawabannya akan Tidak? Hingga hari ini pertanyaan ini belum terjawab.

Berikutnya: Permasalahan dan program