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