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 fontes no fim do texto, mas que não são citadas 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 , onde

  • é um conjunto finito de estados
  • é um conjunto finito de símbolos chamado alfabeto da fita
  • é o estado inicial
  • éo conjunto de estados de aceitação.
  • é a relação entre estados e símbolos chamados função de transição.

onde

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= 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 M' e M' M.

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

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= com a função de transição

Essa máquina também aceita L.

Bibliografia[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