Alan M. Turing war ein englischer Mathematiker, der von 1912 bis 1954 lebte. Er ist im Bereich der Informatik eine Koryphäe, weil er die nach ihm benannte Turing Maschine ersonnen hat. Dabei handelt es sich aber nicht um einen jemals in Produktion gegangenen Apparat, sondern um ein theoretisches Konstrukt.
Die Turing Maschine ist sozusagen das einfachste System, welches einen beliebigen Algorithmus ausführen kann. Sie ist eigentlich nur eine kleine Menge von möglichen Operationen, um eine Eingabe in eine Ausgabe zu verwandeln.
Interessant daran ist, dass die einfachen Operationen der Turing Maschine, wie etwa ein einzelnes Zeichen der Eingabe zu lesen und in Reaktion darauf ein anderes Zeichen zu schreiben, so elementar sind, dass sie in ähnlicher Weise von jedem denkbaren Verfahren umgesetzt werden müssen. Auf dieser Grundlage lassen sich deshalb allgemeine Aussagen über die Komplexität der Berechenbarkeit von Problemen treffen.
Tinyentropy's Blog 