Quelle est la représentation arbitraire d'une machine de Turing?

Question

Je travaille sur un problème connexe de décidabilité/reconnaissable, et pour le résoudre, j'ai besoin de clarifications sur l'encodage/la représentation d'une machine à turing.

Je sais qu'une machine à écrire est formellement définie comme un 7-tuple. Si j'ai une machine de Turing U et une autre machine de Turing M, est-il trivial de concevoir U pour reconnaître une partie de M (comme l'alphabet de M, les symboles d'entrée, l'ensemble des états d'acceptation, etc.)? Une partie de moi pense que parce que ce sont des ensembles finis, il est trivial de les compter, mais une partie de moi se demande si vous pouvez ou non énumérer une partie de la définition de M sans avoir la possibilité de boucler à l'infini.

Answer 1

Oui, le U représente la machine Universal Turing. Lisez à ce sujet au http://en.wikipedia.org/wiki/Turing_machine#Universal_Turing_machines.