Máquina de Turing Multi-fita
As máquinas de Turing com várias fitas têm várias fitas, sendo que cada fita é acessada com um cabeçote separado. Cada cabeça pode se mover independentemente das outras cabeças. Inicialmente a entrada está na fita 1 e as outras estão em branco. A princípio, a primeira fita é ocupada pela entrada e as demais fitas são mantidas em branco. Em seguida, a máquina lê símbolos consecutivos sob suas cabeças e a TM imprime um símbolo em cada fita e move suas cabeças.
Uma máquina de Turing Multi-tape pode ser formalmente descrita como uma 6 tupla (Q, X, B, δ, q 0 , F) onde -
Q é um conjunto finito de estados
X é o alfabeto da fita
B é o símbolo em branco
δ é uma relação sobre estados e símbolos onde
δ: Q × X k → Q × (X × {Left_shift, Right_shift, No_shift}) k
onde há k número de fitas
q0 é o estado inicial
F é o conjunto de estados finais
Note - Cada máquina de Turing de fita múltipla tem uma máquina de Turing de fita única equivalente.