Eine Turingmaschine, die Primzahlen entscheidet
Turingmaschinen sind ein grundlegendes formales Rechenmodell in der theoretischen Informatik.
Setzt man die Church-Turing-These als wahr voraus, so ist jede „intuitiv“ berechenbare Funktion von einer Turingmaschine berechenbar. Dies macht die Turingmaschinen gleich mächtig wie zum Beispiel die Registermaschinen, welche das theoretische Modell hinter dem normalen PC sind.
Hier sind nun ein paar Dokumente zu einer Turingmaschine, die ich Ende des Jahres 2004 gebaut habe, welche zu einer als Binärzahl übergebenen Eingabe entscheiden kann, ob diese eine Primzahl ist oder nicht.
1. Informelle Beschreibung der TM als Paper
Ein kurzer Artikel über das Problem und die informelle Beschreibung der Funktionsweise der Turingmaschine. Außerdem ist die Gödelnummer angegeben.
Download [136 KiB] (Update: 16 Feb 2005)
2. DIN-A1 Poster des Übergangsgraphen
Dies ist der Übergangsgraph der Turingmaschine, durch den sie quasi definiert wird - als DIN-A1 Poster!
Download [41 KiB] (Update: 16 Feb 2005)
3. Folienpräsentation vom 17.02.2005
Ich habe eine kurze Präsentation über die Turingmaschine in der Informatik III Übung am 17.02.2005 an der Universität Karlsruhe (TH) gehalten. Die Folien dazu kann man sich hier ziehen.
Download [536 KiB] (Update: 17 Feb 2005)
4. TM-Datei für den Simulator
Um die Turingmaschine zu testen habe ich diesen Simulator der unter Linux auf Python Basis läuft benutzt. Die TM-Datei ist downloadbar.
Download [2 KiB] (Update: 16 Feb 2005)