The Busy Beaver Problem

 The Busy Beaver Problem

Nama Kelompok:

Nicholas 5025231031

Thopaz Givangkara Rosadi 5025231050

Alif Nurrohman 5025231057

Moch. Septian Ezra Maulana 5025231120

Dosen Pengampu:

Ilham Gurat Adillion, S. Kom., M. Eng

INSTITUT TEKNOLOGI SEPULUH NOPEMBER

2024/2025

BAB I 

PENDAHULUAN

1.1 Latar Belakang

Komputasi modern memiliki akar yang dalam pada model matematika ideal yang disebut Turing machine, yang diperkenalkan oleh Alan Turing pada tahun 1936. Mesin ini tidak hanya merevolusi pemahaman kita terhadap algoritma dan komputasi, tetapi juga membawa kita ke dalam diskusi tentang apa yang dapat dan tidak dapat dilakukan oleh mesin secara fundamental.

Dari model ini, berbagai persoalan muncul, salah satunya adalah Busy Beaver Problem. Diperkenalkan oleh Tibor Radó pada tahun 1962, masalah ini mengeksplorasi batas tertinggi dari "produktivitas" sebuah mesin Turing sebelum berhenti. Meskipun terdengar sederhana, Busy Beaver Problem menjadi sangat kompleks dan memicu berbagai kajian mendalam dalam teori komputasi, terutama mengenai fungsi yang tidak dapat dihitung (non-computable functions).

1.2 Rumusan Masalah

1. Apa definisi formal dari Busy Beaver Problem?

2. Bagaimana Busy Beaver Problem menunjukkan keterbatasan mesin komputasi?

3. Apa hubungan Busy Beaver Problem dengan undecidability dan teori informasi?

4. Apakah Busy Beaver dapat diimplementasikan dalam eksperimen atau simulasi?

5. Sejauh mana peran Busy Beaver dalam pemahaman batas pengetahuan manusia?

BAB II 

PEMBAHASAN

2.1 Pembahasan

1. Mesin Turing

Mesin Turing adalah model abstrak dari komputer yang bekerja melalui:

• Pita tak terbatas (tape) yang terdiri dari sel-sel,

• Kepala baca/tulis (head) yang bergerak satu sel ke kiri atau kanan,

• State register yang menyimpan keadaan saat ini,

• Tabel transisi (transition function) yang menentukan tindakan berdasarkan simbol yang dibaca dan state saat ini.

Sebuah mesin Turing dapat menulis simbol, berpindah ke kiri atau kanan, dan mengubah state. Ia akan terus berjalan hingga mencapai kondisi berhenti (halting state).

2. Busy Beaver Function

Busy Beaver Function, Σ(n) (dibaca: Sigma n), adalah jumlah maksimum simbol 1 yang dapat ditulis oleh mesin Turing dengan n state sebelum berhenti, ketika dimulai dari pita kosong. Fungsi lain yang berkaitan adalah S(n), yaitu jumlah maksimum langkah yang dilakukan mesin n-state sebelum berhenti.

3. Formalisasi Masalah

Untuk setiap n, kita mencari mesin Turing deterministik dengan:

• Alfabet {0,1},

• Pita kosong (semua 0),

• n internal state (tidak termasuk state berhenti),

• Mesin berhenti (halts),

yang memaksimalkan jumlah simbol 1 yang tertulis (untuk Σ(n)) atau jumlah langkah yang dilakukan (untuk S(n)).

2.2 Contoh Nilai Busy Beaver

n	Σ(n)	S(n)	Catatan
1	1	1	Mesin dengan 1 state, trivial
2	4	6	Sudah terbukti secara lengkap
3	6	21	Diperoleh dari pencarian menyeluruh
4	13	107	Brady (1983), eksplorasi ekstensif
5	≥ 4098	≥ 47.176.870	Belum diketahui pasti, hasil simulasi
6	Tidak diketahui	Tidak diketahui	Eksponensial dan sangat sulit dihitung

2.3  Kompleksitas dan Non-komputabilitas

Fungsi Σ(n) tumbuh lebih cepat dari fungsi apapun yang dapat dihitung oleh algoritma. Artinya, tidak ada program yang dapat menerima n sebagai input dan mengembalikan nilai Σ(n) untuk semua n.

Ini membuktikan bahwa Busy Beaver Function adalah contoh fungsi total yang tidak dapat dihitung (non-computable function). Hal ini secara langsung berkaitan dengan masalah halting: jika kita bisa menghitung Σ(n), kita bisa menyelesaikan halting problem, yang telah terbukti mustahil oleh Turing.

2.4  Aplikasi Teoretis

Busy Beaver digunakan untuk:

• Menunjukkan batas dari sistem pembuktian formal seperti Zermelo–Fraenkel Set Theory (ZF) dan Peano Arithmetic (PA).

• Menganalisis kompleksitas algoritma dengan produktivitas maksimum.

• Mengeksplorasi pertanyaan seputar algorithmic information theory dan Kolmogorov complexity.
  
  

