Sistem formal dan teka-teki MU

Sistem formal (formal system) adalah sistem yang dibangun dari bahasa formal (formal language). Bahasa formal terdiri dari alfabet, yaitu sekedar simbol tanpa memiliki arti tertentu. Dari alfabet tersebut kita dapat membuat string (runtutan alfabet). Misalnya, kita memiliki sebuah kumpulan (set) S = {%, &, #}. Contoh string adalah (tanpa tanda petik) “%#”, “%&”, “%%%”, “%%&#”, dan seterusnya.

Sistem formal dibangun dengan  cara menambahkan aturan untuk membentuk string di dalam suatu bahasa formal. Jadi, tidak sembarang string dapat dibangun dari alfabet. Dilihat dari sudut pandang tertentu, sistem formal seperti sebuah permainan dengan aturan-aturan yang harus ditaati. Semua kemungkinan yang muncul dalam permainan tersebut, adalah hasil dari penerapan aturan-aturan yang berlaku (tentu saja dalam sistem formal, kemungkinan-kemungkinan ini juga merupakan string).

Dalam buku yang ditulis oleh Douglas Houfstadter, yang berjudul Godel, Escher, Bach, terdapat satu teka-teki yang berkaitan dengan sistem formal ini. Teka-teki tersebut diberi nama teka-teki MU (MU-Puzzle). Teka-teki tersebut digambarkan sebagai berikut.

Terdapat satu bahasa formal yang terdiri atas tiga alfabet, yaitu M, I, dan U.

Dalam bahasa formal ini, dibuat sebuah sistem formal dengan aturan-aturan sebagai berikut.

Peraturan 1: Jika sebuah string berakhiran I, maka dapat ditambahkan U di akhir string tersebut. Contoh UI menjadi UIU.

Peraturan 2: Jika sebuah string memiliki bentuk Mx, dengan x adalah variabel yang juga berupa string, maka di akhir string dapat ditambahkan juga x. Misal, string MUI dapat kita ubah menjadi MUIUI. Contoh lain, string MIIU dapat kita ubah menjadi MIIUIIU.

Peraturan 3: Jika dalam satu string muncul III, maka dapat digantikan dengan U. Contoh MIII menjadi MU. IIIUI menjadi UUI.

Peraturan 4: Jika dalam satu string muncul UU, maka UU tersebut dapat dihilangkan. Misalkan, MUUU menjadi MU.

Teka-tekinya adalah sebagai berikut. Dimulai dari string MI, coba bentuk string MU dengan menerapkan aturan-aturan yang berlaku (yaitu aturan-aturan 1-4). Ada yang bisa? 🙂

Leave a Reply