Turing makinesi
Sonsuz bir kâğıt şeridi ve bir okuma kafası olan matematiksel bir oyuncak; 1936’da bilgisayarların neyi yapamayacağını kanıtlamak için icat edildi.
Modelin dört parçası vardır: hücrelere bölünmüş bir şerit, her seferinde tek bir sembol okuyup yazan bir kafa, sonlu bir durum kümesi ve mevcut durum ile kafanın altındaki sembole göre ne yapılacağını söyleyen bir tablo. Aygıtın tamamı bundan ibaret. Aritmetik yok, yazmaç yok, adresleme yok; yine de başka her hesaplama modelinin hesapladığı her şeyi hesaplar.
Bir tane yapmak hiçbir zaman amaç değildi. Alan Turing’in, hiçbir yordamın başaramayacağı şeyler üzerine akıl yürütebilecek kadar yalın bir “mekanik yordam” tanımına ihtiyacı vardı ve Hilbert’in Entscheidungsproblem’ine verilen yanıt olumsuz çıktı: hiçbir algoritmanın karara bağlayamadığı sorular vardır; rastgele bir programın durup durmayacağı bunlardan biridir. Alonzo Church aynı yıl lambda hesabıyla aynı sonuca vardı ve iki modelin denkliği Church–Turing tezinin içeriğidir.
Evrensel Turing makinesi, şeridinde başka bir makinenin tanımını alıp onu taklit eden makinedir. Bu, onu çalıştırabilecek donanımı kimse yapmadan on yıl önce ortaya konmuş saklı program fikridir. Bir dile Turing-tam demek, böyle bir makineyi simüle edebildiği anlamına gelir; birkaç eklentiyle CSS’in de dahil olduğu, büyük olasılıkla da istemeden girdiğiniz bir kulüp.