Turing Makineleri
Turing makinesi, sonlu bir kontrol birimine ve sınırsız bir banda sahip soyut bir aygıttır; algoritma sezgisel kavramını yakalamakta ve hesaplanabilir olanın standart referans modeli olarak hizmet etmektedir.
Tanım
Bir Turing makinesi, sonlu bir durum kümesinden ve iki yönlü sonsuz bir hücre bandından oluşmaktadır; her adımda kafasının altındaki sembolü okur, bir sembol yazar, sola veya sağa hareket eder ve bir geçiş fonksiyonuna göre durum değiştirir; kabul veya reddetme durumuna girdiğinde durmaktadır.
Kapsam
Bu konu, Turing makinelerinin tanımını ve işleyişini, konfigürasyonlarını ve hesaplamalarını, çoklu bantlar ve deterministik olmama (nondeterminism) gibi varyantlar altında modelin sağlamlığını, diğer herhangi bir makineyi simüle edebilen evrensel Turing makinesini ve kendi kendine referans ile karar verilemezlik (undecidability) argümanlarını mümkün kılan makinelerin veri olarak kodlanmasını kapsamaktadır.
Temel sorular
- Basit bir oku-yaz-hareket et aygıtı, algoritma kavramının tamamını nasıl yakalamaktadır?
- Modelin birçok varyantı neden tam olarak aynı fonksiyonları hesaplamaktadır?
- Evrensel bir makine nedir ve varlığı neden önemlidir?
- Makineleri dizeler (strings) olarak kodlamak, kendi davranışları hakkında kanıtları nasıl mümkün kılmaktadır?
Temel kuramlar
- Evrensellik
- Tek bir evrensel Turing makinesi bulunmaktadır ki, herhangi bir makinenin kodlaması ve girdisi verildiğinde, o makinenin hesaplamasını simüle etmektedir; bu durum, programların kendilerinin veri olduğu depolanmış programlı bilgisayarın habercisi olmuştur.
- Modelin Sağlamlığı
- Bantlar, çoklu kafalar, iki boyutlu bantlar veya deterministik olmama (nondeterminism) eklemek, hesaplanabilir fonksiyonlar sınıfını değiştirmemektedir; bu nedenle Turing makinesi, bu tür detaylara duyarsız bir hesaplama kavramını yakalamaktadır.
Klinik önem
Turing makinesi, programlama dillerinin ve bilgisayar mimarilerinin gücünün ölçüldüğü bir ölçüttür ve evrensel makine, tüm modern bilişimin dayandığı genel amaçlı depolanmış programlı bilgisayarın kavramsal atasıdır.
Tarihçe
Turing, makinelerini 1936'da bir sayının hesaplanabilir olmasının ne anlama geldiğini kesinleştirmek ve Hilbert'in karar problemini çözmek amacıyla tanıtmıştır. Depolanmış bir açıklamanın genel bir aygıtı kontrol ettiği evrensel makine fikri, on yıl sonra von Neumann'ın depolanmış programlı bilgisayar tasarımını etkilemiştir.
Öne çıkan isimler
- Alan Turing
- Emil Post
- John von Neumann
İlgili konular
Temel eserler
- turing1937
- sipser2013
Sıkça sorulan sorular
- Turing makinesi gerçek bir bilgisayar mıdır?
- Hayır, o, sınırsız banda sahip olup hız veya bellek maliyetiyle ilgilenmeyen matematiksel bir soyutlamadır. Değeri kavramsaldır: prensipte neyin hesaplanabileceğini tam olarak belirlemektedir ve gerçek bir bilgisayarın yapabileceği herhangi bir görevi, yeterli bant ve zaman verildiğinde bir Turing makinesi de yapabilmektedir.
- Evrensel Turing makinesi neden önemlidir?
- Tek bir sabit makinenin, o makinenin tanımı girdi olarak verildiğinde, başka herhangi bir makinenin davranışını gerçekleştirebileceğini göstermektedir. Bu, yazılımın her görev için yeniden kablolama yapmak yerine tek bir yorumlayıcı aygıta beslenen veri olduğu genel amaçlı programlanabilir bilgisayarın teorik temelidir.