oleh, Ernastuti pada Proceedings, Komputer dan Sistem Intelegen (KOMMIT 2004)
LATAR BELAKANG
Dalam menyelesaikan suatau masalah diperlukan sederetan langkah-langkah tertentu. Langkah-langkah tersebut dapat dipandang sebagai suatu barisan. Pada makalah ini dibahas tentang metode penomoran godel yang memperlihatkan bagaimana suatu barisan dapat dikaitkan dengan hanya satu bilangan bulat positif yang unik.
PERUMUSAN MASALAH
Apakah metode penomoran Godel sangat tepat untuk encode-encode suatu program dengan mengaitkan bilangan bulat posotif ini (bilangan Godel) ke sebuah program bahasa GOTO.
Bagaimana suatu fungsi yang dihitung oleh suatu program dapat dinyatakan berdasarkan bilangan godel dari program tersebut.
METODOLOGI
Dalam tulisan ini akan menjelaskan tentang bagaimana pentingnya perkalian bilangan-bilangan prima untuk mengaitkan barisan hingga bilangan bulat positif dengan satu bilangan bulat positif. Bilangan prima pada metoda penomoran godel dapat dipandang sebagai faktor-faktor prima dari suatu bilangan bulat positif.
INTI PEMBAHASAN
Terdapat sembilan teorema yang akan digunakan untuk memperkuat metode penomoran godel dengan menggunkan bahasa pemrograman GOTO.
Teorema-teorema tersebut adalah :
1. Setiap bilangan bulat n > 1 adalah suatu bilangan prima atau suatu perkalian bilangan-bilangan prima.
2. Untuk sebarang pasangan bilangan bulat positif a dan b, pembagi umum terbesar d = (a,b) selalu ada dan unik.
3. Untuk pembagi umum terbesar d = (a,b), himpunan bilangan bulat x dan y himpunan d = ax + by.
4. Untuk setiap bilangan bulat positif a, b dan c. jika a|bc dan (a,b) = 1, maka a|c.
5. Jika bilangan prima p membagi ab, maka p membagi paling sedikit satu dari a atau b.
6. Jika bilangan prima p membagi suatu perkalian a1,a2……an, maka p membagi paling sedikit satu dari faktor-faktor tersebut.
7. Sembarang bilangan bulat positif n > 1 dapat dinyatakan secara unik sebagai n = U1^a1, U2^a2…Uk^ak. Dengan k = bilangan ulat positif, setiap U1 adalah bilangan prima, setiap a1 adalah bilangan bulat positif, dan 1 < U1 < U2 < …. < Uk.
8. Tidak ada 2 barisan hingga bilangan bulat positif yang berbeda mempunyai bilangan godel yang sama.
9. Suatu bilangan bulat g > 1 adalah bilangan godel dari barisan hingga bilangan bulat positif a1, a2, …… an. Jika dan hanya jika ᵾm, m < n dan Pn adalah faktor dari g, maka Pm adalah juga faktor dari g.
Bahasa pemrograman GOTO adalah suatu bahasa yang digunakan untuk membuat program didalam komputer. Bahasa GOTO ini bekerja atas dasar bilangan-bilangan bulat non negatif dengan operasi yang sederhana. Operasi-operasi aritmatik yang dapat dilakukannya adalah hanya penambahan dan pengurangan.
Contoh sintaks dari bahasa GOTO, bahasa GOTO mempunyai 2 command aritmatik yaitu : menambah dengan 1 (satu) dan mengurang dengan 1 (satu). Karena bahasa goto bekerja atas dasar bilangan bulat non negatif, maka hasil pengurangan pada 0 ditentukan/didefinisikan sama dengan 0.
Tiga control command yang ada dalam bahasa GOTO adalah : unconditional transfer (GOTO…), conditional transfer ( IF V=0 GOTO ….) dan HALT.
Karakter-karakter yang ada dalam bahasa GOTO ialah :
1. Decimal digit : 0,1,2,3,4,5,6,7,8,9;
2. Huruf besar : A,B,C ……. X,Y,Z;
3. Tanda khusus : ;’:,=,(,)
Terdapat pula Bilangan godel dari string, cara menentukannya adalah : pertama, setiap karakter didalam suatu alfabet masing-masing dikaitkan didalam satu bilangan bulat positif yang berbeda, dengan demikian setiap string dari alfabet tersebut dapat dipandang sebagai barisan hingga dari bilangan bulat positif. Sehingga bilangan godel dari string diperoleh dengan cara seperti pengaitan bilangan godel dengan barisan hingga bilangan bulat positif.
Penggunaan bahasa pemrograman GOTO dalam pengkodean untuk metode bilangan godel sangat membantu untuk memecahkan masalah seperti setiap barisan hingga bilangan bulat positif dapat dikaitkan dengan satu bilangan bulat positif, dengan demikian metode penomoran godel adalah sebuah fungsi dari himpunan barisan hingga bilangan bulat positif (domain) ke himpunan bilangan bulat positif (codomain). Setiap bilangan bulat positif yang merupakan hasil pemetaan dari suatu barisan didalam domain inilah yang disebut Bilangan Godel.
KESIMPULAN
Bilangan godel akan bertambah besar jika barisannya semakin panjang, sekalipun suku dalam barisannya merupakan bilangan; Bilangan godel mengaitkan barisannya secara unik dan bilangan godel adalah bilangan bulat positif > 1; Tidak semua bilangan positif bilangan godel karena tidak ada 2 barisan berbeda mempunyaibilangan godel yang sama dan terdapat sejumlah bilangan bulat positif yang bukan bilangan godel, maka metode penomoran godel adalah fungsi satu-satu. Dari kesimpulan tentang bilangan godel ini , maka metode penomoran godel sangat tepat untuk masalah encode dan decode.
DAFTAR PUSTAKA
1. B.M Stewart, “Theory of numbers”. The Macmillan company, New York, 1964.
2. Ernastuti, “Godel Numbering pada string, graf, dan program”, skripsi, FMIPA-UI, 1985
3. F.Hennie, “Introduction to computability”, Addison-Wesley publishing Company, New York, 1978
4. M.A. Aiserman and L.A. Gusev, “Logic, automata and algorithma”. Academic press, New York, 1971
5. N.Curtland, “Computability : An introduction to recursive function theory”, Cambridge University press, 1990
6. R.McNaughton, “Elementary computability formal language and automata” Prantice-hall, New Jersey, 1982
7. T.M.Apostol, “Mathematical Analisys”, Addison-Weslley publihing Company, New York. 1978.
