问题标签 [turing-machines]

在进行考试复习时，我无法回答 Sipser 的“计算理论导论”一书中的以下问题。不幸的是，书中没有解决这个问题。

解释为什么以下不是合法的图灵机。

M = {

输入是关于变量 x1, ..., xn 的多项式 p

1. 尝试所有可能的 x1, ..., xn 设置为整数值
2. 在所有这些设置上评估 p
3. 如果这些设置中的任何一个评估为 0，则接受；否则拒绝。}

这真让我抓狂！我怀疑这是因为整数集是无限的？这是否超出了字母表的允许大小？

我一直在努力寻找这个理论问题的答案，即使它不是直接的编程问题，我相信它确实相关。

假设一种图灵机不能超过 1000 个方格。此类可识别语言的集合与正常可识别语言的集合之间的关系是什么。

我有一个关于图灵机和停机问题的问题。

假设我们有 Atm = {(M,w)，其中 M 是图灵机，w 是输入}，
HALTtm = {(M,w)，其中 M 是图灵机，输入 w}

我想证明 HALTtm <=m Atm

我尝试了一些方法，但我认为它们远非解决方案。任何人都可以提供一些线索？

我正在为车床设计一个项目，但在概念化这些步骤时遇到了问题。

根据我的理解，我要将数字转换为二进制，但是如何找到二进制数字的立方。

另外，我如何在磁带上写立方体。

到目前为止，我在想我应该创建一个接受 0-9 二进制版本的状态图，但接下来呢？

我试图找到逻辑上的艾伦图灵解释为什么不能有一个程序来检查另一个程序。

我记得我们在计算课程上学过，但现在我找不到解决方案，我需要向工作中的某个人解释。

感谢帮助。

背景

冯-诺依曼架构描述了存储程序计算机，其中指令和数据存储在内存中，机器通过改变其内部状态来工作，即指令对某些数据进行操作并修改数据。所以本质上，系统中维护着状态。

图灵机架构通过操纵磁带上的符号来工作。即存在无限数量的插槽的磁带，并且在任何一个时间点，图灵机都在特定的插槽中。根据在该插槽读取的符号，机器可以更改符号并移动到不同的插槽。所有这些都是确定性的。

问题

1. 这两个模型之间有什么关系吗？冯诺依曼模型是基于图灵模型还是受其启发？

2. 我们可以说图灵模型是冯纽曼模型的超集吗？

3. 函数式编程适合图灵模型吗？如果是这样，怎么做？我认为函数式编程并不适合冯诺依曼模型。

我正在尝试学习与编程语言相关的 Chomsky Hierarchy 的某些方面，但我仍然需要阅读 Dragon Book。

我读过大多数编程语言都可以解析为上下文无关语法（CFG）。就计算能力而言，它等于下推非确定自动机之一。我对吗？

如果是真的，那么一个 CFG 怎么可能持有图灵完备的无限制语法（UG）？我之所以问是因为，即使 CFG 描述了编程语言，它们实际上也用于描述图灵机，因此通过 UG。

我认为这是因为至少有两个不同级别的计算，第一个是 CFG 的解析，侧重于与语言的结构（表示？）相关的语法，而另一个侧重于语义（意义，解释数据本身？）与图灵完备的编程语言的能力有关。同样，这些假设是否正确？

我对神经网络的计算能力很感兴趣。人们普遍认为循环神经网络是图灵完备的。现在我正在寻找一些证明这一点的论文。

到目前为止我发现了什么：

• 图灵可计算性与神经网络，Hava T. Siegelmann 和 Eduardo D. Sontag，1991

  我认为这只是从理论的角度来看很有趣，因为它需要具有无限精确的神经元活动（以某种方式将状态编码为有理数）。

• S. Franklin 和 M. Garzon，神经可计算性

  这需要无限数量的神经元，而且看起来也不太实用。

（请注意，我的另一个问题试图指出这种理论结果与实践之间的问题。）

我主要在寻找一些真正可以执行一些我也可以在实践中模拟和测试的代码的神经网络。当然，在实践中，他们会有某种有限的记忆。

有谁知道这样的事情？

我之前讨论过状态机，有一个问题是它是否可能不会因某些输入而停止。它似乎是状态机的一个重要且经常被提及的属性，但我一生都无法弄清楚该属性的名称是什么。有这样的说法吗？它是“可停止的”、“不是无限循环的”还是其他什么？

我正在开发一个软件来从正则表达式生成一个图灵机。

[ 编辑：为了澄清，OP希望将正则表达式作为输入，并以编程方式生成图灵机来执行相同的任务。OP 正在寻求执行从正则表达式创建 TM 的任务，而不是使用正则表达式。]

首先，我将解释一下我做了什么，然后我的具体问题是什么：

我将正则表达式建模如下：

正则表达式（接口）：下面的类实现了这个接口

简单（即：“aaa”、“bbb”、“abcde”）：这是一个叶类，它没有任何子表达式

ComplexWithoutOr (ie: "a(ab)*","(a(ab) c(b) )*")：这个类包含一个正则表达式列表。

ComplexWithOr (ie: "a(a|b) ","(a((ab) |c(b) ) ")：该类包含一个Or运算，其中包含一个RegularExpression的列表。它表示“a|b " 第一个例子的一部分和第二个例子的 "(ab) |c(b) "。

变量（即：“awcw”，其中 w E {a,b}*）：尚未实现，但想法是将其建模为具有与 Simple 不同的逻辑的叶类。它代表示例的“w”部分。

理解并同意上述模型很重要。如果您有任何问题，请在继续阅读之前发表评论...

在 MT 生成方面，我有不同程度的复杂性：

很简单：这种表达方式已经在起作用了。为每个字母生成一个新状态并向右移动。如果在任何状态下，读取的字母不是预期的，它就会启动一个“回滚电路”，在 MT 磁头处于初始位置时结束，并在非最终状态下停止。

ComplexWithoutOr：我的问题来了。在这里，算法为每个子表达式生成一个 MT 并将它们连接起来。这适用于一些简单的情况，但回滚机制有问题。

这是一个不适用于我的算法的示例：

“(ab) abac”：这是一个 ComplexWithoutOr 表达式，它包含一个 ComplexWithOr 表达式“(ab) ”（在“ab”内有一个 Simple 表达式）和一个 Simple 表达式“abac”

我的算法首先为“ab”生成一个 MT1。这个 MT1 被 MT2 用于“(ab)*”，所以如果 MT1 成功则再次进入 MT1，否则 MT1 回滚，MT2 正确完成。换句话说，MT2 不能失败。

然后，它为“abac”生成一个 MT3。MT2的输出就是MT3的输入。MT3的输出是执行的结果

现在，假设这个输入字符串：“abac”。如您所见，它与正则表达式匹配。因此，让我们看看执行 MT 时会发生什么。

MT1 第一次执行“ab”。MT1 第二次“ac”失败并回滚，将 MT 头置于第三位置“a”。MT2 正确完成并将输入转发到 MT3。MT3 失败，因为 "ac"!="abac"。所以 MT 不识别“abac”。

你明白这个问题吗？你知道有什么解决办法吗？

我是用Java开发的，但是语言不重要，我想讨论一下算法。