Máquina de Turing multifita

Máquina de Turing
Máquina
Máquina de Turing universal Máquina de Turing alternada Máquina de Turing quântica Máquina de Turing não determinística Máquina de Turing somente de leitura Máquina de Turing movimentação à direita Máquina de Turing probabilística Máquina de Turing multifita Máquina de Turing de Várias Faixas Máquinas de Turing equivalentes Exemplos de Máquinas de Turing
Ciência
Alan Turing Categoria:Máquina de Turing

Uma máquina de Turing multifita é uma máquina de Turing comum com várias fitas. Inicialmente a entrada aparece na fita 1 e todas as outras vazias, como cada fita tem sua própria cabeça para ler e escrever, a função de transição pode ler, escrever e mover as cabeças em algumas ou todas as fitas simultaneamente.

Definição formal

Uma máquina de Turing com k fitas também pode ser descrita como uma 7-upla $M=(Q,\Sigma ,\Gamma ^{1},\Gamma ^{2},...,\Gamma ^{k},s,b,F,\delta )$, onde

• $Q$ é um conjunto finito de estados
• $\Sigma$ é um alfabeto finito de símbolos
• $\Gamma ^{i},i=1,...,k$ é o alfabeto da fita $i$ (conjunto finito de símbolos)
• $k$ é o número de fitas
• $s\in Q$ é o estado inicial
• $b\in \Gamma$ é o símbolo branco
• $F\subseteq Q$ é o conjunto dos estados finais
• $\delta :Q\times \Gamma ^{k}$ ⇒ $Q\times \Gamma ^{k}\times \{\leftarrow ,\rightarrow ,P\}^{k}$ é uma função parcial chamada função de transição, onde $\leftarrow$ é o movimento para a esquerda, $\rightarrow$ é o movimento para a direita e k é qual fita está sendo referenciada.

A expressão $\delta$ = (q_i, a₁, ..., a_k) = (q_j, b₁, ..., b_k, E, D, ..., E) significa que, se a máquina está no estado q_i e as cabeças 1 a k estão lendo símbolos a₁ a a_k, a máquina vai para o estado q_j, escreve os símbolos b₁ a b_k e direciona cada cabeça para mover para a esquerda ou direita, ou permanecer parada, conforme especificado.

Máquinas de Turing multifita parecem ser mais poderosas que as MTs comuns, mas podemos mostrar que elas são equivalentes em poder. Duas máquinas são equivalentes se elas reconhecem a mesma linguagem.

Equivalência entre uma máquina multifita e uma de fita simples

Seja M uma MT multifita e S uma MT equivalente de fita única. A ideia da prova é mostrar como simular M com S. Digamos que M tenha k fitas. Então S simula o efeito de k fitas armazenando sua informação na sua única fita. Ela usa o novo símbolo # como um delimitador para separar o conteúdo das diferentes fitas. Além do conteúdo dessas fitas, S tem que manter registro das posições das cabeças. Ela faz isso escrevendo um símbolo de fita com um ponto acima dele para marcar o local onde a cabeça estaria naquela fita.

S = "Sobre a entrada w = w₁ ... w_n:

1. Primeiro S põe sua fita no formato que representa todas as k fitas de M. A fita formada contém

#w*₁w₂ ... w_n#*#*# ... #

1. Para simular um único movimento, S faz uma varredura na sua fita desde o primeiro #, que marca a extremidade esquerda, até o (k 1)-ésimo #, que marca a extremidade direita, de modo a determinar os símbolos sob as cabeças virtuais. Então, S faz uma segunda passagem para atualizar as fitas conforme a maneira pela qual a função de transição de M estabelece.
2. Se em algum ponto S move uma das cabeças virtuais sobre um #, essa ação significa que M moveu a cabeça correspondente para a parte previamente não lida em branco daquela fita. Portanto, S escreve um símbolo em branco nessa célula da fita e desloca o conteúdo da fita, a partir dessa célula até o # mais à direita, uma posição para a direita. Então ela continua a simulação tal qual anteriormente."

Bibliografias

• Michael Sipser. Introdução à Teoria da Computação. Tradução brasileira de "Introduction to the Theory of Computation" (PWS Publishing Company, 2nd edition, 2005), por Ruy de Queiroz, revisão Newton Vieira, Cengarle Learning, 2007 ISBN 978-85-221-0499-4.