Modulare Maschine

Beschreibung

Eine Modulare Maschine ist eine Numerischere Form der Turingmaschine. Es kann als eine Verallgemeinerung betrachtet werden, da sich jede Turingmaschine in eine Modulare Maschine umwandeln lässt.

Definition

Eine Modulare Maschine $M$ besteht aus

• einer Größe $m\in \mathbb{N}$
• einer Alphabet-Größe $n<m$
• Einer Menge von Übergängen der Form $(a,b,c,D)$ Die Komponenten stehen für:
  • Aktueller Zustand/Zeichen auf Band $a,b<m$
  • Nächster Zustand/Zeichen auf Band $c<m^2$
  • Bewegrichtung des Bandes $D\in \{L,R\}$

Die Übergänge sollen determiniert sein, d.h. für jedes $a,b$ gibt es nur einen resultierenden Übergang.

Konfiguration

Wie bei einer Turingmaschine, bewegt sich eine Modulare Maschine durch Zustandsübergänge zwischen Konfiguration. Eine Konfiguration ist charakterisiert als ein 2-Tupel $(\alpha ,\beta )=(um+a,vm+b)$ wobei:

• $u={\sum }_0^k{a}_j{m}^j$ die linke Seite des aktuellen Bandes ist, geschrieben als $m$-äre Zahl
• $v={\sum }_0^k{b}_j{m}^j$ die rechte Seite des aktuellen Bandes ist, geschrieben als $m$-äre Zahl
• $a,b$ das aktuelle Bandzeichen und Zustand (anhand der Größe kann man die beiden auseinanderhalten. Zeichen sind $<n$)

Terminale Konfiguration

Gibt es keinen Übergang, der eine bestimmte Konfiguration $(\alpha ,\beta )$ einen einen neuen Zustand bringt, so nennt man die Konfiguration terminal

Komputationsfunktion

Wir definieren für eine Modulare Maschine $M$ eine Komputationsfunktion $g_M:{\mathbb{N}}^2\to {\mathbb{N}}^2$. Diese nimmt eine Konfiguration $(\alpha ,\beta )$ entgegen. Dann wird so oft ein Statusübergang auf die Konfiguration angewendet, bis man bei einer Terminales Konfiguration ankommt. Diese wird dann ausgegeben.

Eigenschaften

Jede Turingmaschine kann einfach in eine Modulare Maschine umgewandelt werden.

\newcommand{\R}{\mathbb R}