2.5  Contoh Soal

Berikut contoh implementasi Turing machine 2-state untuk mencari Busy Beaver:

1. Busy Beaver dengan 1 State

Tentukan mesin Turing 1-state yang menulis jumlah maksimum simbol 1 di pita kosong dan berhenti.

Transisi:

State: A, Halting state: HALT

Alfabet: {0, 1}

Transisi:

(A, 0) → (1, R, HALT)

 Hasil:

Langkah: 1

Jumlah 1 yang ditulis: 1

2. Busy Beaver dengan 2 State

Tentukan mesin Turing 2-state (A, B) yang menulis jumlah 1 maksimum di pita kosong dan berhenti.

Transisi:

(A, 0) → (1, R, B)

(A, 1) → (1, L, B)

(B, 0) → (1, L, A)

(B, 1) → (1, R, HALT)

Hasil:

Langkah: 6

Jumlah 1 yang ditulis: 4

3. Busy Beaver dengan 3 State

Cari mesin Turing 3-state (A, B, C) yang menulis 1 paling banyak di pita kosong dan berhenti.

Transisi:

(A, 0) → (1, R, B)

(A, 1) → (1, L, C)

(B, 0) → (1, R, C)

(B, 1) → (1, R, B)

(C, 0) → (1, L, A)

(C, 1) → (0, L, HALT)

Hasil:

Langkah: 21

Jumlah 1 yang ditulis: 6

2.6 Implementasi 

01: class TuringMachine:

02:     def __init__(self, transitions, initial_state='A'):

03:         self.transitions = transitions

04:         self.state = initial_state

05:         self.tape = {}

06:         self.head = 0

07:         self.steps = 0

08:

09:     def read(self):

10:         return self.tape.get(self.head, 0)

11:

12:     def write(self, value):

13:         self.tape[self.head] = value

14:

15:     def move(self, direction):

16:         self.head += 1 if direction == 'R' else -1

17:

18:     def step(self):

19:         symbol = self.read()

20:         key = (self.state, symbol)

21:         if key in self.transitions:

22:             write_val, move_dir, next_state = self.transitions[key]

23:             self.write(write_val)

24:             self.move(move_dir)

25:             self.state = next_state

26:             self.steps += 1

27:             return True

28:         return False

29:

30:     def run(self):

31:         while self.state != 'HALT':

32:             if not self.step():

33:                 break

34:

35:         ones_written = sum(1 for v in self.tape.values() if v == 1)

36:         print(f"Final State: {self.state}")

37:         print(f"Steps taken: {self.steps}")

38:         print(f"Ones written: {ones_written}")

39:         print("Final Tape:", self.tape)

40:

41: # ====================================

42: # Change this section for each case

43: # ====================================

44: # Example: 3-State Busy Beaver

45: transitions_3_state = {

46:     ('A', 0): (1, 'R', 'B'),

47:     ('A', 1): (1, 'L', 'C'),

48:     ('B', 0): (1, 'R', 'C'),

49:     ('B', 1): (1, 'R', 'B'),

50:     ('C', 0): (1, 'L', 'A'),

51:     ('C', 1): (0, 'L', 'HALT'),

52: }

53:

54: tm = TuringMachine(transitions_3_state)

55: tm.run()

56:

2.7 Eksperimen Exhaustive Search

Untuk nilai n kecil (misalnya n = 2 atau 3), kita bisa menggunakan brute-force untuk mencari semua mesin Turing dan mengevaluasi produktivitasnya. Namun jumlah kemungkinan mesin tumbuh sangat cepat: untuk n state dan m simbol, jumlah kemungkinan mesin sekitar [(2*m*(n+1))]^(m*n). Oleh karena itu, eksplorasi n ≥ 5 hanya dapat dilakukan dengan bantuan heuristik, superkomputer, dan pengecekan manual.

2.8 Relasi dengan Kolmogorov Complexity

Busy Beaver berkaitan erat dengan konsep Kolmogorov complexity (panjang program terpendek yang menghasilkan suatu output). Jika kita bisa menentukan Σ(n), kita dapat mengukur kompleksitas dari keluaran tertentu dan membedakan antara string acak dan terstruktur.

BAB III

KESIMPULAN

3.1 Kesimpulan

Busy Beaver Problem adalah salah satu permasalahan paling mencolok dalam teori komputasi karena menunjukkan secara eksplisit batas dari apa yang bisa dihitung oleh mesin. Fungsi Busy Beaver Σ(n) tumbuh lebih cepat dari fungsi manapun yang dapat dihitung secara algoritmis dan tidak dapat dihitung secara umum karena kaitannya dengan halting problem. 

Masalah ini tidak hanya menarik secara teoritis, tetapi juga menantang secara praktikal karena ia menguji batas-batas eksplorasi algoritmik dan bahkan sistem matematika formal. Walau tampak sederhana, masalah ini membawa kita pada diskusi mendalam tentang esensi komputasi, kompleksitas, dan pengetahuan.