Mini-Turing-Maschine

Den Beweis für die wohl kleinste universelle Turing-Maschine hat der 20-jährige britische Student Alex Smith aus Birmingham erbracht. Er hat damit einen Wettbewerb gewonnen, der von Wolfram Research und deren Gründer Stephen Wolfram, dem Erfinder des Computeralgebraprogramms Mathematica, ausgelobt wurde. Wolfram, der die bislang kleinste Turing-Maschine mit zwei Zuständen und fünf Farben entwikkelt hat, hat in seinem Buch «A New Kind of Science» dargelegt, dass zwei Zustände und zwei Farben für eine universelle Turing-Maschine zu wenig seien. Er ging aber davon aus, dass bereits eine Farbe mehr ausreichen würde, und suchte dafür den entsprechenden Beweis. Diesen erbrachte Alex Smith mit einer Art Compiler, der Code für eine bekannte universelle Turing-Maschine auf die 2,3-Maschine von Wolfram übersetzte. Er erhält dafür 25’000 Dollar.
Eine universelle Turing-Maschine kann, einem bestimmten Regelsatz und Programm folgen, beliebige Berechnungen durchführen und ist das theoretische Fundament heutiger Computer.