Turing Makinesi ( The Turing Machine )

Turing makinesi, Karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılmasını sağlayan hesap makinesi Karmaşık hesapların belirli bir düzenek tarafından yapılıp yapılanamayacağı 20yy’ın başlarında büyük bir tartışma konusu olmuştu Öteden beri el ile veya zihinden yapılan hesaplamalar çok zaman almakla birlikte, birçok hatayı da beraberinde getiriyordu Tüm bu tartışmalar sürerken, 1936 yılında, ünlü matematikçi Alan M Turing "Saptama Problemi Hakkında Bir Uygulamayla Birlikte Hesaplanabilir Sayılar" (İngilizce On computable numbers, with an application to the Entscheidungsproblem) isimli bir makalesini yayınladı Makalesinde teorik ve matematiksel temellere dayalı sanal bir makineden bahseden Turing, her türlü matematiksel hesabın bu sanal makineyle yapılabileceğini iddia ediyordu Turing’in 1950 yılında yayınlanan "Hesaplama Mekanizması ve Zeka" (İngilizce Computing Machinery and Intelligence) isimli ikinci makalesi ise, makineler ve zekayla ilgili birçok tartışmalı konuya cevap niteliğindeydi İşte bu makalelerde sözü geçen sanal makine daha sonraları Turing Makinesi (İngilizce The Turing Machine) olarak isimlendirildi

Bu tablo, o Turing makinesinin çalıştırdığı algoritmadır Turing makinesi, her adımda:

• O anda kafanın görmekte olduğu sembolü okur
• Geçiş tablosunda okuduğu sembol ve o anki durumunu içeren bir girdi arar:
• Eğer öyle bir girdi bulursa, yazılacak sembolü yazar veya kafasını hareket ettirir ve yeni duruma geçer Makine, yeni durum ve kafanın okuduğu yeni sembol ile çalışmaya devam edecektir
• Eğer öyle bir girdi bulamaz ise, durur