Satz Anzahl der Konfigurationen eines LBTM

Einfache Sprache

Def. Satz Anzahl der Konfigurationen eines LBTM

Sei $M$ eine LBTM mit $q$ Zuständen, und $g$ Bandsymbolen. Dann hat $M$ für eine Eingabe der Länge $N$ genau $qng^n$ verschiedene Konfigurationen.

Beweis: Bemerke, dass eine Konfiguration einer TM wie eine Momentaufnahme einer Berechnung ist. Diese Momentaufnahme besteht also aus dem Zustand, indem die TM ist, der Position, wo sich der Lese-Schreibkopf befindet, und der Inhalt des Bandes, hier Linear beschränkt. In unserem konkreten Fall kann $M$ in $q$ verschiedenen Zuständen sein. Das Band ist $n$ lang, kann also in $n$ verschiedenen Positionen sein. Auf dem $n$ langen Band können $g^n$ verschiedene Zeichenketten (Zeichenkette) von Bandsymbolen sein. Das Produkt dieser drei ergibt dann die Anzahl an verschiedenen Konfigurationen einer TM $M$ mit einer Bandlänge $n$.