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

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

Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę stanów?
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?

— Student
źródło

Innym interesującym pov wrt jest to, że UTM może być zbudowany ze stałą liczbą stanów. symuluje inne bazy TM z dowolną liczbą stanów lub symboli zakodowanych na taśmie.

— vzn

pokrewnym pytaniem jest, w jaki sposób TM może symulować bankomat (naprzemiennie TM), który jest mniej więcej tą samą metodą pf kodującą dodatkowe adata na taśmie plus redukcję stanów do klas

— Nikos M.

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 i przesuń kieruj się w kierunku . ” 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 i $2^q$ $2^\ell$ symboli taśmowych. Przechowuj funkcję przejścia jako binarne drzewo głębokości gdzie na pierwszych poziomach 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.

— David Richerby
źródło