Bir Turing makinesi, 1936'da Alan Turing tarafından önerilen teorik bir hesaplama modelidir. Hesaplamalar yapmasına izin veren birkaç bileşenden oluşur.Bir Turing makinesinin ana parçaları şunlardır:
Kaset: Bant, her biri sonlu bir alfabeden bir sembol alabilen sonsuz bir hücre dizisidir.Her iki yönde de sonsuzca uzanır.Teyp, hesaplama sırasında veriler için birincil depolama görevi görür.
KAFA: Kafa, bant üzerindeki sembolleri tarayan bir okuma/yazma mekanizmasıdır.Geçerli konumdaki sembolü okuyabilir, yeni bir sembol yazabilir ve bant boyunca sola veya sağa hareket edebilir.
Sonlu Durum Kontrolü: Bu bileşen, Turing makinesinin beyni gibi davranır.Mevcut duruma ve kafa tarafından taranan sembole göre makinenin davranışını belirler.Sonlu durum kontrolü, durumlar arasında geçiş yapmaktan ve bandı güncellemekten sorumludur.
Devlet Kaydı: Durum kaydı, Turing makinesinin mevcut durumunu tutar.Makinenin davranışı hem mevcut duruma hem de taranan sembole bağlıdır.
Alfabe: Alfabe, Turing makinesinin okuyup teybe yazabileceği sonlu bir semboller kümesidir.Tipik olarak hem giriş sembollerini hem de kontrol amacıyla kullanılan özel sembolleri içerir.
