出于好奇，我试图确定我使用的系统的计算模型在功能上是等价的，并证明了等价性 . 我花在这个问题上的时间越长，我越怀疑系统不是图灵相当的 . 我对图灵机和递归可枚举语言的理解很好，但我不太了解具有较小功能的自动机（例如下推自动机），所以我不知道如何继续 .
首先，任何人都可以推荐一个很好的资源来学习不同的计算模型吗？我对语法，语言和自动机感兴趣，以及如何证明它们之间的等价和差异 . 理想情况下，资源会详细分解每个模型的所有元素并进行比较 .
其次，在尝试将系统安装到任何这些计算模型时，是否应该使用一般方法或框架？
3 回答
以下链接的视频讲座很好地介绍了计算理论 . 这是此主题的最佳资源之一 .
Video Lectures on Theory of Computation by Prof. Shai Simonson
我是在Sipser's Introduction to the Theory of Computation学习的，这在我看来非常好 . 您可能还会找到free textbook教授相同的内容，但我不推荐） .
另一种方法可能只是阅读维基百科 . 如果你知道你在寻找什么以及以什么顺序，你可以从维基百科文章中获得很多里程 . 此外，如果有任何不清楚的地方，您通常可以谷歌它，并找到有关该特定主题的更多资源 .
当然，这将是一本真正的教科书，但它是一个现在开始的好地方，它是免费的 .
作为一个起点，我建议您阅读以下主题（按所列顺序）：
Deterministic Finite Automaton
Nondeterministic Finite Automaton，它们与DFA的等价性 .
Regular Languages，它们与DFA的等价性 .
Pushdown Automata
Context-free Grammars，它们与Pushdown Automata等价 .
Chomsky Hierarchy
Turing Machines
这应该简要介绍人们谈论的大多数计算模型 . 2：我是'd recommend a good textbook on computer science (In my Uni course, I'，我从Sipser's Introduction to the Theory of Computation学习，这在我看来非常好） . 另一种方法可能只是阅读维基百科 . 如果您知道're looking for and in what order. Also, if anything is unclear, you can usually Google it and find more resources about that particular subject. As a starting place, I'd建议阅读以下主题（按所列顺序），您实际上可以从维基百科的文章中获得很多里程：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
可能很难找到的旧文本是Hopcroft和Ullman的“自动机理论，语言和计算简介” . 有很多版本---我听说'79是最好的，因为它引入复杂的东西是最少的 . 它是一本合法的，虽然很小的教科书，它引入了整个领域，而不仅仅是你正在寻找的东西 . 我建议这可能是徒劳的希望，也许其他消息来源遗漏的那些“更棘手”的证据可能是你的关键 .
作为一个更温和的起点，有一些方便的“基准”语言 .
如果你的模型 can 识别字符串中As和B数量相同的所有字符串的语言，那么它至少比FSM更强大 .
如果不能，那么它可能等同于FSM .
同样，如果你的模型 can 识别字符串中As，B和Cs数相同的所有字符串的语言，那么它比CFG或PDA更强大 .
这些“基准语言”实际上只是伪装的功能 - 第一种基本上是询问2个一元数是否相等，第二个是询问3个一元数是否相等 . 它们既美观又简单，众所周知，它们高于或低于特定型号的功能 . 对于更复杂的机器，我不知道简单的机器，所以你可能是独立的 .
请注意，对于模型“LBA”，线性有界自动机，我相信没有已知的自然语言可以用TM计算，但不是LBA . 这个陈述来自朦胧的记忆，所以不要把它当作正式的证据 . :)
注意（最后）"benchmark"语言没有 Build 平等 . 也就是说，如果你的模型不能比较2个一元数，那并不意味着它必然等同于FSM，它甚至可能更弱 . 这些语言只会确定它比权力更大或更低的权力 .
在完全（完全）不同的轨道上，Sipser的书确实在正则表达式和FSM之间以及PDA和CFG之间进行了 equivalence 的证明 . 我正在考虑，但如果你已经等同于对等，那么这些可能是一个很好的起点 .