Como uma máquina universal de Turing simula as "maiores"?

Estou tentando encontrar as respostas de duas perguntas sobre a máquina Universal Turing.

1. Como a máquina Universal de Turing pode simular uma máquina de Turing se a que está sendo simulada possui um número maior de estados?
2. Como a máquina Universal Turing pode simular uma máquina de Turing se a que está sendo simulada possui um número maior de caracteres do alfabeto?

Alguém pode me ajudar com essas perguntas?

A resposta para ambas as subquestões é a mesma: usando a fita para armazenar os dados necessários. Podemos assumir que o conjunto de estados e o alfabeto da máquina a ser simulada são subconjuntos dos números naturais ("Estado 1", "Estado 2", "Estado 3" etc.). Mesmo com apenas dois caracteres não em branco, a máquina universal pode representar todos esses números inteiros como cadeias binárias.

Note, no entanto, que a máquina universal possui um número fixo de estados, o que torna um pouco complicado a função de transição da computação. O que gostaríamos de fazer é escrever algumas instruções que implementem uma grande declaração de opção do formulário: "Se o estado for  e o caractere embaixo da cabeça for  , vá para o estado  , escreva o caractere  e mova o siga na direção  . " Então - e acho que essa pode ser a raiz da sua pergunta - como calculamos a função de transição se nem temos estados suficientes na máquina universal para armazenar a entrada da função de transição?$s$$x$$s'$$x'$$d$

Uma maneira é armazenar a função de transição como uma árvore binária. Suponha que toda a máquina simulada tenha  estados e  símbolos de fita. Armazene a função de transição como uma árvore binária de profundidade onde, nos primeiros  níveis, você vai para a esquerda ou para a direita, dependendo se o próximo bit do estado simulado é um ou um zero e os próximos  níveis de são os mesmo para os bits sucessivos do caractere de fita simulado. Agora, sua máquina universal pode andar para trás e para frente em sua fita, verificando o próximo bit do estado / caractere, lembrando-se desse bit em seus próprios estados, voltando para a árvore, colocando um marcador no nó correto e assim por diante.$2^q$$2^\ell$$q+\ell$$q$$\ell$

Isso fica um pouco mais fácil se você deixar sua máquina universal ter várias fitas, mas ainda assim precisar mostrar que sua máquina de várias fitas é equivalente a uma única máquina de fita.