Teori ketidaklengkapan Godel

Salah satu artikel terbaik yang bisa menjelaskan tentang Teori Ketidaklengkapan Godel (Godel’s Incompleteness Theorem) adalah artikel yang ditulis oleh Solomon Feferman. Artikel ini berjudul “The Nature and Significance of Godel’s Incompleteness Theorem“.

Teori Ketidaklengkapan Godel berusaha untuk menunjukkan bahwa dalam setiap sistem formal (formal system), terdapat pernyataan yang benar (true), namun pernyataan tersebut tidak dapat dibuktikan baik kebenarannya maupun ketidakbenarannya di dalam sistem tersebut.

Pada dasarnya, Teori Ketidaklengkapan Godel menunjukkan bahwa sebuah sistem formal, tidak dapat membuktikan dirinya sendiri. Untuk dapat membuktikan dirinya sendiri, sistem tersebut harus memperluas batasannya. Akan tetapi, sistem yang telah diperluas ini, juga tidak akan bisa membuktikan dirinya sendiri. Demikian seterusnya.

Beberapa berspekulasi bahwa Teori Ketidaklengkapan Godel membuktikan bahwa pikiran manusia tidak sama dengan suatu alat mekanis, bahwa manusia tidak dapat membuktikan dirinya sendiri. Bahwa logika, dasar dari semua pemikiran manusia, hanyalah sebuah asumsi. Logika tidak bisa membuktikan dirinya sendiri.

Mengapa memakai LaTeX

Bagi beberapa orang, mungkin latex bisa jadi adalah bahan sintetis seperti karet. Akan tetapi, dalam tulisan ini, LaTeX berarti bahasa markup untuk menyiapkan dokumen dengan menggunakan sistem pencetakkan (typesetting) TeX yang dibuat oleh Donald Knuth (Orang yang sama yang menulis buku klasik The Art of Computer Programming).

Di dunia tunjuk dan klik (point-and-click) sekarang, mungkin orang akan berpikir aneh jika ada yang menyarankan penggunaan LaTeX untuk membuat dokumen. Dengan menggunakan program pengolah kata, seperti Microsoft Words atau OpenOffice (dan saudaranya LibreOffice), tampaknya sebuah dokumen dapat dihasilkan dengan mudah. Lalu, untuk apa bersusah payah menggunakan LaTeX?

Jika Anda belum tahu, membuat dokumen dengan menggunakan LaTeX membutuhkan pengetahuan akan bahasa markup seperti kita menulis dokumen HTML (HyperText Markup Language). Dengan demikian, setiap efek terhadap tulisan, dituliskan dengan menggunakan markup. Ada markup untuk menulis miring, tebal, dan seterusnya.

Dengan cara menulis seperti itu, LaTeX dijuluki pembuat dokumen yang bersifat WYMIWYG (What You Mean Is What You Get — Kamu mendapatkan yang kamu maksud). Bandingkan dengan program pengolah kata yang bersifat WYSIWYG (What You See Is What You Get — Kamu mendapatkan yang kamu lihat).

Lalu, mengapa menggunakan LaTeX?

Jawaban yang paling sederhana adalah bahwa dengan LaTeX, kita lebih memiliki kendali terhadap hasil keluaran dokumen yang kita buat agar sesuai dengan keinginan kita. Hal ini terutama terasa ketika kita harus mengelola dokumen yang tebal.

Sebab lain adalah dengan LaTeX, otomatisasi merupakan sesuatu yang mudah. Daftar Isi, Daftar Gambar, Daftar Istilah, Daftar Tabel, Daftar Singkatan, Acuan terhadap nomor gambar dan letak halamannya, Daftar Pustaka, serta Indeks, semua dihasilkan secara otomatis oleh LaTeX. Dengan demikian, kita hanya perlu menulis, dan tak perlu memikirkan semua itu.

Terakhir, LaTeX menyimpan tulisan kita dalam file teks. Dengan demikian, kita bisa menggunakan program versioning (seperti svn) untuk merekam jejak perubahan dalam dokumen yang kita buat. Seperti tahapan penerbitan perangkat lunak, kita bisa menggunakan istilah alfa, beta, dan versi untuk tulisan kita.

Jika Anda tertarik, selamat mencoba LaTeX. Saya menemukan menulis jadi lebih menyenangkan dengan LaTeX. 🙂

Algoritma SRT (Shortest Remaining Time) untuk Antrian Proses di Sistem Operasi

