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. 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. Każdą wielotaśmową maszynę Turinga działającą w czasie niezależnie od liczby taśm, można zasymulować za pomocą jednotaśmowej maszyny Turinga w czasie . 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.