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 ${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$, onde

• ${\displaystyle Q}$ é um conjunto finito de estados
• ${\displaystyle \Sigma }$ é um conjunto finito de símbolos chamado alfabeto da fita
• ${\displaystyle \Gamma \in Q}$
• ${\displaystyle q_{0}\in Q}$ é o estado inicial
• ${\displaystyle F\subseteq Q}$ éo conjunto de estados de aceitação.
• ${\displaystyle \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.
• ${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$

onde ${\displaystyle 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= ${\displaystyle \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 ${\displaystyle \subseteq }$ M' e M' ${\displaystyle \subseteq }$ M.

• ${\displaystyle M\subseteq M'}$

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

• ${\displaystyle 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= ${\displaystyle \langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$ com a função de transição ${\displaystyle \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