3

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

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

其次，在尝试将系统拟合到任何这些计算模型时，是否应该使用通用方法或框架？

4

3 回答 3

3

以下链接中的视频讲座很好地介绍了计算理论。这是有关此主题的最佳资源之一。

Shai Simonson教授计算理论视频讲座

于 2010-01-12T08:03:40.910 回答
2

我会推荐一本很好的计算机科学教科书（在我的 Uni 课程中，我正在学习Sipser 的计算理论导论，我认为这非常好。你也可以找到一本免费的教科书，它教同样的内容，但是我没有任何经验，所以我不能推荐）。

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

当然，这不会像一本真正的教科书那么好，但它是现在开始的好地方，而且它是免费的。

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

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

这应该为人们谈论的大多数计算模型提供一个非常简短的介绍。 2：我会推荐一本很好的计算机科学教科书（在我的大学课程中，我正在学习Sipser 的《计算理论导论》，我认为这非常好）。另一种方法可能只是阅读维基百科。如果您知道要查找的内容和顺序，您实际上可以从 Wikipedia 文章中获得大量信息。此外，如果有任何不清楚的地方，您通常可以谷歌搜索并找到有关该特定主题的更多资源。作为一个起点，我建议阅读以下主题（按列出的顺序）： 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

于 2010-01-12T07:58:19.017 回答
1

可能很难找到的旧文本是 Hopcroft 和 Ullman 的“自动机理论、语言和计算简介”。有很多版本——我听说'79 是最好的，因为它在引入复杂的东西时用力最少。这是一本合法的，虽然很小的教科书，它介绍了整个领域，而不仅仅是你正在寻找的东西。我建议这样做可能是徒劳的，希望其他来源遗漏的那些“更棘手”的证据之一可能是你的关键。

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

  • 如果您的模型可以识别字符串中包含相同数量的 As 和 B 的所有字符串的语言，那么它至少比 FSM 更强大。
  • 如果不能，那么它可能相当于FSM。
  • 类似地，如果您的模型可以识别字符串中的 As、Bs 和 Cs 数量相同的所有字符串的语言，那么它比 CFG 或 PDA更强大。

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

请注意，对于模型“LBA”，线性有界自动机，我相信没有已知的自然语言可以用 TM 计算，但不能用 LBA。这句话是从模糊的记忆中提炼出来的，所以不要把它当作正式的证据。:)

请注意（最后）“基准”语言没有建立平等。也就是说，如果您的模型不能比较 2 个一元数，并不意味着它一定等同于 FSM，它可能会更弱。语言只会确定它大于权力或小于权力的东西。

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

于 2010-01-14T05:38:52.863 回答