Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Bei iner k-spurigen TM, handelt es sich um eine TM, bei der das Band in k Spuren eingeteilt ist.

In jeder Bandzelle stehen k-Zeichen, die der Kopf gleichzeitig lesen kann.

Das Bandalphabet wird also um einen k-dimensionalen Vektor erweitert:


Beispiel: Addition binärer Zahlen: Spur 1 und 2 enthalten zwei binär kodierte Zahlen, das Ergebnis wird auf Spur 3 geschrieben. Überträge werden während der Rechnung im Zustandsraum gespeichert. (3 Phasen!)