问题标签 [turing-machines]

“字典”是指具有唯一键的键/值对数组。如果不是，为什么？如果足够长，您可以将键用作输入，将值用作输出，它可以解决任意数量的问题。只要它足够长以容纳所有可能的输入，它就可以“计算”任何东西。只要确定输入将具有一定数量的位，它就不需要是无限的。因此，如果我们同意输入将是 X 位，那么您将只需要一个包含 2^X 项的字典，并且您拥有所有可能的图灵机，它将 X 位作为输入。

对？好吧，我想我不是，但为什么？

如果我们将星巴克的迷你语言菜单系统解释为某种语法或状态机，那么这种语法会是图灵完备的吗？星巴克的订单迷你语言的描述可以在这里找到

我希望能够让学生了解在现代计算机中程序执行过程中究竟发生了什么——例如内存地址、引用、堆栈、堆等的使用。

理想情况下，我希望他们能够玩某种演示，其中运行一个简单的应用程序（例如计算器、基本数据库等）并且可以暂停，并且运行程序的机器的状态在相当低的级别上查看通过“漂亮”的 GUI。

这样的应用程序存在吗？如果没有，任何超级程序员可以就编写这样的软件的可行性提出建议吗？目标受众可能是学习现代 OO 语言（C#，最好是 Java）的一年级 Comp Sci 学生。

编辑：

我以为这已经凉了，但是今天有人发帖了，所以我想我最好更新一下...

我可能应该在这个问题中加入“图灵”和“机器”这两个词。我想人们以为我想调试 Windows 或其他东西，而实际上我只是在考虑 TM。这是一个相当不错的模拟器，尽管按照今天的标准来说并不漂亮。

如果有人知道其他任何人，我会很感激你发布一个链接。谢谢。

下面的语言L是不可判定的吗？

L = {米| M是图灵机描述，存在长度为k的输入x ，使得M在最多k步后停止}

我认为是，但我无法证明。我试图考虑减少停机问题。

我需要对非确定性算法的简单描述。我们可以将非确定性算法与具有并行处理器的计算机进行比较吗？请有人准确地向我解释一下非确定性算法

有没有人有一套用于脑残解释器的元胞自动机规则？我认为它类似于通用图灵机的实现。这些存在于 wolfram 网站上，但我不知道如何为 BF 系统调整它们。

我的《计算机算法的设计与分析》今天已经到了。在第一章中，作者介绍了图灵机。我还有另外两本算法教科书，《算法导论》和《算法设计手册》，但它们都没有谈到图灵机，尽管它们在算法和数据结构方面很有名。

我想了解图灵机和算法/数据结构之间的关系是什么。了解图灵机成为算法专家真的很重要吗？

我认为图灵机的时间复杂度和空间复杂度的定义是相同的，我无法区分它们。

请帮我。谢谢。

对于给定的 n 状态忙碌海狸游戏，忙碌海狸功能是唯一的，还是可能有多个功能具有相同的最高分数？也许这两种方法都没有被证明？

我知道在图灵机中，（不同的）磁带用于输入和输出以及堆栈。在使用图灵机添加 2 个数字的问题中，输入处理许多符号，例如 1,0,B(blank),+。

（这个问题与物理学有关，我在这里问是因为我认为他们可能不知道图灵机及其输入。）

我的疑问是，如果输入是 BBBBB1111+111111BB，那么在磁带中，

1->由北极表示（比如说）。
0->由南极表示（比如说）。
B->以无极性表示。

那么，“+”将如何表示？我认为不会有一些特殊符号的代码（如 ASCII）。由于特殊符号的数量和类型将取决于实现。特殊代码也会使算法更加乏味。

或者

磁带中的输入符号表示是否与上述方法完全不同？如果是，请解释。