Comment une machine universelle de Turing peut-elle simuler des «plus grandes» machines?

J'essaie de trouver les réponses à deux questions sur la machine Universal Turing.

Comment la machine Universal Turing peut-elle simuler une machine Turing si celle qui est simulée a un plus grand nombre d'états?
Comment la machine Universal Turing peut-elle simuler une machine Turing si celle qui est simulée a un plus grand nombre de caractères alphabétiques?

Quelqu'un peut-il m'aider avec ces questions?

computability turing-machines simulation turing-completeness Étudiant
la source

un autre point de vue intéressant est que l'UTM peut être construit avec un nombre d'états constant. il simule d'autres MT avec un nombre arbitraire d'états ou de symboles codés sur la bande.

vzn

une question connexe est de savoir comment une MT peut simuler un ATM (MT alternatif), qui est à peu près par la même méthode pf encodant des données supplémentaires sur bande plus une réduction des états en classes

Nikos M.

Réponses:

La réponse aux deux sous-questions est la même: en utilisant la bande pour stocker les données nécessaires. On peut supposer que l'ensemble d'états et l'alphabet de la machine à simuler sont des sous-ensembles des nombres naturels ("Etat 1", "Etat 2", "Etat 3", etc.). Même avec seulement deux caractères non vides, la machine universelle peut représenter tous ces entiers sous forme de chaînes binaires.

$s$ $x$ $s'$ $x'$ $d$

$2^q$ $2^\ell$ $q+\ell$ $q$ $\ell$

Cela devient un peu plus facile si vous laissez votre machine universelle avoir plusieurs bandes, mais vous devez toujours montrer que votre machine à bandes multiples équivaut à une seule machine à bande.

David Richerby
la source