Turing Makinesi

1930’larda bir algoritmanın tanımlanıp tanımlanamayacağını ve kanıtlanabilir herhangi bir matematiksel problemi kanıtlamak için kullanılıp kullanılamayacağını belirlemek için tasarlanmış varsayımsal bir makinedir. turing makinesi dört bileşenden oluşuyordu: bir jeton alfabesi, bir sonlu durum makinesi, sonsuz bir bant ve sonlu durum makinesi tarafından üretilen bilgileri banttan okumak ve banda kaydetmek için kullanılan bir okuma-yazma kafası. kasetin sonsuz olmasının tek nedeni, okuma-yazma kafasının her zaman veri ile beslenmesinin yanı sıra yeni veri yazacak alana sahip olmasının beklenmesi idi. turing makinesinin durumunu tanımlamanın birden fazla yolu vardır. bir yaklaşım, belirteç alfabesi tarafından sağlanan beş değerden oluşan bir kümedir: (a) sonlu durum makinesinin durumu, (b) teypten okunan belirteç, (c) teybe yazılan belirteç, (d) okuma-yazma kafasını hareket ettirme talimatı ve (e) sonlu durum makinesinin bir sonraki durumu. bu beş belirteçten oluşan kümeler makinenin programını oluşturur. program makinenin kasetine yerleştirilebildiğinde, buna evrensel turing makinesi denir. daha sonra turing makinesinin, hesaplanabilir herhangi bir fonksiyonu hesaplayabilen maksimum güçlü makineler sınıfının bir örneği olduğu gösterilmiştir. ayrıca bkz. gödel’in ispatı. [alan mathison turing (1912-1954), ingiliz matematikçi]