A New Kind of Science - Stephen Wolfram

Geçenlerde Stephen Wolfram'ın (Mathematica'nın yaratıcısı) $25000
ödüllü bir soru koyduğunu duydum web'e (http://www.wolframprize.org).
Bu da beni bir süre önce aldığım ama 1000 sayfa olduğu için
korkudan hiç açmadığım "A New Kind of Science" kitabına bakmaya
ikna etti.

Ana konu her işi yapabilen (hesap anlamında), düşünebileceğiniz
her makineyi simüle edebilen evrensel makinelerin var
oluşu. Fiziksel cisimlerle uğraşmaya alışık dimağlarımız için bu
inanması zor bir durum. Bir makine düşünün, istediğiniz zaman bir
arabayı, istediğiniz zaman bir tornavidayı, istediğiniz zaman bir
telefonu simüle edebiliyor! Bir kere A makinesinin B makinesini
simüle edebilmesi için A'nın daha kompleks bir makine olması gerek
gibi bir sezgimiz var. Eğer bu sezgi doğru olsaydı, evrensel bir
makine mümkün olamazdı, her zaman ondan daha kompleks makineler
tasarlayabilirdik. (Asal sayıların sonsuz olmasının ispatı ile
olan analojiye dikkatinizi çekerim).

Ama Alan Turing 1936'da sanal alemde böyle bir makinenin mümkün
olabileceğini gösterdi. İşin ilginç tarafı Turing'in evrensel
makinesi oldukça basit. Sonsuz bir şerit üzerinde bir daktilonun
kafası gibi ileri geri hareket edebilen yazıcı bir kafa düşünün
(1936'da henüz PC'ler icat olunmamıştı, ama daktilolar vardı). Bu
kafanın yapabildiği tek şey şeritte üzerinde bulunduğu sembolü
okuyabilmek, ve sonlu sayıda kurala göre yeni bir sembol yazıp
sağa ya da sola doğru bir pozisyon hareket edebilmek. Turing bu
makinenin diğer tüm makineleri simüle edebileceğini ispatladı.

Evrensel olan tek makine tabi bu daktilo bozması şey değil, Turing
makineleri sadece evrenselliği ilk ispatlanan (gerçi Godel'in
1931'deki meşhur ispatında da evrensel bir makine gizli olduğu
söylenebilir). "A new kind of science" kitabının üçüncü chapterini
okursanız iyi bir basit makineler listesi ve güzel tarifleri var
(http://www.wolframscience.com/nksonline):

- cellular automata
- mobile automata
- turing machines
- substitution systems
- tag systems
- cyclic tag systems
- register machines
- symbolic systems

Ve tabi bugün kullandığımız tüm bilgisayar dilleri ve CPU'larını
da (sonsuz bir memory ekledikten sonra) bu evrensel makineler
listesine koyabiliriz.

Tüm bu makine çeşitleri içinde belli bir karmaşıklığa ulaştıktan
sonra evrenselliği görmek mümkün - bu evrensel makinelerden
herhangi birisi diğer hepsini simüle edebiliyor. Fakat her Turing
makinesi evrensel değil. Örneğin sadece iki çeşit sembol okuyup
yazabilen, ve sadece iki çeşit kurala göre hareket edebilen Turing
makinelerinin evrensel olamayacağı gösterilmiş. Turing'in orijinal
makinesinde tam kaç sembol ve kaç kural olduğunu bilmiyorum. Ama
1960'larda Marvin Minsky 4 sembol ve 7 kural ile evrensel bir
Turing makinesi yapılabileceğini göstermiş. Uzun zaman basit
Turing makineleri konusu ile kimse uğraşmazken, 1990'larda Wolfram
5 sembol ve 2 kural kullanarak evrensel bir makine
yapılabileceğini göstermiş. Yani bu makinenin kendini içinde
bulabileceği 10 farklı durum var. Bu 10 farklı durum için
bulunduğu pozisyona ne yazacağına ve sağa mı sola mı hareket
edeceğine karar veriyorsunuz, o kadar. Ve bu makine dünyada
yazılmış tüm programları simüle etmek için yeterli! (Sadece
programınızın uygun bir tercümesini makinenin şeridine başta
yazmanız gerek, tabi simülasyonun biraz yavaş olduğunu da akıldan
çıkarmamak lazım).

Ödüllü soru ise Wolfram'ın seçtiği 2 kural ve 3 renkli bir Turing
makinesinin evrenselliğini ispatlamak. Var mı gönüllü?

Related link