Wielotaśmowa maszyna Turinga

Wielotaśmowa maszyna Turinga (ang. multitape Turing machine) jest jak zwykła maszyna Turinga z tą różnicą, że ma wiele taśm. Każda taśma ma własną głowicę do zapisu i odczytu danych. Początkowo dane wejściowe zapisane są na taśmie pierwszej, a pozostałe taśmy są puste^[1].

W niektórych publikacjach naukowych wielotaśmowa maszyna Turinga nazywana jest także maszyną Turinga z wieloma ciągami i kursorami, gdzie ciągi to innymi słowy taśmy, natomiast kursory to głowice^[2].

Każdą wielotaśmową maszynę Turinga działającą w czasie ${\displaystyle f(n),}$ niezależnie od liczby taśm, można zasymulować za pomocą jednotaśmowej maszyny Turinga w czasie ${\displaystyle \mathrm {O} (f(n)^{2})}$^[2]. Ponadto żadna z klas złożoności (np. czasu wielomianowego) nie podlega zmianom, a zatem zarówno w modelu jednotaśmowym, jak i wielotaśmowym są one takie same.

Maszyna Turinga z ${\displaystyle k}$-taśmami może być opisana jako ${\displaystyle M_{k}=\langle Q,\Sigma ,\Gamma ,s,b,F,\delta \rangle ,}$ gdzie:

• ${\displaystyle Q}$ – skończony zbiór stanów,
• ${\displaystyle \Sigma }$ – skończony zbiór symboli wejściowych,
• ${\displaystyle \Gamma \supseteq \Sigma }$ – skończony zbiór dopuszczalnych symboli,
• ${\displaystyle s\in Q}$ – stan początkowy,
• ${\displaystyle b\in \Gamma \setminus \Sigma }$ – symbol pusty, który należy do zbioru dopuszczalnych symboli, ale nie może być symbolem wejściowym,
• ${\displaystyle F\subseteq Q}$ – zbiór stanów końcowych,
• ${\displaystyle \delta :Q\times \Gamma ^{k}\to Q\times (\Gamma \times \{L,R,S\})^{k}}$ – funkcja częściowa, zwana funkcją przejść, gdzie ${\displaystyle k}$ jest liczbą taśm, ${\displaystyle L}$ to przesunięcie w lewo, ${\displaystyle R}$ przesunięcie w prawo, a ${\displaystyle S}$ to brak przesunięcia.

Maszyna Turinga z dwoma stosami (ang. two-stack Turing machine) – to deterministyczna maszyna Turinga z taśmą wejściową służącą tylko do odczytu, oraz dwiema taśmami pamięci. Jeżeli na którejkolwiek z taśm pamięci głowica przesuwa się w lewo, to na danej taśmie drukowany jest symbol pusty.

Specjalnym przypadkiem wielotaśmowej maszyny Turinga jest maszyna posiadająca trzy taśmy: roboczą, wejściową i wyjściową. Na taśmie wejściowej umieszczone jest słowo wejściowe tylko do odczytu, bez możliwości zmiany zawartości komórek. Na taśmie wyjściowej w chwili początkowej umieszczone są wyłącznie symbole puste, a w trakcie wykonywania programu w komórkach zapisywane są pewne symbole wynikające z prowadzonych obliczeń^[3].

• maszyna Turinga
• maszyna Turinga z wyrocznią
• niedeterministyczna maszyna Turinga