如何枚举所有图灵机？

Question

为什么这真：“那里是多么多的图灵机“

在这个问题的顶部答案中，给出了如何枚举所有图灵机的描述。

这一切都很清楚，除了一个部分：你如何知道字符串是图灵机的有效编码吗？在步骤3中，算法需要检查字符串是否是图灵机的有效编码。这是如何完成的？

Answer 1

图定机器具有作为串的表示。更具体地说，您写入转换函数。为此，只需将其视为一个大型桌子，在每一行两个状态都是一个字母，头部过渡（L为左或右）。

现在，编码过渡功能表的每个条目，以及3个零（它喜欢“魔术号”，所以我们会知道条目开始和结束的位置）。每个条目都包含两个数字 - 表示一个状态的每个数字，字母的另一个位和头部转换的另一个位（例如，1将是R和0是l）。

在两个数字和其他位之间放2个零，就这样你就可以区分它们。

现在，要枚举所有图定机器，只会枚举所有字符串并检查它们是否以上述格式