问题标签 [turing-machines]

“图灵完备”的表达是什么意思？

你能给出一个简单的解释，而不涉及太多的理论细节吗？

在课堂上，我们学习了停机问题，图灵机，归约等。很多同学说这些都是抽象无用的概念，了解它们没有任何意义（即，一旦课程结束就可以忘记它们）结束并且不会丢失任何东西）。

为什么理论有用？您是否曾经在日常编码中使用它？

您什么时候亲自遇到过该领域的停顿问题？这可能是当同事/老板提出一个违反计算基本限制的解决方案时，或者当你意识到你试图解决的问题实际上是不可能解决的。

我最近一次想到它是在学习类型检查器时。我们班意识到不可能编写一个完美的类型检查器（一个接受所有运行时没有类型错误的程序，并拒绝所有运行时出现类型错误的程序），因为这实际上可以解决停机问题. 另一个是当我们意识到，在同一个类中，在类型检查阶段不可能确定除以零是否会发生，因为在运行时检查一个数字是否为零也是停止问题的一个版本。

什么是图灵机，为什么人们一直提到它？我只需要我的 IBM PC 来进行计算！为什么有人关心这些机器？

我最近在阅读关于人工生命的文章，偶然发现了这样的说法，“康威的生命游戏展示了足够的复杂性，可以被归类为通用机器。” 我对什么是通用机器只有一个粗略的了解，而维基百科只是让我与维基百科一样接近理解。我想知道是否有人可以对这个非常性感的声明有所了解？

对我来说，康威的生命游戏似乎是一种可爱的消遣，具有一些巨大的影响：我无法在它和计算器之间进行跳跃？这甚至是我应该做出的飞跃吗？

在JFLAP中，有一些图灵机转换的快捷方式。只要当前磁带符号不是指示符号，这些快捷方式之一就允许您进行转换。例如，转换 !g,x;R 基本上表示“如果当前磁带符号不是 g，则进行此转换”。

到现在为止还挺好。但我想要的过渡是 !□,~;R 基本上说“只要当前符号不是字符串结尾（空单元格）符号就向右移动”。问题是我不知道如何输入“！□”。

JFLAP在线文档有这样的说法：

第一个快捷方式是存在使用“！”的选项 字符来传达“除此字符之外的任何字符”的含义。例如，关于过渡（！a；x，R），如果头部遇到除“a”之外的任何字符，它将用“x”替换字符并向右移动。要写表达式“！□”，只需在输入命令时输入“1”即可。

我该如何做最后一句话试图向我解释的事情？

我目前正在学习离散数学测试，我们正在学习乔姆斯基的层次结构和识别层次结构每个级别的自动机类型。我被告知大多数计算机语言都属于层次结构的“第 2 级和第 1 级”，但不准确。

我的问题是：

1. 每个级别都有哪些功能？

2. 这仅仅是理论基础吗？我想知道像 Dennis Ritchie 和 James Gosling 这样的语言设计师在设计 C 和 Java 时是否必须考虑到这一点。他们有吗？有人会如何应用这个？

3. 我们被告知图灵机可以识别层次结构的第 0 级。如果有，是否有属于 0 级的语言特征？我猜这可能是自然语言处理，是吗？

一些程序员在理论 CS 课程中看不到太多相关性（尤其是我的学生）。这是我觉得非常相关的事情。让我为那些以前没有看过它的人构建它......

A) 编程问题可以改写为关于语言的问题。

B) 图灵机识别语言。

C）图灵机可以编码为（大）整数。

D）因此，可能的图灵机的数量是可数无限的

E) 一个集合的幂集就是该集合的所有可能子集。

F) 如果一个集合是可数无限的，它的幂集更大，即不可数无限。

G) 因此，如果一种语言是无限的，它就有无数个子集。这些中的每一个都代表一个问题。但是只有无数的图灵机可以用来解决这些问题。如果我们不能用图灵机解决问题，它就无法解决。

结论……我们只能解决所有问题的一小部分。

我的问题差不多到了……

每当我向学生提出这个论点时，他们都会陷入可数与不可数无限之间。他们通常没有很强的数学背景，所以试图通过康托尔的对角化论证来解释往往会让他们眼花缭乱。

通常我会尝试给他们一些他们可以掌握的东西，就像这样......在计数线的任何部分放置一个有限的盒子，我们捕获这些数字的有限数量......但是在任何部分放置一个有限的盒子实数线，我们捕获了无限数量的实数。一种证明实数比计数数多的证据。

最后我的问题......你如何向那些从未听说过这个概念并且可能没有数学倾向的人解释多重无穷大的概念？

最终编辑：通过提出这个问题，我学到了很多东西，我很感激反馈。我浪费了太多时间试图弄清楚“社区维基”到底是什么。我了解到，有些人对理论问题存在固有的偏见，我认为这只是一个错误，因为我们今天所做的很多事情都是昨天的理论。但是这种偏见是很自然的，虽然我不同意他们对理论价值的看法，但我对此没有异议，它有助于我了解我的学生来自哪里。我确实认为 BS 的评论是不必要的。

我根本不认为这个问题是民意调查或预测 2009 年的问题。那些只想要编码问题和编码答案的人可能想要重新检查该要求。我已将此问题移至社区 wiki，但强烈认为我因不当使用武力而被迫这样做。

我正在研究图灵机的测试，但我遇到了一个问题，我必须创建一个图灵机作为函数计算器：

我知道我的磁带输入会像这样分开：

我的磁带输出就像

我将如何在磁带上放置 X 和 Y？（可以是多磁带机）状态图是什么样的？

注意：我使用的是一元，其中 1 用于表示 0，而 0 不用作值，而是用作分隔符。

所以：

我正在学习一门非常基于 jflap 的课程的自动机测试。问题是我们没有太多的文档，而且我在 jlap 上找到的示例自动机，例如this和this，不足以为即将到来的测试做准备。

我在哪里可以找到更多信息？任何其他具有示例图灵机的资源都显示为带有转换的图表，这也会有所帮助。