Gödel Untuk Semua1 Ivan Mulianta2 “Either mathematics is too big for the human mind or the human mind is more than a machine.” Kurt Friedrich Gödel (1906-1976)
0. Pengantar Formalisme adalah suatu metode dalam matematika untuk membuktikan kebenaran suatu hal. Formalisme ini juga menjadi pekerjaan penting bagi setiap matematikawan. Namun, tidak semua hal dapat dibuktikan kebenarannya melalui formalisme ini. Adalah Kurt Friedrich Gödel, matematikawan Austria yang kali pertama membuktikan secara formal bahwa tidak semua hal dapat dibuktikan kebenarannya melalui formalisme. Kalau memang tidak semua hal tidak dapat dibuktikan, lalu kenapa? Apa manfaatnya? Seberapa pentingkah hal itu sehingga ada orang yang mau menulisnya. Untuk permulaan anggaplah ini sangat penting sehingga anda akan menelusuri tulisan ini, mulai dari riwayat hidup Gödel secara sekilas, cara Gödel membuktikan ketidaklengkapan dan ketidakkonsistenan dalam formalisme, dan bagaimana perkembangan bukti itu dan berbagai penerapannya. Setelah anda membaca tulisan ini, tentu anda akan menyadari betapa pentingnya ketidaklengkapan dan ketidakkonsistenan dalam kehidupan ini.
1. Riwayat Hidup Gödel Kurt Friedrich Gödel, dilahirkan di kota Brno (sekarang Brunn), daerah Austro-Hungary (sekarang Republik Ceko) pada tanggal 28 April 1906 dari pasangan Rudolf Gödel dan Marianne Handschuh. Selain Kurt, pasangan ini juga melahirkan Rudolf (1902). Kurt dan Rudolf Gödel menghabiskan masa kecil dan remajanya di Brno. Pada masa kecilnya, Kurt sudah menunjukkan kejeniusannya, misalnya pada pelajaran bahasa latin, dia selalu menulis dengan tata bahasa latin yang sempurna. Dia juga orang yang mempunyai rasa ingin tahu yang sangat besar, sampai-sampai teman-temannya memanggilnya “Tuan Mengapa” (“Herr Warum”). Kurt melanjutkan studinya ke Universitas Vienna pada tahun 1924. Pada awal kuliahnya, dia mempelajari filsafat, fisika, dan matematika, dia belum menentukan subyek yang akan diambil. Bahkan dia sebenarnya bermaksud mendalami fisika teori setelah menghadiri kuliah Hans Thirring tetapi Kurt akhirnya memilih matematika. Menurut Prof. Edmund Hlawka, hal ini dipengaruhi oleh Hans Hahn dan Karl Menger, pada saat Kurt menghadiri kuliah teori himpunan (set theory) dan fungsi real (real function). Selain itu, Kurt juga pernah menghadiri kuliah Phillip Furtwängler tentang teori bilangan (number theory) yang kemudian dia terapkan pada logika. Kelak, melalui metode teori bilangan ini
1 Makalah ini dibuat untuk menyambut 74 tahun penemuan Gödel (1931 – 2005) tentang teorema ketidaklengkapan dan ketidakkonsitenan beserta dampaknya pada perkembangan ilmu pengetahuan hingga sekarang 2 Dept. Dynamical System Modeling, Bandung Fe Institute, email:
[email protected]
2 juga, Kurt mampu membuktikan ketidaklengkapan dan ketidakkonsistenan pada formalisme matematika.3 Kurt Gödel menikah dengan Adelle Nimburg pada tahun 1927. Adelle sangat setia mendampingi Kurt, bahkan ia juga berperan sebagai pengetes makanan Kurt (Kurt percaya bahwa ada orang yang ingin meracuni makanannya). Selama perang dunia II, Austria dikuasai oleh NAZI (saat itu dipimpin oleh Adolf Hittler) yang menangkapi orang-orang Yahudi dan teman-teman dekatnya. Kurt termasuk dalam senarai hitam (black list) tersebut. Dia berhasil keluar dari Austria menuju Universitas Princeton di New Jersey, Amerika Serikat (tempat dia pernah melakukan kuliah tamu) meskipun melalui perjalanan panjang melalui trans Siberia. Kurt menghabiskan sisa hidupnya di Universitas Princeton dan menjadi profesor tetap sejak 1949. Selama masa pengabdiannya di Universitas Princeton, Kurt berkumpul bersama beberapa raksasa ilmu pengetahuan lainnya seperti: Albert Einstein, John Von Neumann di Institut Studi Lanjut (Institute of Advance Studies). Kurt juga mendapatkan beberapa penghargaan seperti National Medal Science, Einstein’s Award. Kurt meninggal dunia pada tahun 1976.
2. Ketidaklengkapan dan Ketidakkonsistenan 2.1 Ilustrasi contoh Anda tentu pernah minum jus, yaitu minuman sari buah. Jus ini tidak hanya terbuat dari satu macam buah saja tetapi juga dapat dicampur-campur. Kita tentu mengetahui bahwa jus ini tidak hanya terbuat dari sari buah saja tapi juga ada beberapa campuran lain seperti gula, air, susu, yang akan membuat rasa jus tersebut khas. Untuk menciptakan jus tersebut, kita membutuhkan proses yang mengubah dari campuran bahan-bahan seperti: sari buah, gula, air menjadi jus. Untuk lebih jelasnya, coba kita lihat gambar 1.
Gambar 1 Mesin Jus Untuk membuat jus, kita memerlukan bahan-bahan seperti sari buah, gula, air, susu sebagai masukan pada mesin jus tersebut. Mesin tersebut akan mengolah bahan-bahan tersebut. Hasil proses tersebut berupa jus atau bukan jus.
Untuk melakukan proses ini, kita membutuhkan suatu alat, sebut saja mesin jus. Mesin jus ini akan mengubah campuran bahan-bahan tadi menjadi jus berdasarkan resep yang kita buat. Cara 3 Kurt membuktikan teorema ketidaklengkapan dan ketidakkonsistenan formalisme matematika (teorema Gödel) pada tahun 1931 dengan makalah yang berjudul “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme”
3 kerja mesin jus ini seperti berikut: masukkan sari buah, gula, air, tentukan resep untuk jus buah, maka mesin jus ini akan memproses dan menjadikan campuran tadi menjadi jus. Sekarang, kita pikirkan bagaimana mesin jus yang ideal tersebut. Untuk membuat mesin jus yang ideal tersebut ada dua kriteria yang diperlukan (Casti & De Pauli, 2000). Yang pertama, mesin itu dapat diandalkan (reliable), artinya setiap campuran bahan-bahan dan resep yang kita masukkan, kemudian akan diproses hanya akan menjadi jus. Yang kedua adalah keutuhan (totality), artinya mesin ini mampu menjalani uji jus. Jika ada sebuah jus tertentu, pastilah dapat dibuat oleh mesin jus tersebut. Dua hal tersebut, keandalan (reliability) dan keutuhan (totality), yang akan membuat jus ini dapat dipasarkan di mana pun, bahkan di rumah kita sendiri. Tetapi muncul pertanyaan besar, apakah mesin ini khayalan atau hanya rekayasa sedemikian rupa sehingga kita dapat meniru jus tertentu? Jika ya, maka banyak pedagang jus akan segera gulung tikar! 2.2 Mesin Kebenaran Ilustrasi di atas menggambarkan upaya yang dilakukan oleh David Hilbert4 untuk membuktikan kebenaran segala hal. Pada tahun 1928, di sebuah Kongres Internasional Matematika (International Congress of Mathematics, ICM) yang diselenggarakan di Bologna, Italia, David Hilbert membuat tantangan bahwa dia dapat membuat suatu perangkat yang dapat membuktikan kebenaran dari semua pernyataan (lihat gambar 2). Singkatnya, mesin kebenaran Hilbert akan membuktikan semua pernyataan matematika. Dalam kuliahnya di Bologna, Hilbert membuat persyaratan untuk mesin kebenaran atau penekanan pada istilah aksiomatis, formal, sistem formal, serta dengan keyakinan bahwa programnya akan menghasilkan formalisasi yang lengkap dari seluruh matematika.
True Statement
Tr u t h Ma c hine
OR False
Gambar 2 Mesin Kebenaran Hilbert
4 David Hilbert adalah matematikawan Jerman yang mempunyai ambisi untuk menciptakan sebuah mesin yang jika dimasukkan suatu pernyataan akan menghasilkan output benar atau salah.
4 Melalui pemikirannya tersebut, David Hilbert menyimpulkan: 1. matematika konsisten, yaitu sebuah pernyataan matematika dan ingkarannya tidak akan pernah dapat dibuktikan kebenaran keduanya 2. matematika lengkap, yaitu semua pernyataan matematika yang benar dapat dibuktikan 3. matematika dapat ditentukan, yaitu akan selalu ada aturan mekanisme untuk menentukan apakan suatu pernyataan matematika itu benar atau salah. Mari kita kembali ke masalah jus tadi, apakah semua jus ini mempunyai resep tertentu sehingga selain itu bukan jus? Orang kebanyakan mempercayai bahwa semua jus itu dapat dituliskan resepnya. Kurt Gödel secara meyakinkan dapat membuktkan bahwa apa yang benar dan apa yang dapat dibuktikan adalah dua hal yang berbeda pada tahun 1931 (tidak sampai 3 tahun setelah karya Hilbert). Kita akan membahas bagaimana Gödel membuktikan bahwa ambisi Hilbert itu tidak akan pernah tercapai. 2.3 Teorema Gödel Pada makalah ini hanya akan dibahas ide dasar dari ketidaklengkapan dan ketidakkonsistenan sistem formal.
pembuktian Gödel saja terhadap
Untuk membuktikan ketidaklengkapan ini, Gödel memakai self-reference, yaitu mencoba merepresentasikan bahasa, simbol, tanda yang ada di Principia Mathematica5 (untuk selanjutnya akan disingkat PM) dengan bahasa, simbol, tanda lain yang terdapat di PM, misalnya bilanganbilangan (yang nantinya akan disebut bilangan Gödel). Gödel mengembangkan skema pengodean untuk menerjemahkan setiap formula logika ke dalam bilangan-bilangan (lihat Tabel I pada lampiran 7.1 untuk penerjemahan tanda-tanda logika elementer ke dalam bilangan asli). Sebagai contoh, “Untuk setiap nilai x maka berlaku x ditambah 0 sama dengan x”, jika dituangkan dalam pernyataan logika menjadi: (∀x )( x + 0 = x ) . Dalam hal ini, x adalah variabel numerik maka diterjemahkan menjadi bilangan prima yang lebih besar dari 12, yaitu 13. Maka pernyataan logika ini jika diterjemahkan dalam bilangan Gödel akan menjadi (8, 11, 13, 9, 8, 13, 12, 6, 5, 13, 9). Selanjutnya bilangan-bilangan ini akan menjadi pangkat dari bilangan-bilangan prima, karena untuk pernyataan ini dihasilkan 11 bilangan, maka yang dipakai adalah 11 bilangan prima awal, yaitu (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Maka bilangan Gödel untuk pernyataan logika: (∀x )(x + 0 = x ) adalah:
2 8 x 3 11 x 5 13 x 7 9 x11 8 x13 13 x17 12 x19 6 x 23 5 x 29 13 x 31 9 = 6 , 9414 x10 108 Setelah penomeran, Gödel melanjutkan dengan pemakaian paradoks kebohongan6 namun ia mengganti “false” dengan “unprovable” sehingga menjadi “pernyataan ini tidak dapat dibuktikan” (“this statement is unprovable”). Melalui penomeran Gödel dihasilkan bilangan Gödel, sebut saja (G) dari “pernyataan ini tidak dapat dibuktikan”. Jika sistem formal tersebut konsisten maka bilangan Gödel (G) ini benar walaupun tidak dapat dibuktikan. Hal ini menunjukkan ketidaklengkapan dari sistem formal tersebut. Hampir serupa dengan ketidaklengkapan, Gödel juga memperlihatkan bagaimana membangun pernyataan aritmatika A, yang diterjemahkan dalam Principia Mathematica adalah buku yang berisikan prinsip-prinsip dasar matematika, terdiri dari 3 volume, ditulis oleh dua matematikawan besar, yaitu Bertrand Russell dan Alfred North Whitehead 5
6 Paradoks kebohongan adalah pernyataan salah yang mengandung kebenaran (kali pertama dipakai oleh Epimenedes), misalnya “Orang itu berbohong”, “pernyataan itu salah”, bagaimana nilai kebenarannya?
5 klaim “aritmatika adalah konsisten”. Dia kemudian menunjukkan “pernyataan A tidak dapat dibuktikan” yang berimplikasi bahwa konsistensi aritmatika tidak dapat ditentukan oleh sistem formal yang merepresentasikan aritmatika sendiri. Untuk ringkasan cara Gödel untuk membuktikan ketidaklengkapan dapat dilihat pada lampiran 2. Berdasarkan langkah-langkah di atas, maka Kurt Gödel mengeluarkan teorema ketidaklengkapan yang terkenal, yaitu: 1. Teorema ketidaklengkapan pertama: Untuk setiap formalisasi aritmatika yang konsisten, akan ada kebenaran aritmatika yang tidak dapat dibuktikan melalui sistem formal tersebut. 2. Teorema ketidaklengkapan kedua: Untuk setiap formalisasi aritmatika yang membentuk suatu pernyataan tidak dapat membuktikan kekonsistenannya sendiri. Sekarang, kita lihat kembali mesin jus tadi. Akan ada suatu jus yang tidak diperoleh dari bahanbahan yang kita sebutkan (sari buah, susu, air, gula), misalnya jika kita masukkan jus, hasilnya akan berupa jus juga. Padahal mesin jus ini hanya menghasilkan jus dari proses bahan-bahan tersebut tetapi ada juga jus yang dihasilkan bukan dari proses tersebut, yaitu dari jus itu sendiri. Jadi, ide mesin jus ini hanya sebuah khayalan saja. Karya Gödel ini merupakan salah suatu masterpiece dalam abad XX, sebab dampak dari karya ini menyentuh hampir semua aspek dalam kehidupan manusia, seperti bahasa, psikologi, fisika, dan terutama perkembangan komputer! Pada bagian selanjutnya akan dibahas berbagai dampak yang terjadi pada ilmu pengetahuan dan kehidupan pada umumnya.
3. Dampak Karya Gödel Setelah karya Gödel ini dipublikasikan tahun 1931, berbagai perkembangan dan penelitian dilakukan terutama pada ilmu komputer. Setelah itu, ilmu komputer mengalami perkembangan pesat dan mulai memasuki “mesin berpikir”, yang kemudian berkembang menjadi “kecerdasan buatan” (artificial intellegence). Dalam bagian ini, hanya akan dibahas beberapa saja, seperti komputer, logika, dan ilmu sosial. 3.1 Mesin Komputasi Universal Pada tahun 1935, adalah Alan Turing, yang kali pertama mengembangkan ilmu komputer, dengan memecahkan “masalah penentuan” (“decision problem”), yaitu apakah ada sebuah prosedur sistematis yang akan memberitahu setiap bentuk string yang diberikan termasuk dalam sistem formal (F). Solusi Turing pada masalah penentuan ini (pada konteks komputasi), sebenarnya identik dengan hasil Gödel pada masalah logika matematika. Masalah ini pada konteks komputasi lebih dikenal dengan istilah ‘masalah pemberhentian’ (‘halting problem’). Pemikiran itu tercipta ketika Alan Turing masih menjadi mahasiswa di Universitas Cambridge saat dia mengikuti kuliah tentang logika matematika. Ide utama dari kuliah itu adalah apakah ada sebuah aturan himpunan terbatas (finite sets) yang merupakan suatu mekanisme yang akan menentukan kebenaran atau kesalahan dari setiap pernyataan yang mungkin dari bilangan yang dapat dibuat dalam bahasa Principia-Mathematica-nya Russell dan Whitehead. Atau singkatnya apakah ada sebuah mesin yang jika diberikan masukan pernyataan apa saja akan memprosesnya
6 dalam suatu waktu tertentu, dalam konteks ini terbatas (finite) lalu mampu memberikan keputusan pernyataan itu benar atau salah. Alan Turing yang ingin menciptakan aturan mekanis guna memecahkan masalah penentuan ini mengembangkan bentuk matematika untuk komputer. Alat yang dibuatnya, kemudian disebut Mesin Turing (Turing Machine), memberikan jawaban lengkap pertama yang memuaskan untuk memunculkan komputasi. Dia menggunakan pemikiran pengetahuan umum dari manusia ketika melakukan komputasi. Pada dasarnya, perhitungan sehingga menjadi pemikiran di luar kepala itu mengikuti suatu aturan tertentu. Sebagai contoh, ketika kita ingin menghitung berapa nilai dari 5 . Kita dapat menggunakan sebuah aturan yang akan memunculkan himpunan bilangan⎛x ⎞ ⎛ 1 ⎞ bilangan ( xi ) , yaitu xn +1 = ⎜ n ⎟ + ⎜⎜ ⎟⎟ . Nilai awal dapat merupakan tebakan, berapa nilai yang ⎝ 2 ⎠ ⎝ xn ⎠ dekat dekat dengan 5 , katakanlah 2 4 = 2 , maka x0 = 2 . Untuk nilai-nilai berikutnya akan disajikan pada Tabel II.
(
)
Tabel II nilai-nilai xx Xn Xn+1 n 0 2 2.4 1 2.4 2.146667 2 2.146667 2.292687 3 2.292687 2.203215 4 2.203215 2.256172 5 2.256172 2.224149 6 2.224149 2.24327 7 2.24327 2.231765 8 2.231765 2.238656 9 2.238656 2.234517 10 2.234517 2.236999 11 2.236999 2.23551 12 2.23551 2.236403 13 2.236403 2.235867 14 2.235867 2.236189 15 2.236189 2.235996 16 2.235996 2.236111 17 2.236111 2.236042 18 2.236042 2.236084 19 2.236084 2.236059 20 2.236059 2.236074 21 2.236074 2.236065 22 2.236065 2.23607 23 2.23607 2.236067 24 2.236067 2.236069 25 2.236069 2.236068 26 2.236068 2.236068 27 2.236068 2.236068 28 2.236068 2.236068 29 2.236068 2.236068 30 2.236068 2.236068
7
Setelah 26 langkah dilakukan, baru kita mempunyai nilai yang diinginkan dan mengumpul pada 2.236068 sampai 6 pecahan desimal. Tapi yang paling penting mengenai metode NewtonRaphson untuk menghitung 5 adalah bahwa prosedur terseebut merupakan sebuah mekanisme murni, proses langkah demi langkah (secara teknis adalah sebuah algoritma) untuk menemukan angka yang diinginkan. Berangkat dari hasil inilah yang membuat Alan Turing mempercayai bahwa sangat mungkin untuk membuat suatu mesin untuk melakukan komputasi. Begitu algoritma dan nilai awal dimasukkan, maka komputasi dari urutan hasil menjadi masalah mekanis murni tanpa gangguan dari luar. Ini akan memerlukan suatu mesin khusus untuk menyelesaikan perhitungan tersebut (bukan sembarang mesin), yaitu mesin Turing. Mesin Turing terdiri dari dua komponen, yaitu: i. Suatu ‘pita’ (‘tape’) yang panjangnya tidak terbatas yang berbentuk persegi-persegi. Setiap persegi memuat satu dari himpunan simbol terbatas. ii. Kepala pembacaan (scanning head) yang dapat berupa salah satu dari bilangan terbatas keadaan (state) atau konfigurasi setiap langkah dari proses komputasional. Kepala ini dapat membaca persegi-persegi dari pita dan menuliskan salah satu simbol pada setiap persegi. Perilaku mesin Turing ini dikontrol oleh suatu algoritma (sekarang disebut program). Program ini disusun dari instruksi bilangan terbatas yang dipilih dari himpunan kemungkinan: i. Berubah atau tetap pada keadaan sekarang dari kepala tersebut (2 kemunginan) ii. Mencetak simbol baru atau mempertahankan simbol lama pada persegi tersebut (2) iii. Bergerak ke kiri atau ke kanan satu persegi (2) iv. Berhenti (1) Ada tujuh kemungkinan perilaku mesin Turing Mesin Turing melakukan komputasi dengan langkah bertahap (step by step procedure), setiap langkahnya dispesifikasikan dalam bahasa tanda pada sebuah 'pita', lalu diperiksa, kemudian didefinisikan (secara diskrit) sebagai 'keadaan internal' ('internal state'). Perbedaan yang diperbolehkan pada 'keadaan internal' adalah bilangan terbatas (finite) dan jumlah total bilangan di 'pita' tersebut juga harus terbatas (walaupun sebenarnya panjang 'pita' itu sendiri tidak terbatas). Mesin ini memulai dari keadaan tertentu, misalnya 0 dan dimasukkan instruksi pada 'pita' (katakanlah dalam urutan 0 dan 1). Kemudian mesin tersebut akan membaca instruksi, lalu memindahkan 'pita' dengan jalan yang definitif sesuai langkah bertahap yang dibuat, yang ditentukan setiap tahap dari 'keadaan internal' dan digit tertentu yang akan diperiksa. Mesin tersebut akan menghapus tanda, membuat yang baru berdasarkan prosedur ini. Ini akan terus berlangsung sampai instruksi 'berhenti' ('stop') pada sebuah nilai tertentu yang ditampilkan pada 'pita' tersebut, dan aktivitas mesin tersebut akan berhenti. Beberapa mesin Turing direferensikan sebagai mesin Turing universal karena dapat mensimulasi mesin Turing apapun. Setiap mesin Turing universal mempunyai kemampuan untuk melakukan komputasi yang dispesifikasi oleh seseorang. Sumbangan Alan Turing yang jenius adalah tipe mesin komputasi yang sederhana ini adalah bentuk dasar dari komputer-komputer yang pernah dibuat bahkan untuk komputer di zaman ini!
8
Kita akan membahas bagaimana teorema Gödel dalam terminologi mesin Turing. Yang menjadi perhatian kita adalah bagaimana menentukan komputasi itu berhenti atau tidak (‘halting problem’)? Kita lihat kembali mesin jus kita. Kita akan membuat jus dari dua mesin jus, mesin jus pertama (J) dan mesin jus kedua (Y). Apa yang dilakukan mesin jus pertama (J) dapat dibuktikan oleh mesin jus kedua (Y). Mesin jus kedua (Y) tidak melakukan proses pengolahan namun hanya untuk menentukan apakah mesin jus pertama (J) menhasilkan jus atau bukan jus. Sesuai cara kerja mesin jus kita, jika dimasukkan campuran bahan-bahan jus maka akan dihasilkan jus. Perhatikan contoh-contoh berikut ini: (A) Jika campuran bahan-bahan jus dimasukkan pada J, maka J akan menghasilkan jus. Hal ini dapat dibuktikan pada Y. Hal ini sesuai dengan kriteria mesin jus kita. Jika kita masukkan bukan campuran bahan-bahan jus, maka: (B) Jika bukan campuran bahan-bahan jus dimasukkan pada J, maka J akan menghasilkan bukan jus. Hal ini juga terbukti pada Y. Sekarang kita pilih campuran bahan-bahan jus tadi, misalkan jeruk, maka kita mendapatkan: (C) Jika jeruk dimasukkan pada J, maka J akan menghasilkan jus jeruk. Bagaimana jika bukan campuran bahan-bahan jus yang dimasukkan melainkan jus jeruk itu sendiri, maka: (D) Jika jus jeruk dimasukkan pada J, maka J tidak mengubah apapun dan tetap menghasilkan jus jeruk juga. Hal ini juga terbukti pada Y. Bagaimana jika bukan jus yang dimasukkan, seharusnya akan menghasilkan bukan jus. Misalnya apel, maka: (E) Jika batu dimasukkan pada J, maka J tidak akan menghasilkan jus. Namun, hal ini tidak terbukti pada Y, Y tidak dapat menentukan hasil dari J. Berdasarkan (E) batu menghasilkan bukan jus pada J, sementara pada Y hasil dari batu tidak dapat ditentukan. Hal seperti inilah yang disebut ketidakdapatditentukan (undecidability), yang juga berlaku pada mesin Turing, yaitu halting problem (untuk contoh lain yang sedikit rumit, anda dapat melihat di lampiran 3). 3.2 Logika Seperti telah dikemukan bahwa paradoks merupakan kesalahan paling dasar dalam sistem logika biner (dua nilai) sehingga membuka jalan bagi Kurt Gödel untuk menciptakan teorema ketidaklengkapan. Salah satu sifat khas dari paradoks ini adalah self-reference. Perlu diingat bahwa self reference bukanlah suatu syarat perlu dan cukup untuk memunculkan sebuah paradoks walaupun hampir sebagian besar paradoks melibatkan self-reference. Self reference
9 ini juga digunakan sebagai dasar dalam sistem kecerdasan buatan (artificial intelligence) untuk menggambarkan agen yang berintrospeksi, yaitu agen yang memilki kemampuan refleksi diri terhadap pikiran, kepercayaan, dan rencana. Salah satu sifat khas agen yang berintrospeksi adalah hadirnya operator percaya (belief) yaitu kondisi ketika agen percaya terhadap sebuah pernyataan dari sebuah teori formal. Logika juga telah berkembang pada arah yang benar-benar baru, yaitu dengan lahirnya logika kabur (fuzzy logic) yang kali pertama diformalkan oleh Lotfi Zadeh melalui himpunan kabur (fuzzy set). Penemuan logika kabur tersebut ini diharapkan dapat memberikan solusi atas munculnya paradoks dalam logika biner. Logika kabur ini berbeda dengan logika biner yang hanya mendasarkan pada dua nilai kebenaran saja, yaitu benar (1) dan salah (0) sedangkan pada logika kabur nilai kebenarannya terbentang dari 0 sampai 1 [0, 1]. Paradoks menghasilkan ketidakkonsistenan dalam logika biner, misalnya pada kalimat: “Pernyataan ini salah”
(1)
Jika kalimat tersebut bernilai benar (p) maka pernyataan ini akan bernilai salah (q=1-p) sementara kalimat tersebut akan konsisten jika p=q atau p=1-p. Hal ini tidak dipenuhi oleh logika biner sebab pada logika biner nilai p dan q hanya 1 atau 0, maka jika p=1, q=0, demikian juga jika p=0, q=1. Hal ini menyebabkan kontradiksi sebab kalimat tersebut bernilai benar sekaligus salah, inilah yang disebut tidak konsisten! Bagaimana dengan logika kabur? Pada logika kabur, nilai kebenaran terbentang pada selang [0, 1] maka kalimat itu konsisten jika p=1-p dan nilai itu dipenuhi pada p=½. Dalam logika kabur, nilai kebenaran kalimat tersebut adalah separuh benar atau separuh salah! Sementara itu Hariadi (2004) , mencoba mengkaji hubungan antara paradoks bohong, logika kabur, dan chaos. Hariadi (2004) mengembangkan paradoks bohong dengan menggunakan logika kabur, dengan memplot derajat kebenaran dari pernyataan dalam paradoks bohong tersebut terhadap parameter kontrol alpha (α) yang juga merupakan derajat kebenaran dalam peta logistik. Simulasi dilakukan terhadap dua kasus, dengan kasus yang kedua merupakan penegasan dari kasus pertama, yaitu pengkuadratan dari kasus pertama. Hasil yang diperoleh untuk kasus pertama selang atraktor semakin bertambah dengan meningkatnya parameter kontrol α sedangkan pada kasus kedua, atraktor berperilaku unik dengan pada awalnya hanya mempunyai dua titik atraktor dan berubah menjadi tak-hingga titik atraktor atau disebut chaos pada α=0.25, tetapi ketika α mendekati nilai 1, titik atraktornya berubah menjadi satu. Pemberian nilai parameter alpha (α) ini merupakan pengembangan dari model Ian Stewart (1999) yang menggunakan model self reference. Tetapi hasil simulasi tetap menunjukkan adanya ketidakkonsistenan yang terlihat dari penambahan selang atraktor dan perubahan titik atraktor! Ternyata, masih tidak mungkin untuk menemukan suatu sistem logika yang lengkap sekaligus juga konsisten!
10 3.3 Ilmu Sosial Teorema ketidaklengkapan Gödel bersifat abstrak dan sangat jauh dari kegiatan praktis7. Tetapi ini bukan berarti tidak berguna untuk dipelajari. Teorema ini telah banyak mempengaruhi banyak bidang ilmu pengetahuan khususnya ilmu pengetahuan alam, seperti fisika. Sayangnya, ilmu pengetahuan sosial mengabaikan dampak tersebut. Ini dapat dimengerti sebab teorema ketidaklengkapan Gödel tersebut ditulis dalam bahasa logika formal yang sulit. Namun, Situngkir (2004) mencoba suatu usaha untuk menemukan dampak dari teorema ketidaklengkapan Gödel pada pendekatan fenomena sosial dengan metodologi ilmiah melalui teori informasi algoritmik, yang kali pertama diperkenalkan oleh Gregory Chaitin (1974). Dalam hal ini, yang dimaksud teori sosial adalah informasi yang dapat membuat kita menggeneralisasi fenomena sosial dalam pengetahuan sosiologis agar mendapatkan suatu pemahaman. Fenomena sosial ini meliputi segala kejadian yang melibatkan identitas, budaya, simbol-simbol, kepercayaan, dan sebagainya. Kejadian-kejadian tersebut dapat berupa konflik sosial, proses pemilihan (voting), dan lain-lain oleh sebab itu fenomena sosial dapat dikatakan sebagai suatu yang tak-terbatas (infinite). Cara mengkonstruksi fenomena sosial adalah dengan mereduksi informasi yang dijelaskan sebagai fenomena sosial. Salah satu diktum ilmiah yang terkenal yaitu pisau cukur Ockham, yang secara prinsipnya mengatakan bahwa teori yang paling banyak dipakai mempunyai penjelasan yang terbaik. Selanjutnya, salah seorang sosiolog besar, yaitu Talcott Parson8 (1945) menambahkan bahwa teori yang baik adalah teori yang sederhana namun mampu menjelaskan banyak hal. Maka untuk membentuk teori sosial adalah dengan memadatkan sekecil mungkin informasi yang diperoleh dalam fenomena sosial untuk menjelaskan hal yang paling umum. Secara sekilas, pemikiran Parson ini menyerupai David Hilbert yang ingin membuktikan secara formal semua pernyataan matematik (Casti & De Pauli, 2000). Tetapi seperti kita sudah bahas pada bagian sebelumnya bahwa hal itu tidak mungkin dengan munculnya teorema Gödel. Kita dapat memodelkan seorang teoretisi sosial sebagai komputer teoretis yang mencari penjelasan fenomena sosial berdasarkan pemahamannya pada teori sosial. Tapi, perlu diingat tidak selamanya komputer dapat menjelaskan fenomena tertentu. Selain itu, penelitian sosial dilakukan untuk menjelaskan suatu fenomena sosial dengan melalui algoritma tertentu dengan suatu aturan kesimpulan dari sebuah teori sosial untuk merekonstruksi fenomena sosial yang dimaksud. Berdasarkan teori informasi algoritmik, fenomena sosial mengandung kompleksitas yang tak-terbatas maka tidak mungkin menangkap seluruh fenomena sosial secara lengkap dalam sebuah teori sosial tunggal dalam lingkungan yang logis juga, yaitu tidak mungkin menghasilkan sebuah teori sosial tunggal yang lengkap dan konsisten sekaligus! Maka Situngkir (2004) menyarankan bahwa untuk mengukur kekuatan sebuah teori sosial dapat melalui dua cara, yaitu kemampuan untuk menjelaskan dan ketepatan dalam prediksi. Melalui pendekatan inilah diharapkan teori sosial tidak terperangkap lagi dalam perangkap deksripsi dan perangkap logika. Seperti telah dikemukan bahwa kebanyakan fenomena sosial belum diketahui secara maksimal dengan kompleksitas tak-terbatas dari fenomena sosial dibandingkan dengan kompleksitas tak-terbatas dari teori sosial. Memang kompleksitas tak-terbatas dari fenomena 7 8
Pernyataan dari Gregory Chaitin saat memberikan kuliah di Massachusetts Institute of Technology, Amerika Serikat Talcott Parson adalah seseorang sosiolog besar yang dikenal sebagai pelopor fungsionalisme
11 sosial ini menjadikan suatu batas tetapi bukan berarti itu menjadi penghalang malah sebaliknya memberikan suatu tantangan untuk menciptakan teori yang lebih baik lagi, seperti penelitian oleh Doran (1997), Axtell (2000), Langton (2000) tentang kehidupan dan masyarakat buatan (artificial life, society). Ini juga memberikan tantangan kepada kita untuk mengeksplorasi fenomena sosial yang belum kita tahu untuk kehidupan sosial yang lebih baik lagi. 3.4 Sains kognitif Sejak Descartes9, banyak orang yang mulai berspekulasi tentang mungkin atau tidaknya memahami pikiran (mind) seperti layaknya sebuah mesin. Setelah itu Alan Turing berhasil menciptakan Mesin Turing, yaitu sebuah mesin komputasi melalui sebuah proses mekanis. Bangunan dasar mesin itu adalah suatu sistem formal. Orang-orang kembali melihat sistem formal untuk memahami pikiran seperti layaknya mesin. Tetapi J.R Lucas yang kemudian dilanjutkan oleh Roger Penrose membantah hal ini. Banyak orang mulai meragukan lagi kemampuan sistem formal untuk menjelaskan pikiran. Tetapi ketidakmungkinan memahami pikiran seperti mesin telah membuat beberapa peneliti untuk melakukan dirty and quick trick untuk membiarkan pikiran yang tidak mekanistik itu tidak lengkap atau tidak konsisten sebab yang dicari adalah teori tentang pikiran yang bersifat commonsense dengan “ketidak-dapat ditentukan” (“undecidability”) itu adalah hal yang wajar. Tetapi kemudian trik ini tidak dapat menjelaskan mana yang commonsense atau bukan dalam sistem formal. Timbul pertanyaan selanjutnya bagaimanakah menghadirkan pikiran commonsense dalam fisik mesin. Turing mengusulkan “permainan tiruan” (imitation game, 1950) dengan menyebutkan kemungkinan mesin yang belajar (learning machine). Pada awal 90’an, sejalan dengan perkembangan komputasi dan simulasi memunculkan konsep brojol-an (emergence) dalam suatu bidang penelitian yang disebut ilmu kompleksitas. Suroso (2004) memperlihatkan kemungkinan pemahaman (atau pemodelan) pikiran sebagai mesin dalam konteks mesin yang belajar atau otonomi (autonomous) sehingga pembatasan sistem formal dapat diabaikan. Suroso (2004) mencoba mengelaborasi bagaimana mesin diimplementasikan dalam tubuh yang bio-mekanis atau komponen-komponen fisik apa saja yang diperlukan untuk menjelaskan suatu jenis khusus pikiran dari manusia dapat bekerja (tetapi tidak semua pikiran mengikuti aturan sistem formal). Jika pikiran secara kasarnya adalah program komputer maka dapat dikatakan bahwa pikiran adalah sebagai manipulasi sintaktis yang diimplementasikan dalam tubuh biologis sementara manipulasi sintaktis itu sendiri dianggap tidak lengkap atau tidak konsisten yang akan membawa pada masalah brojol-an. Implementasi ini dibedakan berdasarkan metode yang paling banyak digunakan ada dua, yaitu koneksionisme (connectionism) dan representasi pengetahuan (knowledge representation) (Suroso, 2004:3-6). Untuk memodelkan mesin yang otonomi maka kita akan menempatkan diri sebagai pengamat suatu mesin tertentu sehingga kita dapat melakukan apapun terhadapnya. Jika mesin tersebut merespon, (kita sebagai pengamat) berharap respon tersebut bukan hanya hasil dari stimuli tertentu dan desain yang mengandung aksioma dan aturan-aturan yang diberikan di awal. Inilah 9 René Descrates, salah satu tokoh filsuf rasional dan matematikawan terkenal. Salah satu jasanya dalam matematika adalah diagran cartesius yang kita pakai dekarang. Peryataan beliau yang terkenal, yaitu “cogito ergo sum” (“aku berpikir maka aku ada”)
12 yang dimaksud dengan mesin otonomi. Singkat kata, mesin yang bebas memodifikasi dirinya, misalnya mendapatkan proposisi baru seperti konsep baru, menolak beberapa kesimpulan yang ilegal, semuanya ini diringkas dalam prinsip umum. Namun, perdebatan masih berlangsung antara, kaum yang melihat secara fisik saja dengan kaum yang melihat secara fungsi, perdebatannya antara level mikro dan level makro, antara mental dan biologis, ada sebuah hukum yang menghubungkan keduanya (misal: mikro dan makro) yang beroperasi sebagai proses menengah (intermediate), yang disebut Ernest Nagel sebagai “Hukum Jembatan” (“Bridge Law”) sedangkan pada pendekatan kontinu, Stephen Pepper menyebutnya sebagai “Hukum Brojol-an” (“Emergence Law”). Kondisi “tak-terprediksikan” (unpredictibility) hadir ketika tidak adanya penghubung antara level mikro dan level makro atau tidak adanya “Hukum Jembatan” tersebut. Level meso (menengah) ini yang menghubungkan dua level yang sangat jauh berbeda ini sedang menjadi topik penelitian yang menarik. Level meso ini tetap dihasilkan dari brojol-an pada level mikro tetapi tidak akan mem-brojol lagi pada level makro! Meskipun jika pikiran itu sepenuhnya mekanik atau otonomi dan “tak-dapat ditentukan” (undecidable) hadir maka menurut pengamat, ada suatu kemungkinan bahwa “tak-dapat ditentukan” itu di-brojol-kan dari dua sifat level mikro yang berlainan. Yang menjadi perhatian adalah walaupun “tak-dapat ditentukan” itu hadir, hal ini tokh tidak akan membunuh kita atau membuat pikiran kognitif atau mesin kognitif kita bekerja dengan tidak benar, misalnya jika “tidak-dapat ditentukan” hadir, kita dapat langsung berpindah ke teorema yang lain tanpa harus terganggu untuk menyelesaikan konsep logika abstrak tersebut. Kita dapat mengikut Gödel bahwa apa yang benar tidak perlu terkomputasi. Bisa juga mengikuti Turing “jika suatu desain diimplementasikan untuk tidak saja untuk kelengkapan untuk menemukan teorema dalam satu level melainkan lengkap secara keseluruhan pada semua level, maka kelengkapan seperti itu tidak akan tercapai tetapi mesin tersebut akan memulai sesuatu yang lain”. Kita tidak akan membahas sampai sejauh mana kita dapat dihitung atau tidak(computable) tapi sebaliknya bagaimana kita memahami diri kita dengan bantuan komputer.
4. Penutup Setelah kita berkelana mulai dari awal abad XX sampai awal XXI, tentu kita dapat melihat kegunaan dari Teorema Gödel ini. Beberapa contoh telah diberikan di atas dan diharapkan mampu memperkaya cakrawala kita. Untuk diketahui bahwa Teorema Gödel ini tidak saja digunakan untuk bidang ilmu penngetahuan saja tetapi juga dihubungkan dengan masalah mistik dan agama (Casti & De Pauli, 2000: hal 41) meskipun Gödel sewaktu di Universitas Princeton dia menjadi tertarik untuk mempelajari keberadaan Tuhan dan perpindahan jiwa (hal 86). Tidak mungkin mendapatkan kelengkapan dan kekonsistenan sekaligus secara bersamaan ini menjadi hal yang perlu diperhatikan juga untuk kalangan yang bergerak di bidang hukum. Sewaktu Gödel ingin mendapatkan kewarganegaraan Amerika Serikat, dia harus mempelajari undang-undang negara tersebut. Dia menemukan ketidakkonsistenan dalam undang-undang tersebut bahwa presiden Amerika Serikat dapat menjadi diktator padahal menurut hakim undang-
13 undang Amerika itu lengkap, kemudian dia memberitahu kepada sahabat-sahabat dekatnya, yaitu Oskar Morgenstern10 dan Albert Einstein. Kita memang tidak dapat menghindari ketidaklengkapan dan ketidakkonsistenan tersebut tetapi ini bukan berarti dunia akan kiamat. Teorema Gödel bukan sebagai suatu penghalang kita untuk menciptakan sesuatu seperti kecerdasan buatan, kehidupan buatan (Langton), masyarakat buatan (Eipsten & Axtell), dan lain-lain. Setelah kita ber-Gödel ria sejenak, sekarang mari kita nikmati jus kita dulu.
5. Pengakuan Penulis mengucapkan terima kasih kepada Surya Research Intl. untuk bantuan dana selama penulisan makalah ini, Yohanes Surya untuk beberapa bukunya, Board of Science BFI yang telah memberikan kesempatan untuk menulis ulang topik ini, Hokky Situngkir, Rendra Suroso atas diskusinya, khususnya Yun Hariadi yang telah memberikan inspirasi, dan terakhir untuk semua scholars dan civitas akademika di BFI atas bantuannya. Semua kesalahan dalam makalah ini menjadi tanggung jawab pribadi penulis sepenuhnya.
6. Daftar Pustaka [1] Casti, John L. & De Pauli, Werner, Gödel: A Life of Logic, Cambrigde, MA, Perseus Publishing, 2000 [2] Franzén, Torkel, “Using the Gödel sentence to prove the incompleteness theorem”, published online, URL: http://www.sm.luth.se/~torkel/eget/godel/theorems.html [3] Gödel, Kurt, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme” (transl. B. Meltzer), Monatshefte für Mathematik und Physik, 38:173-198, 1931/1962 [4] Hariadi, Yun, “Attractor Logic: On Liar Paradox with Fuzzy Logic, will be published on forthcoming Journal of Social Complexity (JOSC) Vol 1 No.5 2004, 2004 [5] Hofstadter, Douglas, “Kurt Gödel”, TIME Magazine, published http://www.time.com/time/time100/scientist/profile/godel.html
online:
[6] O'Connor, J.J, et al., “Kurt Godel”, published online, URL: http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Godel.html [7] Penrose, Roger, “Shadows of the Mind: A Search for the Missing Science of Consciousness”, New York, NY, Oxford University Press Inc., 1994
Oskar Morgenstern adalah ekonom hebat dari Austria, bersama John Von Neumann menerapkan game theory dalam ekonomi
10
14 [8] Shalizi, Cosma Rohilla, "Gödel's Theorem", notebooks, published online, URL : http://cscs.umich.edu/~crshalizi/notebooks/godels-theorem.htm l [9] Situngkir, Hokky, "How Far Can We Go Through Social System?", will be published on forthcoming Journal of Social Complexity (JOSC) Vol 1 No.5 2004, 2004 [10] Suroso, Rendra, "Emergent Undecidability Is Decidable", will be published on forthcoming Journal of Social Complexity (JOSC) Vol 1 No.5 2004, 2004 7. Lampiran 7.1 Lampiran 1 Tanda ~
∨ ⊃ ∃ = 0 S ( ) ‘
∀ +
Tabel I Penomeran Gödel Untuk Tanda-tanda Logika Elementer Bilangan Gödel Arti 1 ingkaran 2 atau 3 jika... mka 4 terdapat 5 sama dengan 6 nol 7 kelanjutan langsung 8 tanda kurung buka 9 tanda kurung tutup 10 aksen 11 untuk setiap 12 tambah
7.2 Lampiran 2 Langkah-langkah utama yang dilakukan Gödel untuk membuktikan teoremanya adalah sebagai berikut (disarikan oleh Casti dan DePauli): 1. Penomeran Gödel, yaitu mengembangkan skema pengodean (coding) untuk menerjemahkan setiap formula logika dan urutan pembuktian dalam Principia Mathematica ke dalam pernyataan-pernyataan “cermin-gambar” (“mirror image”) pada bilangan asli (lihat Tabel I). 2. Paradoks Bohong, yaitu mengganti pemikiran dari “benar” (“truth”) dengan “terbuktikan” (“provability”), dengan cara demikian maka paradoks kebohongan diterjemahkan menjadi “pernyataan ini tidak terbuktikan” (“this statement is unprovable”) 3. Kalimat Gödel, yaitu memperlihatkan bahwa kalimat “pernyataan ini tidak terbuktikan” mempunyai imbangan aritmatika, kalimat Godel (G), dalam setiap formalisasi aritmatika yang mungkin. 4. Ketidakklengkapan, yaitu membuktikan bahwa kalimat Gödel (G) pasti benar jika sistem formal tersebut konsisten.
15 5. Tidak ada jalan keluar, yaitu membuktikan bahwa walaupun ditambah aksioma baru untuk membentuk sistem baru, yang dapat membuktikan G, maka sistem baru tersebut (dengan tambahan aksioma baru) akan mempunyai kalimat Gödel (G) yang tidak terbuktikan lagi. 6. Konsistensi, yaitu membangun pernyataan aritmetis yang menegaskan bahwa “aritmatika adalah konsisten”. Menunjukkan bahwa peryataan aritmetis ini tidak dapat dibuktikan, maka ini menunjukkan bahwa aritmatika sebagai sebuah sistem yang formal terlalu lemah untuk membuktikan konsistensinya.
7.3 Lampiran 3 Kita akan melihat bagaimana teorema Godel dalam terminologi mesin Turing. Pertimbangkan suatu komputasi yang bergantung atau bekerja berdasarkan pada bilangan asli, a . Kita namakan saja komputasi tersebut, K (a ) . Komputasi ini akan menyediakan 'keluarga komputasi' (‘family of computation’) untuk setiap komputasi terpisah dari setiap bilangan asli (0,1,2,3,K) yang disebut K (0 ), K (1), K (2 ), K . Dalam terminologi mesin Turing, K (a ) ini adalah eksekusi dari mesin Turing terhadap bilangan a , yaitu bilangan a sebagai masukan dan mesin itu akan melakukan komputasi! Yang menjadi perhatian kita adalah apakah mesin ini akan pernah berhenti atau tidak untuk setiap pilihan bilangan a. Untuk menjelaskan hal ini, kita coba lihat contoh-contoh berikut ini: (A) Temukan suatu bilangan yang bukan penjumlahan dari bilangan kuadrat a dan (B) Temukan suatu bilangan ganjil yang merupakan penjumlahan dari bilangan genap a Komputasi (A) hanya akan berhenti ketika a = 0,1,2, dan 3 ketika menemukan bilangan 1,2,3, dan 7 (7 bukan merupakan penjumlahan 3 bilangan ganjil, untuk perhitungannya lihat Penrose, 1994: 66-67). Sementara untuk (B), komputasi ini tidak akan pernah berhenti pada a berapapun! Tetapi jika kita ingin memastikan bahwa (A) tidak berhenti ketika a ≥ 4 , maka kita membutuhkan matematika yang canggih (dalam hal ini bukti Lagrange), tetapi untuk (B) sudah jelas tidak akan pernah berhenti! Tentu ada sebuah prosedur yang ada di matematika untuk memastikan ketidakberhentian dari suatu komputasi, tetapi bisakah diterapkan dalam bahasa komputasi? Katakanlah, kita mempunyai suatu prosedur komputasi, yaitu P , yang ketika berhenti akan tetap mendemonstrasikan bahwa komputasi seperti K (a ) sebenarnya tidak pernah berhenti. Bayangkan jika P dapat menangkap semua prosedur yang ada pada para matematikawan untuk mendemonstrasikan bahwa komputasi tidak berhenti. Sesuai dengan itu, jika dalam sebuah kasus P ini pernah berakhir, tetap akan mendemonstrasikan seperti manusia bahwa komputasi tidak pernah berhenti!
16 Yang ditekankan di sini adalah bahwa P ini tidak akan pernah memberikan jawaban yang salah, yaitu jika disimpulkan bahwa K (a ) ini tidak berhenti maka pada kenyataannya memang tidak berhenti. Jika P memberikan jawaban sesuai kenyataan, kita katakan P itu selaras. Namun sebaliknya, jika P tidak selaras, maka komputasinya pasti salah! Untuk setiap P yang memberikan kesalahan bahwa komputasi, K (a ) tidak berhenti padahal pada kenyataannya berhenti, maka komputasi K (a ) akan mengantar pada penolakan (refutation) P ! Untuk menerapkan P pada komputasi secara umum, kita memerlukan pengodean untuk seluruh komputasi yang berbeda dari K (a ) , jadi P ini akan menggunakan kode tersebut untuk komputasi. Semua kemungkinan komputasi yang berbeda pada kenyataannya dapat dibuat senarainya, katakanlah menjadi: K 0 , K 1 , K 2 , K 3 , K yang disebut K q atau komputasi ke-q.
Ketika komputasi itu diterapkan pada bilangan tertentu, a , kita tuliskan K 0 (a ), K 1 (a ), K 2 (a ),K yang disebut K q (a ) . Komputasi ini dalam terminologi mesin Turing berarti komputasi yang
mengeksekusi pasangan bilangan q dan a (pertama Komputasi pada q dilanjutkan a ) untuk menghasilkan K q (a ) . Prosedur P sebenarnya dapat dikatakan sebagai komputasi tertentu, yang ketika ditampilkan pasangan bilangan tertentu, q, a , yang mencoba memastikan bahwa komputasi K q (a ) tidak akan pernah berhenti! Prosedur P hanyalah suatu himpunan keselarasan dari aturan komputasi untuk memastikan bahwa beberapa komputasi K q (a ) tidak akan pernah berhenti sebab P bergantung pada dua bilangan, yaitu q dan a , maka kita mendapatkan: (C) Jika P(q, a ) berhenti maka K q (a ) tidak berhenti Sekarang coba pertimbangkan jika pernyataan tertentu dari (C) yang q -nya dibuat sama dengan a ( q = a , ini adalah langkah pertama dari 'diagonal slash’11), maka untuk q = a , kita mendapatkan: (D) Jika P (a, a ) berhenti maka K a (a ) tidak berhenti Sekarang, P hanya bergantung pada satu bilangan saja, a , jadi niscaya P ini adalah salah satu dari komputasi K a (K 1 , K 2 , K 3 , K) sebab K a ini adalah senarai dari semua komputasi yang ditampilkan terhadap satu bilangan tertentu dari a , katakanlah pada t , pada kenyataan dari K t , kita akan mendapatkan: (E) P (a, a ) = K t (a )
Diagonal slash adalah cara yang menggunakan penyamaan variabel. Cara ini ditemukan oleh Georg Cantor, matematikawan yang berpengaruh di abad XIX.
11
17 Bagaimana jika nilai tertentu dari a itu adalah t ( a = t , langkah kedua dari 'diagonal slash'), berdasarkan (E) kita mendapatkan:
(F) P (t , t ) = K t (t )
Berdasarkan (D), dengan a = t , kita mendapatkan: (G) Jika P (t , t ) berhenti maka K t (t ) tidak berhenti Subtitusi (F) pada (G), kita mendapatkan (H) Jika K t (t ) berhenti maka K t (t ) tidak berhenti Melalui deduksi ini, komputasi K t (t ) pada kenyataannya tidak berhenti (berdasarkan (H), jika K t (t ) berhenti maka K t (t ) tidak berhenti). Namun P(t , t ) tidak berhenti juga sebab melalui (F), P (t , t ) = K t (t ) . Maka, prosedur P tidak mampu memastikan bahwa komputasi tertentu ini,
K t (t ) tidak berhenti meskipun K t (t ) tidak berhenti. Inilah yang disebut ketidakdapatditentukan (undecidability).
