Mehrband-Turingmaschine

Eine Mehrband-Turingmaschine (englisch Multitape Turing machine) ist eine abstrakte Maschine in der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine. Die Mehrband-Turingmaschine verfügt über mehrere Speicherbänder, die jeweils einen eigenen Lese- und Schreibkopf besitzen, wobei diese Lese- und Schreibköpfe unabhängig voneinander bewegt werden können (ein wesentlicher Unterschied zur Mehrspuren-Turingmaschine). Ansonsten verhält sich eine Mehrband-Turingmaschine genau so wie eine klassische Turingmaschine. Eine Mehrband-Turingmaschine mit nur einem Band entspricht genau der klassischen Turingmaschine und jede Mehrband-Turingmaschine kann durch eine klassische Turingmaschine (mit nur einem Band) simuliert werden. Die beiden Maschinenmodelle sind also bezüglich der Berechenbarkeit von Funktionen äquivalent, d. h., beide Modelle können die gleichen Funktionen berechnen. Die Mehrband-Turingmaschine arbeitet im Allgemeinen effizienter als eine Einband-Maschine, aber nicht entscheidend im Sinne der wichtigsten Fragen der Komplexitätstheorie, d. h., vor allem für die Frage, welche Probleme in Polynomialzeit gelöst werden können: Eine Mehrband-Maschine, die ein Problem in Polynomialzeit löst, kann von einer Einband-Maschine in Polynomialzeit simuliert werden, wobei aber im Allgemeinen der Grad des die Laufzeit beschränkenden Polynoms höher ist.