W jaki sposób uniwersalna maszyna Turinga może symulować „większe”?

Próbuję znaleźć odpowiedzi na dwa pytania dotyczące uniwersalnej maszyny Turinga.

1. Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę stanów?
2. Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę znaków alfabetu?

Czy ktoś może mi pomóc z tymi pytaniami?

Odpowiedź na oba pytania jest taka sama: używając taśmy do przechowywania niezbędnych danych. Możemy założyć, że zestaw stanów i alfabet symulowanej maszyny to podzbiory liczb naturalnych („stan 1”, „stan 2”, „stan 3” itd.). Nawet przy użyciu tylko dwóch niepustych znaków, maszyna uniwersalna może reprezentować wszystkie te liczby całkowite jako ciągi binarne.

Zauważ jednak, że maszyna uniwersalna ma ustaloną liczbę stanów, co sprawia, że ​​obliczenie funkcji przejścia jest trochę trudne. Chcielibyśmy napisać kilka instrukcji, które implementują dużą instrukcję switch formularza: „Jeśli stan to  a znak pod nagłówkiem to  $s$$x$ , to przejdź do stanu  , napisz znak  x ′ i przesuń kieruj się w kierunku  d . ” Więc - i myślę, że może to być sedno twojego pytania - jak obliczyć funkcję przejścia, jeśli nie mamy nawet wystarczającej liczby stanów w maszynie uniwersalnej do przechowywania danych wejściowych funkcji przejścia?$s'$$x'$$d$

Jednym ze sposobów jest przechowywanie funkcji przejścia jako drzewa binarnego. Załóżmy, że cała symulowana maszyna ma  stany q i 2 $2^q$$2^\ell$  symboli taśmowych. Przechowuj funkcję przejścia jako binarne drzewo głębokości gdzie na pierwszych  poziomach q przesuwasz się w lewo lub w prawo w zależności od tego, czy następny bit symulowanego stanu to jeden czy zero, a kolejne ℓ  poziomy są takie same ale dla kolejnych bitów symulowanej postaci taśmy. Teraz twoja maszyna uniwersalna może chodzić do tyłu i do przodu na taśmie, sprawdzając następny bit stanu / znaku, pamiętając ten bit we własnych stanach, cofając się do drzewa, umieszczając znacznik we właściwym węźle i tak dalej.$q+\ell$$q$$\ell$

To staje się nieco łatwiejsze, jeśli pozwolisz, aby twój komputer uniwersalny miał wiele taśm, ale nadal musisz pokazać, że twój komputer wielościeżkowy jest równoważny z jednym urządzeniem taśmowym.