了解计算模型的好资源吗？

Question

出于好奇，我试图确定我所使用的系统在功能上等效于哪种计算模型，并证明其等效性。我在这个问题上花费的时间越长，我就越怀疑该系统不是图灵等价的。我对图灵机和递归可枚举语言的理解很好，但我对功能较少的自动机了解不多（例如下推自动机），所以我不知道如何继续。

首先，有人可以推荐一个学习不同计算模型的好资源吗？我对语法、语言和自动机以及如何证明它们之间的等价和差异感兴趣。理想情况下，该资源将详细分解每个模型的所有元素并进行比较。

其次，当尝试将系统安装到这些计算模型中时，是否应该使用通用方法或框架？

Answer 1

我会推荐一本关于计算机科学的好教科书（在我的大学课程中，我正在学习 Sipser 的计算理论导论, ，我认为这非常好。您可能还会发现 免费教科书 它的教学内容相同，但我没有任何经验，所以我不能推荐）。

另一种方法可能只是阅读维基百科。如果您知道要查找的内容以及查找的顺序，您实际上可以从维基百科文章中获得很多帮助。此外，如果有任何不清楚的地方，您通常可以谷歌搜索并找到有关该特定主题的更多资源。

当然，这将 不是 与真正的教科书一样好，但它是一个很好的起点 现在, ，而且是免费的。

作为起点，我建议阅读以下主题（按列出的顺序）：

1. 确定性有限自动机
2. 非确定性有限自动机, ，以及它们与 DFA 的等价性。
3. 常规语言, ，以及它们与 DFA 的等价性。
4. 下推自动机
5. 上下文无关语法, ，以及它们与下推自动机的等价物。
6. 乔姆斯基层次结构
7. 图灵机

这应该为人们谈论的大多数计算模型提供一个非常简短的介绍。 2:我会推荐一本关于计算机科学的好教科书（在我的大学课程中，我正在学习 Sipser 的计算理论导论, ，我认为这非常好）。另一种方法可能只是阅读维基百科。如果您知道要查找的内容以及查找的顺序，您实际上可以从维基百科文章中获得很多帮助。此外，如果有任何不清楚的地方，您通常可以谷歌搜索并找到有关该特定主题的更多资源。作为起点，我建议阅读以下主题（按列出的顺序）：1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Answer 2

从以下链接的视频讲座给人很好的介绍，计算理论。这是关于此主题的最好的资源中的一个。

视频讲座由晒西蒙森教授计算理论

Answer 3

霍普克罗夫特和乌尔曼的《自动机理论、语言和计算导论》是一本可能很难找到的较旧的文本。有很多版本——我听说 '79 是最好的，因为它在介绍复杂的东西方面最省力。这是一本合法的教科书，虽然很小，但它介绍了整个领域，而不仅仅是您正在寻找的内容。我建议这样做可能是徒劳的希望，也许其他来源遗漏的那些“更棘手”的证据之一可能是你的钥匙。

作为一个更温和的起点，有一些方便的“基准”语言。

• 如果你的型号 能 识别所有字符串中具有相同数量的 A 和 B 的字符串的语言，那么它至少比 FSM 更强大。
• 如果不能的话那就 可能 相当于FSM。
• 同样，如果你的模型 能 识别所有字符串的语言，其中字符串中的 As、B 和 C 的数量相同，那么它是 更多的 比 CFG 或 PDA 更强大。

这些“基准语言”实际上只是变相的函数——第一个基本上是询问 2 个一元数是否相等，第二个是询问 3 个一元数是否相等。它们很好、很简单，并且众所周知，它们的功能高于或低于特定模型的功能。我不知道更复杂的机器的简单方法，所以你可能要靠自己了。

请注意，对于模型“LBA”（线性有界自动机），我相信没有已知的自然语言可以用 TM 计算，但不能用 LBA 计算。这个说法是根据模糊的记忆得出的，所以不要把它当作正式的证明。:)

请注意（最后）“基准”语言并没有建立平等。也就是说，如果你的模型无法比较 2 个一元数，那就是 不是 这意味着它必然相当于 FSM，但它可能更弱。语言只能确定什么是大于权力，什么是小于权力。

在完全（完全）不同的轨道上，西普瑟的书确实证明了 等价 正则表达式和 FSM 之间，以及 PDA 和 CFG 之间。我不确定这会有多大帮助，因为您对正在考虑的计算模型相当模糊，但如果您对等价性一心一意，那么这些可能是很好的起点。