Como mapear as fitas de uma máquina de Turing de “fita k” na fita única de uma máquina de Turing de “1 fita”

Estou lendo Sipser e acho difícil entender como é o processo. Se você me der k máquinas de Turing com fitas k, posso cuspir uma máquina de Turing equivalente com apenas uma fita. Um exemplo seria bom. Na verdade, um exemplo elaborado que mostra como passar da TM com fitas para uma com 1 fita é o que realmente estou procurando. Não consegui encontrar um até agora. Também não estou procurando nenhuma prova.$k$

Uma resposta descaradamente copiada de mim mesma :

Uma máquina de Turing com várias fitas é basicamente a mesma que uma máquina com uma fita, exceto que temos uma função de transição estendida onde k é o número de fitas. Assim, em cada estado, a função de transição lê o conteúdo de cada fita, passa para um novo estado, (talvez) escreve algo em cada fita e move cada cabeça - como uma TM comum, exceto que agora temos mais coisas para ler, escrever e mexa-se.$Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$$k$

Como sua pergunta sugere, essa máquina pode ser simulada por uma única fita TM. Melhor ainda, isso pode ser feito com apenas desaceleração quadrática (portanto, para classes polinomialmente fechadas, basta falar sobre máquinas de fita única).

A prova disso é um pouco envolvente e está facilmente disponível com uma simples pesquisa na web, então vou esboçar o mapeamento das teclas das fitas em uma única fita.$k$

A idéia básica é bem direta; basta adicionar alguns símbolos novos e acompanhar cada fita e seguir um após o outro. Em cada etapa do cálculo, podemos ter visitado apenas uma quantidade finita de qualquer uma das fitas; portanto, precisamos armazenar apenas tanta informação sobre cada fita. Assim, para cada , adicionamos um novo símbolo γ _ a Γ que indica onde a cabeça (para cada fita) está em qualquer ponto do cálculo. Também apresentamos um caractere separador # a Γ que indicará o início e o fim das fitas "virtuais". Entrada dada ω = ω 1 … ω $\gamma \in \Gamma$$\underline{\gamma}$$\Gamma$$\#$$\Gamma$$\omega = \omega_{1}\ldots\omega_{n}$(podemos supor que, mesmo na máquina de fita múltipla, toda a entrada está na primeira fita - provando o que é um bom exercício) na máquina de fita múltipla, nossa máquina de fita única terá a entrada

$$\underbrace{\#\underline{\omega_{1}}\ldots\omega_{n}\#\underline{\sqcup}\#\underline{\sqcup}\#\ldots\#\underline{\sqcup}\#}_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots$$

$k$

Um exemplo (espero) simples:

$\Sigma=\{0,1\}$$\Gamma=\{0,1,\sqcup\}$$\omega=10101$

$$\begin{array}{lc} \text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$ $\wedge$

Para construir a máquina de fita única combinada, precisamos adicionar novos símbolos ao alfabeto da fita:

1. Precisamos de um símbolo que indique o início e o fim das fitas simuladas
2. $\Gamma$

$\Gamma' =\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\#\}$

$$\#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$ $\wedge$) e as cabeças simuladas das 3 fitas simuladas (os caracteres sublinhados). É claro que a fita se estende infinitamente para a direita, como de costume. Também traí levemente, movendo a cabeça da fita para o primeiro caractere na primeira corda; estritamente, deveria começar na célula mais à esquerda, mas esse é um detalhe técnico trivial.

$\#$

$1$$1$$0$$1$

$1$

$$\begin{array}{lc} \text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$

$0$

$$\begin{array}{lc} \text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$

$\Gamma'$

$$\#1\underset{\wedge}{\underline{0}}101\#1\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$

Após o segundo passo:

$$\#10\underset{\wedge}{\underline{1}}01\#1\underline{\sqcup}\#1\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$

É claro que essa é uma visão de alto nível do processo - não tentei explicar como construir os estados ou como cada fita simulada fica mais longa (para isso, você precisa de uma pequena rotina que verifique se encontrou o final da fita simulada e, em seguida, move tudo para a direita um passo adiante e aperta um novo espaço em branco - ou seja, ele apenas adiciona células de fita simuladas quando são necessárias).