Sebelumnya saya sudah memaparkan algoritma FCFS untuk antrian proses di sistem operasi. Kali ini, saya akan mencoba untuk menjelaskan antrian lain yang disebut dengan SRT atau Shortest Remaining Time.

Saat pertama kali program dijalankan (misalnya ikon program tersebut di-doubleclick), sistem operasi akan membuat Process Control Block dan memasukkan proses yang baru ini ke dalam keadaan (state) New. Setelah proses ini dipindahkan ke RAM, maka proses akan berubah keadaan menjdi Ready dan mengantri bersama proses lain untuk dijalankan oleh CPU (Central Processing Unit).

Setiap proses memiliki asumsi berapa lama proses tersebut dijalankan (service time). Algoritma SRT memilih proses yang memiliki sisa waktu paling sedikit untuk dijalankan selanjutnya oleh CPU.

Contohnya, proses A memiliki service time 10 detik (misalnya untuk kemudahan) sedangkan proses B memiliki service time 15 detik. Dengan demikian, proses A akan dieksekusi terlebih dahulu. Proses ini bersifat preemptive (dapat dihentikan eksekusinya oleh sistem operasi) dan sisa waktu dari setiap proses dihitung ulang setiap waktu. Dengan demikian, jika suatu saat ketika proses A sudah dijalankan 3 detik (sehingga sisa waktunya adalah 15 detik – 3 detik = 12 detik) lalu masuk proses C dengan service time 5 detik, proses A akan dihentikan dan proses C akan dieksekusi karena memiliki sisa waktu yang lebih kecil.

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? 🙂

Mengganti kata “Contents” menjadi “Daftar Isi” di LaTeX

Daftar Isi dihasilkan secara otomatis ketika kita menggunakan LaTeX. Akan tetapi, judul dari daftar isi itu menggunakan Bahasa Inggris, yaitu “Contents”. Untuk mengganti judul tersebut, misalnya ke “Daftar Isi”, gunakan perintah berikut.

\renewcommand{\contentsname}{Daftar Isi}

Menggunakan vim sebagai hex editor

Untuk menggunakan Vim sebagai Hex Editor, cukup buka file binari dan masukkan perintah berikut (tekan ESC dulu)

:%! xxd

Untuk kembali ke mode normal, ketikkan perintah berikut (tekan ESC dulu)

:%! xxd -r

 

Cerita di balik Ctrl-Alt-Del

Ctrl-Alt-Delete adalah kombinasi tombol di papan ketik komputer kita yang biasanya kita gunakan baik untuk melakukan reboot ataupun memunculkan Task Manager (Windows). Kombinasi tiga tombol ini terkenal dengan sebutan “Three-finger salute“.

Adalah David Bradley yang merancang tiga tombol ini saat dia bersama 12 teknisi lain merancang IBM PC. Saat itu, para teknisi harus sering kali melakukan restart ulang terhadap IBM PC dengan cara mematikan komputer, yaitu menghentikan asupan listrik ke komputer dan menyambungkannya lagi. Akan tetapi, cara ini membutuhkan waktu relatif lama padahal pekerjaan melakukan restart perlu dilakukan berulang-ulang. Ini memerlukan waktu lama karena setelah dimatikan, para teknisi harus menunggu terlebih dahulu sebelum komputer kembali dihidupkan. Hal ini dilakukan untuk mencegah kerusakan catu daya dan hard disk.

Untuk mengatasi ini, David Bradley merancang cara untuk melakukan warm reboot, yaitu me-restart ulang komputer tanpa harus menghentikan asupan listrik. Bradley memilih Ctrl-Alt-Del karena kombinasi ketiga tombol ini kecil kemungkinan ditekan secara bersamaan secara tidak sengaja.

Ketiga tombol ini, yang awalnya hanya dirancang untuk para teknisi, ternyata dianggap berguna oleh para pengembang sistem operasi sehingga digunakan untuk satu fungsi tertentu di sistem operasi. Demikianlah muncul pernyataan David Bradley “I may have invented it (control-alt-delete), but I think Bill [Gates] made it famous“.

Perbedaan program dan proses/task di sistem operasi

Kita mengenal program dalam dunia komputer. Program terdiri dari rangkaian instruksi yang dibuat untuk memenuhi satu fungsi tertentu. Program dapat dibuat dengan menggunakan berbagai bahasa pemrograman. Dari bahasa pemrograman tingkat tinggi, seperti C++ dan Java hingga bahasa pemrograman tingkat rendah, seperti bahasa Assembly* (saya menolak untuk menuliskannya bahasa rakitan dengan alasan yang sama saya tidak mau menyebutkan C++ sebagai “C tambah tambah”).

