Gregory John Chaitin mendefinisikan suatu bilangan real yang disebut dengan omega (Ω). Sebuah bilang real yang sangat aneh, bilangan tersebut terdefinisi defined, tapi tak bisa dihitung uncomputable. tapi  sebelumnya saya akan membahs memngenai Halting Problem

Halting Problem

Misalkan kita punya program komputer sederhana  dengan intruksi

“ambil x bilangan bulat kurang dari 10 kalikan terus dengan x itu sendiri sampai hasilnya lebih dari 100”

Jika kita ambil x=9  maka program akan berhenti di langkah ke-2

Jika kita ambil x=4  maka program akan berhenti di langkah ke-3

tapi jika kita ambil x=1 maka program tersebut tidak akan pernah berhenti sampai hari kiamat hehe 😛

Pada  contoh program sederhana diatas dengan mudah kita mengetahui variabel input apa yang membuat  program tersebut  jalan terus menerus tanpa henti. tapi bagaimana kalau program itu rumit, bagaimana kita mengetahui suatu input jika diinputkan ke suatu Program  maka program itu akan berhenti atau malah jalan terus menerus? Ya cara paling mudah kita jalankan saja programnya lalu kita tunggu apakah akan berhenti halting atau malah  jalan terus menerus, tapi berapa lama kita menunggunya? sejam, sehari, semingu, atau bahkan setahun sebelum kita mememutuskan bahwa variabel anu menyebabkan program ini jalan terus menerus

Pertanyaannya adalah

adakah metode umum  yang bisa menganalisa semua program, untuk dapat mengetahui variabel-variabel input apa saja yang menyebabkan program berhenti halting atau jalan treus menerus sampai kiamat ?

Pertanyan diatas disebut halting problem. Menurut Allan Turing, sang penemu komputer  hal tersebut adalah mustahil.

Apa itu omega?

Misalkan kita punya suatu program komputer yang akan berhenti jika menghsilkan output dalam biner 11001 dan 101. maka peluang/probabilitas program tersebut menghasilkan 2 ouput tadi adalah , itu baru peluang dari satu program untuk berhenti bagaimana kalau kita menghimpun semua program yang ada lalu hitung berapa peluang total kesemua program akan berhenti

Jadi omega Ω adalah jumlah total  peluang output yang menghentikan  program bisa kita tulis

dimana adalah output dalam biner yang menyebabkan program berhenti, $  panjang biner dari dan adalah himpunan dari .

Bisa kita lihat omega Ω terdefinisi dengan baik, sempuna secara matematika. tapi berapakah nilai omega Ω. tidak ada yang bisa menghitungnya karena halting problem itu tadi Tapi Jika suatu saat halting problem terpecahkan (memang, telah dibuktikan bahwa halting problem mustahil dipecahkan, tapi sapa tau di masa depan ada yang bisa memecahkannya) maka kita akan bisa menghitung nilai pendekatan approximation dari omega Ω. Tapi yang jelas karena omega Ω itu nilai dari probabilitas maka nilainya antara nol dan satu

Note

omega Ω juga disebut konstanta Chaitin