问题标签 [turing-machines]

你能给我两种不同的语法来输出相同的单词集吗？

插图：

给定字母表 {0,1} 上的语法 A 和 B，如果语法 A 可以产生单词 0101001，那么语法 B 也可以。如果语法 B 可以产生 0101111，那么语法 A 也可以。如果语法 A 不能产生 01001 那么 B 也不能。

但这里的问题是语法 A 和 B 彼此不同，即它们使用完全不同的算法。那么他们产生的输出集合不仅仅是另一个输出的适当子集。意思是说它们对应的一组输出必须具有相同的基数。可能它们具有不同的复杂性等级，但这没关系。如果可以的话，如果您能给我提供字母 {0,1} 上的语法，就像经典的图灵机一样，我将不胜感激。

对于外行来说，Brainfuck是一种图灵完备的语言，只有 8 个命令，所有这些命令在 C 中都有文字等价物：

在任何有包管理器的 Linux 发行版上，你应该能够找到并安装包beef，一个 Brainfuck 解释器，这样你就可以在家里玩了。

正如您在上面看到的，Brainfuck 只有一个控制结构，[…]将 C 转换为：

这使您可以IF VAR = 0 THEN GOTO 10从 BASIC 进行所有控制。以下将调用getchar()，直到它返回0：

但是，如果我只想阅读换行符\n怎么办？在将我的大脑包裹在如何将其调整为简单的工作之后遇到了一些困难之后，if我想出了以下几点：

（如果有人有更好的方法，请告诉我）

现在可以说我想测试\r除了\n. 鉴于我只有一次机会跳出循环，我该如何测试呢？我的目标是能够模拟switch，嵌套if的 s 或if/else ifs。

如果你把原来的图灵机定义如下：

...以无限磁带的形式获得无限的记忆容量，标记成正方形，每个正方形上都可以打印一个符号。任何时候机器里都有一个符号；它被称为扫描符号。机器可以更改扫描的符号，其行为部分由该符号决定，但磁带上其他地方的符号不会影响机器的行为。然而，磁带可以在机器中来回移动，这是机器的基本操作之一。因此，磁带上的任何符号最终都可能有一个局。（图灵 1948 年，第 61 页）

如果您想将这些操作映射到能够解释汇编程序/二进制指令的处理器上完成的操作 - 哪些操作将被映射？

（我知道这个问题固有的从图灵机到冯诺依曼机的跳跃）

我对什么是图灵机和图灵完备的语言了解一些，但为了更好地理解，有人可以举一些不是图灵完备的语言的例子吗？（甚至可能不是图灵的机器？）

因此，如果一种语言满足某些标准，就可以说它是图灵完备的，并且它可以做另一种图灵完备语言可以做的任何事情。

这是否意味着我理论上可以使用 JavaScript 或Brainf_ck实现 Google ？

这些天我一直在研究 NP 问题、计算复杂性和理论。我相信我终于掌握了图灵机的概念，但我有几个疑问。

我可以接受一个非确定性图灵机有几个选项来处理给定的状态和正在读取的符号，并且它总是会选择最好的选项，如维基百科所述

NTM 如何“知道”它应该采取哪些行动？有两种看待它的方式。一是说机器是“最幸运的猜测者”；如果存在这样的转换，它总是选择最终导致接受状态的转换。另一种是想象机器“分支”成许多副本，每个副本都遵循一个可能的转换。DTM 有一个单一的“计算路径”，而 NTM 有一个“计算树”。如果树的任何分支因“接受”条件而停止，我们就说 NTM 接受了输入。

我不能理解的是，既然这是一个假想的机器，我们说它可以在多项式时间内解决 NP 问题有什么好处？我的意思是，我还可以理论化一个在 O(1) 中解决 NP 问题的神奇机器，如果它可能永远不存在，我能从中获得什么？

提前致谢。

我正在尝试理解和实现最简单的图灵机，如果我说得通，我希望得到反馈。

我们有一个无限的磁带（假设有一个名为 T 的数组，其开头的指针为 0）和指令表：

我的理解是三态两符号是最简单的机器。3状态我不明白。2 符号，因为我们使用 0 和 1 进行读/写。

例如：

从第 1 步开始，如果 Read 为 0，则 { Write 1, Move Right) else {Write 0, Move Right) 然后转到第 2 步 - 这不存在会停止程序。

三态是什么意思？这台机器可以作为图灵机吗？我们可以简化更多吗？

为什么数字 pi 的有限前缀的语言可以由 TM 决定，而说任何实数都有一个 TM 决定给定数字的有限前缀是错误的？

我是最后一年的工程专业学生。我和我的朋友们决定我们最后一年的项目是“使用模板元编程模拟图灵机”。

我了解“图灵机”和“模板元编程”是什么，但我的问题是，如果我们设计没有 TMP 的图灵机，为什么模拟会很乏味？如果我们使用 TMP，我们可以获得什么优势，如果我们不使用 TMP 而使用传统方法，我们会错过/获得什么？

关于我们将如何进行的任何建议？

I'm working on a related decidability/recognizable problem, and to solve it, I need clarification about the encoding/representation of a turing machine.

I know a turing machine is formally defined as a 7-tuple. If I have a Turing Machine U and another Turing Machine M, is it trivial to design U to recognize some part of M (such as M's alphabet, input symbols, set of accepting states, etc)?

Part of me thinks that because these are finite sets, it's trivial to count over them, but part of me wonders whether or not you can just enumerate some part of M's definition without the possibility of looping into infinity.