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.