Automaten

• Menge der Zustände, die er annehmen kann endlich ist

• pro Zustand eine eindeutige Möglichkeit

• Eingabe wird am Ende akzeptiert oder nicht

• Zustandsübergänge haben mehrere gleichwertige Möglichkeiten

• Möglichkeiten sind nicht eindeutig

• aklzeptiert sobald mind einer im Endzustand landet

• verfügen über einen Speicher

• Stack (LIFO)

• gelesen wird nur das oberste

• Palindrome oder Klammern(öffnen und schließen)

Die Berechenbarkeitstheorie untersucht auch die Grenzen der Berechenbarkeit und formuliert präzise Aussagen darüber, welche Probleme nicht lösbar sind, selbst wenn es unendlich viel Zeit und Ressourcen gäbe. Ein klassisches Beispiel hierfür ist das Halteproblem, das besagt, dass es im Allgemeinen nicht möglich ist, einen Algorithmus zu schreiben, der entscheidet, ob ein gegebener Algorithmus auf einer gegebenen Eingabe jemals anhalten wird oder nicht.

• Steuerwerk, in dem sich das Programm befindet

• einem unendlich langen Speicherband

• pro Feld genau ein Zeichen aus eine vordefinierten Alphabet + Blank

• einem programmgesteuerten Lese- und Schreibkopf

• der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern kann

Wieso sind Kellerautomaten mächtiger als Automaten

• Kellerautomaten haben ein Gedächtnis

Wieso ist die Turingmaschine mächtiger als ein Automat

• Turingmaschine kann schreiben

Wieso ist die Turingmaschine mächtiger als ein Kellerautomat

• Kellerautomat kann nur das oberste Zeichen aus dem Keller lesen