Dengan bahasa apapun itu, program pasti diubah ke dalam urutan simbol (string) 1 dan 0 agar dapat dijalankan oleh komputer.

Sistem operasi modern biasanya memiliki kemampuan untuk menjalankan lebih dari satu program dalam satu waktu (walaupun ini sebenarnya ilusi untuk komputer dengan satu prosesor). Kemampuan ini disebut multiprogramming.

Dalam sistem operasi, untuk mendapatkan kesan lebih dari satu program berjalan dalam satu waktu, program dieksekusi secara bergantian (interleave) dalam waktu yang relatif sangat cepat. Suatu program tidak harus selesai terlebih dahulu sebelum program lain menggantikannya untuk dijalankan oleh CPU. Meskipun program yang belum selesai ini berhenti, sistem operasi memastikan bahwa program ini akan mendapatkan gilirannya lagi nanti (dengan syarat tidak terdapat kesalahan dalam program ini).

Dengan pergantian yang seperti ini, sebuah program harus mengingat saat terakhir ia dijalankan. Hal ini disebabkan saat dijalankan, program bekerja dengan data, file, dan berada dalam posisi tertentu. Semua ini akan hilang jika program tidak menyimpannya. Agar program tidak harus kembali lagi dari awal ketika mendapatkan jatah CPU-nya kembali, semua “data kerja” program tadi disimpan di sebuah struktur data yang disebut dengan PCB (Process Control Block). Di Linux (saya benar-benar bermaksud Linux dan bukan GNU/Linux), PCB ini adalah sebuah struct yang bernama task_struct.

Nah, yang disebut dengan proses/task itu adalah program + PCB. Artinya bisa juga disebutkan secara sederhana bahwa program itu disimpan di hard disk, sementara proses itu disimpan di RAM (artinya sedang dijalankan).

[* masih banyak yang salah menyebutkan bahasa Assembly sebagai bahasa Assembler. Bahasa Assembly adalah bahasanya. Adapun Assembler adalah “compiler”-nya]

 

 

Mengganti nama bab di LaTeX

LaTeX mendefinisikan bab suatu tulisan dengan markup \chapter{nama chapter}. Dengan markup ini, setiap bab akan ditulis chapter + penomoran chapter tersebut. Jika ingin mengubah kata “Chapter” menjadi “Bab”, tuliskan seperti ini

\renewcommand{\chaptername}{Bab}

Algoritma FCFS (First-Come-First-Served) untuk Antrian Proses di Sistem Operasi

Sistem operasi yang bersifat multiprogramming, memiliki kemampuan untuk memberikan ilusi seakan-akan beberapa program dapat berjalan bersamaan. Ilusi ini dapat terjadi karena proses (program yang sedang dijalankan) dieksekusi secara bergantian dalam waktu yang sangat singkat (dalam milidetik). Dengan jumlah yang banyak, proses-proses tersebut harus menunggu dalam sebuah antrian untuk dieksekusi. Sebuah algoritma diperlukan untuk menentukan proses mana yang akan dieksekusi selanjutnya.

Algoritma antrian dipilih untuk meningkatkan throughput dan kecepatan-tanggap dari sebuah program. Akan tetapi, kedua tujuan ini jarang sekali dapat dipenuhi secara bersamaan. Throughput biasanya menjadi prioritas untuk server karena sifat proses yang dieksekusinya biasanya tidak menuntut untuk terasa cepat-tanggap terhadap setiap permintaan. Adapun aplikasi desktop biasanya lebih memprioritaskan kecepatan-tanggap karena aplikasi desktop sering melakukan interaksi langsung dengan pengguna. Jika sistem operasi tidak menjamin kecepatan-tanggap terhadap aksi dari pengguna, sistem operasi akan dirasa lamban dan bukan menjadi pilihan pengguna.

Nah, untuk memenuhi semua itu, telah diciptakan berbagai algoritma. Salah satu yang paling sederhana adalah algoritma FCFS (First-Come-First-Served). Algoritma ini sederhana saja. Proses yang lebih dulu datang (first-come) akan dieksekusi (first-served).

Algoritma ini menjamin setiap proses yang meminta untuk dieksekusi akan dijalankan. Akan tetapi, algoritma ini tidak cukup “pintar” untuk memberikan tingkat throughput ataupun kecepatan-tanggap yang tinggi.