alan turing'in 30'lu yıllarda geliştirdiği fiziksel dünyada varolmayan teorik bir makina. normali iki yöne de sonsuz uzunlukta olduğu varsayılan ve üzerine karakter basılabilen bir şerit, şeriti okuyabilen, şerite yazabilen ve şerit üzerinde sağa sola hareket edebilen bir kafa, bir de belirli sayıda duruma sahip olabilen * karar verici mekanizmadan oluşur. karar verici mekanizma kafanın bir yöne gitmesini, bulunduğu yere bir şey yazmasını veya kendi durumunu değiştirmeyi gerçekleştirebilir. karakterlerden biri boşluk olmalıdır.
daha matematiksel bir tanım için: turing makinası t = (s, i, f, s0) şunlardan oluşur: sonlu bir küme olan s kadar durum, boşluk karakteri b'yi de içeren i alfabesi, s*i uzayından s+i+(sağ,sol) uzayına bir parçalı fonksiyon ve başlangıç durumu s0.
bahsedilen parçalı fonksiyon karar verici mekanizmanın kurallar bütünüdür. s*i uzayından (s3 durumundaysan ve okuduğun karakter a ise, vs) s+i+(sağ,sol) uzayına (s5 durumuna geç, şeride c yaz, kafayı sağa kaydır, vs) tanımlı olması bu demektir. bu şekilde durumlar tanımlandıktan ve başlangıç durumu da belirlendikten sonra makina çalışmaya hazırdır.
turing makinasının bu kadar ünlü olmasının sebebi ise zeka oyunu oynamak gibi bir zevk vermesinden ziyade turing-church teoremi ile ilgilidir. bu ispatlanması mümkün olmayan fakat hiç bir türlü de çürütülemeyen teoriye göre herhangi bir fonksiyon veya algoritma sadece bu turing makinası kullanılarak bir şekilde gerçeklenebilir. sonlu durumlu makinalardan ** üstünlüğü de budur. fsm kullanarak her ne kadar kimi kümeler birbirinden ayrılabiliyorsa da genel bir çözüm mevcut değildir. turing makinaları ise kümeleri ayırd etme özelliğine sahiptir.
daha sonra egzotik kimi turing makinası versiyonları da ortaya atılmamış değildir. çift veya daha çok şeritli, tek şerit üzerinde çok kafalı, kafası bir seferde bir adımdan çok gidebilen gibi kimi başka teorik turing makinaları da düşünülmüştür. fakat turing makinası denilince kastedilen asıl basit turing makinasıdır.
bir bant, okuma/yazma başlığı ve sonlu durum makinesinden oluşan makine. alan turing tarafından tanımlanmıştır. turing, bu teorik makinenin işlem bandının sonsuz uzunlukta olduğunu ve sonlu zamanda çözülemeyecek problemleri bile çözebildiğini varmıştır. bu nedenle günümüz bilgisayarlarından oldukça üstündür, çünkü onlar her zaman sonlu adımlarla işlem görürler.
yok aslında böyle bir şey..sanal olan, aslen var olmayan makina..karekök alacam derken insanın ömrünü tüketen makina..daha 18 19 yaşında bilgisayar meraklısı toy çocukların eline verilen, verildiği zannedilen sanal şey. olur ya eğer bir gün turing makinası ile bir ödev yapmak zorunda kalırsanız önce hazır java appletlerini arayın orada yaptırın ödevi yoksa dediğim gibi karekök almak bile harcar adamı..
