无限字母图灵机

Question

图灵机能够从无限字母中读取和写符号比常规TM更强大（这是唯一的区别，机器仍然具有有限的状态）？

直觉不会告诉我，因为您需要无限数量的状态来区分每个符号。因此，我认为由符号（或过渡的某些子集）引起的某些符号或过渡必须等效。因此，您实际上可以使用常规TM和此类符号或过渡的有界子集模拟此类机器。

我如何对此进行正式证明？

Answer 1

不，这将更加强大。过渡功能将不再是有限的，并且 那 给您带来很多力量。

使用无限字母，您可以从一个符号中的无限集中编码任何输入项（尽管输入集不能比字母集“无限”，例如，字母可能只有无限的无限，因此无数元素像实数之类的集合无法用一个符号表示）。同样用于输出。

因此，您可以使用单个过渡进行两态（一个初始，一个接受）Infinite-Alphabet-TM，该过渡移至接受状态并根据您要计算的功能而更改磁带头下方的符号。此食谱将使您可以计算可以将可以放入与字母一对一的对应的集合之间的任何映射。

因此，为了避免这种退化的机器是所有事物的答案，您需要限制过渡功能可以做什么。一个显而易见的是，要求过渡函数本身是可计算的（毕竟普通TM的过渡函数是可以计算的，因为它们是有限的）。但是，您将尝试使用可计算功能来定义您的可计算功能模型。

Answer 2

以上答案是正确的，但是关于无限字母和可计算性，还有更多的话要说。

在WP中，Turing Machine被描述为$ M =（q， gamma，b， sigma， delta，q_0，q_f）$，其中所有集合都是有限的。因此，过渡函数$$ delta：q / f times gamma rightarrow q times gamma times times {l，r } $$必然是有限的。

在无限字母机器中，我们将用$ sigma^{inf} $替换输入字母$ sigma $，因此tape Alphabet by $ gamma^{inf} $和过渡功能由$ delta^{inf } $服从：

$$ delta^{inf}：q / f times gamma^{inf} rightarrow q times times gamma^{inf} times times {l，r } $$

因此，$ delta^{inf} $必然是无限函数。如说，如果此函数是不可符合的，则以上不是有限表示的。让我们假设我们将保持$ delta^{inf} $（部分）递归。问题是字母是否始终允许。

基本问题是，有限字母的整体呈现（因此我们可以选择递归定义我们的功能），但是无限的字母永远无法完整地呈现。那么什么机制正在产生字母？

考虑这一点的最简单方法是想象有一个有限的“核心”字母，例如$ a = {a，b } $。然后生成语言$ l subset a^*$。假设该字符串 阿巴布 $ in L $。然后定义$ alpha =u003Cabaab> in gamma^{inf} $。因此，无限字母由$ l $连接到一个的$ l $组成 单身的 像$u003Cabaab> $。

最简单的字母基本上是 <1*>, ，通过计算每个符号中垂直笔触的数量来区分任何两个符号的常规语言。这将是有限状态解析器（不过，不是作为有限自动机）来计算的。图灵（Turing）主张有限字母，以避免在TM操作中出现任何非限制操作。但是，值得注意的是，英语字母的26个字母不遵循此计数模式：字母Z不包含26个笔触或点或其他任何内容。因此，具有最通用的计算模式可以使用其他模式，该模式基于递归枚举的（RE）语言$ L $。

不过，这里的问题是，除非明确提供$ l $的定义，否则无法构建$ delta^{inf} $。这部分是因为Re集的等效性是不可决定的，部分是因为我们只有有限的样本可以使用，并且无法从中推断出$ L $。 如果 我们确实有$ l $的定义（因此，$ gamma^{inf} $），则如果$ f $是$ gamma^{inf} $递归的，则$ f $在有限a中是递归的，所以f $是绝对的递归，$ delta^{inf} $可以是递归的。

最后，我们认为$ l $没有两个例子：

示例1. 。 $u003Cn> in gamma^{inf} $ iff $ phi_ {n}（n）$证明是偏差。在这种情况下，字母$ gamma^{inf} $显然不会有有限的描述 - 相反，它会随着时间的流逝而“成长”（并且只能在某些计算限制中完全定义自己）。但是，它是一个无限字母，无论如何都不能立即出现。因此，如果$ f $在$ gamma^{inf} $中是递归的，则f在$ delta_2^0 $中 - 停止集。因此，$ delta^{inf} $不能递归。

示例2. 。一个更几何的示例考虑了类似penrose的样子 瓷砖. 。如果$ s $是n个基因的瓷砖单位，则令符号$ s in gamma^{inf} $如果可以证明可以瓷砖平面。该字母是无限的，因为一个人可以为任何n瓷砖的n瓷砖单元构建。无论飞机本身都无法确定，因此随着发现这样的瓷砖，S组将生长。 $ gamma^{inf} $中可能的$ f $递归，但不是绝对递归的。