问题标签 [turing-machines]

请告诉什么是术语“成熟的 KI”？据我了解，它是用于文本分析的数据挖掘的一部分。我对吗？一些有趣和有用的链接会很好！

谢谢！！！

Arthur Dent 使用地球上尚不可用的太空时代技术开发了一种算法，该算法可确定 TM M1 在空白磁带上启动时是否停止。但后来，他发现生命、宇宙和一切的意义是42。

(a) [5] 给定一个 TM M2，证明 Arthur 可以使用他已经开发的程序确定 M2 在输入 42 上是否停止，该程序确定 TM M1 在空白磁带上启动时是否停止。如果您在证明中创建了一个新 TM，请给出其机器模式。

(b) [5] 假设有一个程序比 Arthur 的程序快，但它回答了 TM M2 是否在输入 42 上停止的问题。解释 Arthur 如何使用该算法来确定某个 TM M1 在空白处启动时是否停止胶带。如果您在证明中创建了一个新 TM，请给出其机器模式。

(c) [5] 我们在课堂上证明了确定 TM M 在空白磁带上启动时是否停止的问题是不可判定的。是 (a) 部分还是 (b) 部分可以用来证明确定 TM M 是否在输入 42 上停止也是不可判定的？

任何人都可以帮我破译我的教授在这里所说的内容吗？

我只是在看图灵机模拟器代码并遇到以下语句

“磁带将时间和位置映射到符号。要计算符号，我们必须提前一步查看机器。如果当时磁头在请求的位置，符号已根据表格根据表发生变化，具体取决于相同位置的前一个符号和机器所处的状态。否则，符号没有改变。

斜体部分是什么意思？在这种情况下，请求的位置是什么意思？

图灵机如何实现队列？

这个问题在 NET 考试中被问到。

你能告诉我如何解决这个问题。问题是接受两个长度相同的字符串。

我想以 {turing machine table like q0==> [q0,b,a] } 这种格式回答。

舒巴达

我要求检查只能向右（或停留）移动的图灵机是否等于标准图灵机。

我想将输入复制到另一个不受限制的磁带。但有可能吗？

感谢你。

我找到了一个图灵机等效列表的维基百科文章。但是，它没有说明如何确定给定机器是否与图灵机等效的方法。

需要用图灵机的定义来证明吗？你能举个例子吗？

谢谢。

我碰巧需要一个用于图灵机的算法，它读取一串 0，然后在磁带上写入二进制数。

我意识到在实践中机器实际上不会计算 0，但我对如何做到这一点感到非常困惑。

我想首先我需要标记二进制数以 X 或其他东西开头的位置，然后只为第一个 0 写一个 1，如果最低有效位为 0，则为后面的每个 0 写一个1 但如果是 1 呢？也许把它变成 0 并继续把所有的 1 变成 0 直到我找到一个 0 或空白变成 1？再说一次，在那种情况下，不管LSB如何，都是一样的，因为我会做同样的事情，只有0是第一个位置......

嗯……橡皮鸭……

包含任意数量的磁带符号的图灵机 M 可以由仅包含三个磁带符号的 M' 模拟：{0, 1, B}（B = 空白）。

M 可以用只有两个磁带符号的 M" 来模拟，比如 {1, B}？

正则表达式通常被认为是不完善的语言的经典示例。例如，“正则表达式”作为这个 SO 问题的答案给出，寻找不是图灵完备的语言。

在我对转动完整性概念的理解中，这可能有点基本，这意味着不能使用正则表达式来检查“平衡”的模式。平衡的含义具有与结束字符相同数量的开始字符。这是因为这样做需要你有某种状态，以允许你匹配开始和结束字符。

然而，正则表达式的 .NET 实现引入了平衡组的概念。此构造旨在让您回溯并查看之前的组是否匹配。这意味着 .NET 正则表达式：

可以匹配以下模式：

这是否意味着.NET 的正则表达式是图灵完备的？或者是否还有其他缺少的东西需要语言是图灵完备的？