Máquina de Turing de Várias Faixas

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2012)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

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 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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.

Referências[editar | editar código-fonte]

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