![]()
Bilgisayarın matematiksel temellerini Alan Turing atmıştır. Turing, David Hilbert’in öne sürdüğü bütün matematiksel teoremler bir programla üretilebilir varsayımından hareketle bir hesaplama düzeneği geliştirdi. Bu düzeneğe Turing Makinesi (TM) adı verildi. “Makine” kâğıt üzerinde tasarlanmıştı ve basit bir işleyiş mantığı vardı. Teorik olarak sonsuz uzunlukta bir bant (teyp bandı gibi düşünülebilir), bandın üzerinde sağa sola hareket edebilen bir okuma-yazma kafası, bir kontrol merkezi ve bir durum kaydedicisinden oluşuyordu. Girdi ve çıktılar bant üzerine okuma-yazma kafası aracılığıyla kaydedilip buradan okunabiliyor; kontrol merkezi verilen bir talimat listesine göre o an bant üzerinde okunan değeri ve kaydedicinin içinde sakladığı durumu değerlendirerek bant üzerinde bir takım işlemler gerçekleştiriyordu. Üç çeşit işlem vardı: okuma-yazma kafasını sağa ya da sola hareket ettirme, bandın üzerine bir şey yazma ve durma. Durma işlemi matematiksel derinliği olan bir problemle ilişkiliydi. Durma problemi adı verilen bu problem oldukça karmaşıktır. Ve aslında TM de bu problemden doğmuştur.
Veriler bant üzerinde bit bit kayıtlıdır. Her bit bir rakam olarak düşünülebilir. Ancak teorik bir düzlemden söz ettiğimiz için bakış açısına göre bitlerin yorumlanışı da değişebilir. Bu durumda bitler, harfler, özel karakterler veya rakamlar olabilir. Önemli olan programın bitleri nasıl yorumladığıdır. Rakamların nasıl işleneceği konusu da duruma göre değişir. İkilik veya başka sayı sistemleri kullanılabilir. Kontrol merkezi yani program, okuma-yazma kafasından gelen veriyi ve kaydedicinin durumunu değerlendirir. Durum, önceki işlemlere göre şekil aldığı için program belli bir akışı takip edebilir. Örneğin bant üzerindeki veriler …111101111… şeklinde olsun. Programa 1’leri gördüğü sürece sağa doğru ilerlemesi, 0’ı gördüğü anda durumunu değiştirmesi söylenebilir. Durum değiştikten sonra karşılaşılan 1’ler önceki birlerden farklı şekilde değerlendirilecektir. Mesela tümü sıfır yapılabilir. Bu durumda sonuç şöyle olur: …111100000… Bu örnekte bitler birlik sistemde yorumlanmıştır. Birlik sistem, abaküs mantığına benzer. Her sayının karşılığı sayı kadar 1 rakamıdır. Sayılar büyüdüğünde sistem yetersizleşir.
TM’ye basit bir giriş yaptıktan sonra ilk program örneklerine göz atacağız. İşleyişi anlamak için vereceğimiz ilk program örneği birlik sistemde bir sayıya 1 eklemek:
0 A 0 A R
1 A 1 B R
1 B 1 B R
0 B 1 A S
Bir komut beş parçadan oluşur: [Anlık bit] [Anlık durum] [Yeni bit] [Yeni durum] [Hareket]. İlk komut olan 0 A 0 A R üzerinden açıklanırsa, ilk iki birim komutun çalışması için gereken şartlardır. Bunları takip eden üç birim şartın gerçekleşmesi halinde işletilir. Yani komut makineye 0 biti ile A durumunda iken karşılaşırsan biti yine 0 yap, durumunu koru ve bir sağa kay (R) demektedir. Anlaşılan zararsız bir komut bu. Ancak bu kadar basit görünmesine aldanmamak gerekir. Bu komut olmazsa program asla çalışmaz! Bu bir çeşit başla emridir. Komutun sonundaki ifade okuma-yazma kafasının ne yapacağını belirtir. Buna göre kafa ya sağa bir kayar (R), ya sola bir kayar (L) ya da durur (S). Her programın işini bitirdikten sonra güvenli şekilde durması gerekir. Durmayan program bize sonucu asla veremez. Örneğin bir sayının sıfıra bölünmesi teorik olarak bir durma problemi yaratabilir. Programı incelemeye devam etmeden önce bit dizisini gözümüzün önüne şöyle getirelim:
…0000011100000…
Birinci komut 0 gördüğü sürece kafayı sağa doğru kaydırır ve durumu muhafaza eder. 1 ile karşılaşıldığında durum da A olduğu için ikinci komutun şartları sağlanmış olur ve böylece durum B’ye geçip kafa bir sağa kayar. Bundan sonra 0 ile karşılaşıncaya kadar üçüncü komut tekrar edecektir. B durumunda iken 0 ile karşılaşıldığında ise son komut sihirli dokunuşu yaparak bu biti 1’e çevirir yani birlik sistemde gösterilmiş örnek girdimiz olan 3’ü 4 yapar ve yapılacak başka bir iş kalmadığı için de durur. Son görüntü şöyledir:
…00000111100000…
Birlik sistem basit olsa da büyük sayılar kullanmak gerektiğinde 1’lerin sayısının artması işlemleri pratikte yavaşlatır. Tabii TM bilgisayar ortamında simüle edilmek isteniyorsa. İkilik sistemin yorumlanması daha çok komut ve karmaşık bir programlama gerektirir ancak hız açısından çok büyük bir ivme kazandırır. Aslında bazı işlemlerin ikilik sistemde yapılması birlik sistemden daha kolaydır. Örneğin ikilik sistemdeki bir sayıyı iki ile çarpmak için sayının sağına bir sıfır eklemek yeterlidir. Birlik sistemde sıfır bant boyunca birlerin etrafını saran rakamlardı. Birlerin dışında kalıyorlardı. İkilik sistemde ise sıfırlar en az birler kadar önemlidir. Birlik sistemin gösterimindeki sıfırlardan farklı bir roldedirler. Birlik sistem gösteriminde sıfırların yaptığı boşluğu temsil etme görevini burada başka bir karakter yapmalıdır. Örneğin space (boşluk) kelimesini çağrıştırmak üzere s harfi bunun için seçilebilir. Bu durumda ikilik sistemle kodlanmış bir veri bantta şöyle görünebilir:
…sssss101sssss…
İkilik sistemde bir sayıya bir ekleyen program birlik sisteme göre biraz daha karmaşıktır:
s A s A R
1 A 1 B R
1 B 1 B R
0 B 0 B R
s B s C L
0 C 1 A S
1 C 0 D L
1 D 0 D L
0 D 1 A S
s D 1 A S
Programda üç farklı durma komutu tanımlanmıştır. Yani program farklı şekillerde sonlanabilir. İlk üç komut birlik sistemde verilen örnekteki ilk üç komutla aslen aynıdır. Genellikle bu üç komut bütün programlarda bir açılış prosedürüdür.
Örnek olarak verilen programlar da dâhil olmak üzere bu mantıkla yazılabilecek her bir program bir TM’dir ve programın komutlarının örneğin ikilik sisteme çevrilerek yan yana dizilmesiyle elde edilecek bir sayı bu TM’yi temsil eder. Her bir sayının TM karşılığı var mı yok mu bakılmak istenebilir. Böylece çok karmaşık TM’leri rastgele bulabiliriz. Hayat ne güzel! …öyle mi acaba? Yukarıda sözünü ettiğim durma problemi işte tam da bu noktada gündeme gelir ve her şeyi darmadağın eder. Rastgele sayıların TM karşılıklarını incelemek güzel bir düşüncedir. Ancak bazı TM’ler saçma sapan olacaktır. Bazılarında okuma-yazma kafası yerinden oynamayacak, bazıları hareket etse de hemen sebepsizce duracaktır. Bunlar zararsız olanlarıdır. Bazı TM’ler ise asla durmaz. Ve işin kötüsü TM’nin kısır bir döngüye mi girdiğini yoksa o anda Aynştayn’ın görelilik teorisini mi incelediğini asla bilemeyiz. Çünkü bilmemiz için programın tam olarak durması gerekir.
Teorik olarak bir durma ile sonuçlanan her işlem TM ile ifade edilebilir. Bu da demek olur ki, dört işlemden türev-integral hesaplamaya kadar bir algoritma ile ifade edilebilecek her şeyin TM karşılığı mutlaka vardır. Tek bir bant ve tek bir durum kaydedicisi programlamayı zorlaştırıyorsa da modern bir bilgisayarla yapabilip de TM’de gerçekleyemeyeceğiniz hiçbir şey yoktur. TM bilgisayarın işleyiş biçiminin anlaşılması açısından çok önemlidir. Kendi programlarınızı yapmaya başladığınızda bilgisayarın içinde neler olup bittiğini daha iyi anlayabileceksiniz. Bu amaçla hazırladığım TM simülatörünü buradan indirebilirsiniz. (Şifre: euzkan.wordpress.com)