问题标签 [turing-machines]

我正在为我的形式语言理论课程学习图灵机，教授建议运行以下算法以详细查看“TM”背后的逻辑，但不起作用，尝试编译时告诉我以下错误。

这是代码：

为什么这个程序不起作用？

我必须使用两带图灵机来决定 w#w。我知道你需要复制最后一部分，即 # 之后的部分到第二个磁带上，然后逐个字符比较，看看这两个部分是否相同。

我的问题是如何将 # 之后的那部分复制到第二个磁带上？

有任何想法吗 ？

w = (a|b)^*

这是维基百科中可判定的定义

在可计算性理论中，一个不可判定的问题由一系列需要特定是/否答案的实例组成，因此没有计算机程序可以在给定任何问题实例作为输入的情况下终止并在有限数量后输出所需的答案的步骤。更正式地说，不可判定问题是语言不是递归集的问题

递归集是递归可枚举集的子集。有一些递归可枚举的语言在递归集合之外。那么为什么递归可枚举语言不是不可判定的呢？

减少很多个，是不对称的。我试图证明这一点，但效果并不好。

给定两种语言 A 和 B ，其中 A 定义为

和B=A_TM，其中 A_TM 不可判定但图灵可识别！

鉴于以下减少：

（请原谅我没有使用 Latex ，我没有使用它的经验）

正如我所看到的，从 A <= B（从 A 到 A_TM）的减少是可能的，并且效果很好。但是，我不明白为什么 B <= A 是不可能的。

你能澄清和解释一下吗？

谢谢罗恩

你如何论证 lambda 演算是图灵完备的（以最简单的方式）？

假设存在图灵机 M1、M2、M3，它们识别的语言分别是 L(M1)、L(M2) 和 L(M3)。以下语言 L = {(M1, M2, M3) : L(M1), L(M2), 和 L(M3) 不相等} 语言是否可判定？递归可枚举？或者两者都不是？

嗨，我对可数性有疑问。为什么有必要找出某些事物是否可数。找到它有没有用？而且，如果某些事情是不可数的，是否意味着没有图灵机可以解决它？

有谁知道讨论使用超图来实现或表示非确定性图灵机的任何论文、文本或其他文档？它们实际上是等价的吗？

例如，我很确定超图能够正确且完整地表示非确定性图灵机的状态转换。但到目前为止，我一直无法在印刷品中找到任何可以验证这一点的东西。在我看来，这似乎是一种如此明显的关系，但是我没有找到现有技术的事实让我觉得我走错了路。（也可能是我发现的内容不足以让我理解它在说什么。）;-)

为什么问：我正在开发一个开源包，它在对等网络中进行分布式数据存储和分布式计算。我正在寻找可能支持所需功能的最原始的数据结构。到目前为止，分布式超图看起来很有希望。我的理由是，如果超图可以支持像非确定性图灵机这样的通用事物，那么它应该能够支持更高级别的图灵完备 DSL。（还有其他原因，“非确定性”部分也可能对我有价值，这与分布式数据和/或计算结果的版本控制有关。不过，尽量避免在这里发表论文。）

部分答案：

• opencog 的人们对超图如何适应不同的计算模型进行了一次引人入胜的讨论。这显然与 HypergraphDB 包的开发有关：http: //markmail.org/message/5oiv3qmoexvo4v5j
• 在 MathOverflow 上，有一个问题讨论超图可以做什么——还没有提到图灵，但我要添加它： https ://mathoverflow.net/questions/13750/what-are-the-applications-of - 超图
• 如果超图可以表示非确定性图灵机，那么我认为具有加权边缘的超图将等效于概率图灵机。 http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

我真的很难理解这两者之间的区别。从我的教科书中，它基本上通过说来描述差异

如果一种语言是图灵可识别语言的补充，则它是共同图灵可识别的。

我想我不明白这个定义的一部分是：当它是图灵可识别语言的补充时，它意味着什么？

您如何确定它是否是另一种语言的补充？

我有一个作业问题，要求我描述一个接受L = {a^n: n is prime}. 我不知道该怎么做。我知道吗？我是否使用as 作为一元数字并计算它们？我可以忽略字符串，只测试 n 的主要部分吗？或者是已知的素数，因此只有那些单元格位置是接受状态，我可以像正常一样读取数据？

我该怎么办？