Bagaimana mesin Turing universal mensimulasikan yang "lebih besar"?

Saya mencoba menemukan jawaban dari dua pertanyaan tentang mesin Universal Turing.

1. Bagaimana mesin Universal Turing dapat mensimulasikan mesin Turing jika mesin yang disimulasikan memiliki jumlah status yang lebih besar?
2. Bagaimana mesin Universal Turing dapat mensimulasikan mesin Turing jika mesin yang disimulasikan memiliki jumlah karakter alfabet yang lebih besar?

Adakah yang bisa membantu saya dengan pertanyaan-pertanyaan ini?

Jawaban untuk kedua pertanyaan ini adalah sama: dengan menggunakan rekaman itu untuk menyimpan data yang diperlukan. Kita dapat mengasumsikan bahwa set negara dan alfabet mesin yang akan disimulasikan adalah himpunan bagian dari bilangan alami ("Negara 1", "Negara 2", "Negara 3", dll.). Bahkan dengan hanya dua karakter non-kosong, mesin universal dapat mewakili semua bilangan bulat tersebut sebagai string biner.

Perhatikan, meskipun, bahwa mesin universal memiliki jumlah tetap negara, yang membuat komputasi fungsi transisi sedikit rumit. Apa yang ingin kita lakukan adalah menulis beberapa instruksi yang mengimplementasikan pernyataan saklar besar dari formulir, "Jika negara adalah  dan karakter di bawah kepala adalah  , kemudian pindah ke negara  , tulis karakter  dan pindahkan menuju ke arah  . " Jadi - dan saya pikir ini mungkin menjadi akar dari pertanyaan Anda - bagaimana kita menghitung fungsi transisi jika kita bahkan tidak memiliki cukup status di mesin universal untuk menyimpan input fungsi transisi?$s$$x$$s'$$x'$$d$

Salah satu caranya adalah menyimpan fungsi transisi sebagai pohon biner. Misalkan semua mesin simulasi memiliki  state dan  simbol kaset. Menyimpan fungsi transisi sebagai pohon biner dari kedalaman di mana, pada saat pertama  tingkat, Anda pergi kiri atau kanan menurut apakah bit berikutnya dari negara simulasi adalah satu atau nol dan berikutnya  tingkat adalah sama tetapi untuk bit berturut-turut dari karakter rekaman simulasi. Sekarang, mesin universal Anda dapat berjalan mundur dan maju pada rekamannya, memeriksa bit negara / karakter berikutnya, mengingat bit itu dalam keadaannya sendiri, bergerak kembali ke pohon, meletakkan penanda di simpul yang benar, dan seterusnya.$2^q$$2^\ell$$q+\ell$$q$$\ell$

Ini menjadi sedikit lebih mudah jika Anda membiarkan mesin universal Anda memiliki beberapa kaset tetapi kemudian Anda masih harus menunjukkan bahwa mesin multitape Anda setara dengan mesin kaset tunggal.