Máquina de Turing de várias faixas

A Máquina de Turing de Várias Faixas é um tipo específico de Máquina de Turing multifita. Na máquina de turing com n-fitas padrão, n cabeçotes se movem independemente ao longo das n fitas. Na máquina de Turing com n-faixas, um cabeçote lê e escreve as faixas simultaneamente. A posição da fita na máquina de Turing com n-faixas contém n símbolos do alfabeto da fita. Isso é equivalente a máquina de Turing padrão e portanto aceita precisamente as linguagens recursivamente enumeráveis.

Definição Formal

A máquina de Turing multi-fita pode ser definido formalmente como uma 6-tupla $M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle$, onde

• $Q$ é um conjunto finito de estados
• $\Sigma$ é um conjunto finito de símbolos chamado alfabeto da fita
• $\Gamma \in Q$
• $q_{0}\in Q$ é o estado inicial
• $F\subseteq Q$ éo conjunto de estados de aceitação.
• $\delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times d\right)$ é a relação entre estados e símbolos chamados função de transição.
• $\delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)$

onde $d\in {L,R}$

Prova de equivalência com uma Máquina de Turing padrão

Aqui está a prova que a máquina de Turing de duas faixas é equivalente a uma máquina de Turing padrão. Isso pode ser generalizado para uma Máquina de Turing de n-faixas. Seja L uma linguagem recursivamente enumerável. Seja M= $\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle$ seja uma máquina de Turing padrão que aceita L. Seja M' a máquina de Turing de duas faixas. Para provar que M=M' devemos mostrar que M $\subseteq$ M' e M' $\subseteq$ M.

• $M\subseteq M'$

Se todas as faixas menos a primeira é ignorada então M e M' são claramente equivalentes.

• $M'\subseteq M$

O alfabeto da fita de uma máquina de Turing de uma fita equivalente a uma máquina de Turing de duas faixas, consiste em um par ordenado. O símbolo de entrada de uma máquina de Turing M' pode ser identificada como um par ordenado [x,y] da máquina de Turing M. A máquina de Turing de uma faixa é:

M= $\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle$ com a função de transição $\delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)$

Essa máquina também aceita L.

Bibliografia

Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN 0-321-32221-5. Chapter 8.6: Multitape Machines: pp 269-271