47

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

4

11 回答 11

60

图灵机之所以如此重要，与对经典计算科学或计算理论类东西的研究有关。它基本上是关于分析计算机的一般属性，例如计算机具有哪些理论能力和局限性，以及我们在谈论“计算”时的含义。

可以使用图灵机研究的一个例子是停机问题。虽然这个问题是一种学术练习，但它很容易在现实世界中产生切实的影响。为什么不编写一个调试器，它会简单地告诉您程序是否包含任何无限循环？停止问题确定了在一般情况下解决此问题是不可能的。

图灵机的研究也有助于研究语言语法及其类，从而导致编程语言的发展。术语“正则表达式”的出现是因为它们是一种正则文法，对这些文法（计算理论的一部分）的研究将告诉你更多关于正则表达式可以解决哪些问题以及它们不能解决什么问题的更多信息。例如，传统的正则表达式语法将无法解决以下问题：在输入中解析一些 N 个 'a' 字符，然后解析相同数量 N 个 char 'b'。

如果你对这类事情的好文章感兴趣，请查看Michael Sipser的计算理论导论。很好。

于 2008-10-25T06:52:51.330 回答
33

图灵机是艾伦·图灵发明的一种理论计算机，作为数学计算的理想模型，基本上是一种简单的计算机形式，由磁带（纸带）组成，有一个可以读取符号的头，在原处写一个新符号，然后向左或向右移动。

据说图灵机处于某种状态，然后一个程序就是一个转换列表，有一个当前状态和一个符号，在磁带上应该写什么，下一个状态是什么，以及在哪里头部应该移动。

这是一个基本的图灵机，用 JavaScript 实现......

和草图：

图灵机

于 2008-10-25T06:43:04.140 回答
28

我只需要我的 IBM PC 来进行计算！

其他人没有指出的事情：您的 IBM PC是图灵机。更准确地说，它等同于它，在某种意义上，您的 PC 可以做的任何事情，图灵机都可以做，而图灵机可以做的任何事情，您的 PC 都可以。

具体来说，图灵机是一种计算模型，它完全捕捉了可计算性的概念，同时保持简单的推理，没有你 PC 架构的所有具体细节。

（普遍接受的）“Church-Turing 论点”断言，每个设备或计算模型并不比图灵机更强大。因此，许多理论问题（例如 P 和 NP 等类，“多项式时间算法”的概念等）都以图灵机的形式正式表述，当然，它们可以适用于其他模型：好。（例如，有时用 lambda 演算、组合逻辑或其他任何东西来考虑计算会很方便……它们在能力上彼此相等，对你的 IBM PC 也一样。）

所以你去吧：人们谈论图灵机是因为它是一种精确且完全指定的方式来说明“计算机”是什么，而不必描述 CPU 架构的每个细节、它的约束等等。

于 2008-10-28T17:53:15.120 回答
27

自然界中实际上有图灵机的例子。具体来说，将 RNA 翻译成蛋白质的核糖体实现了图灵机。

首先，一些背景：

  1. RNA 由一串核苷酸（“碱基”）组成，这些核苷酸定义了遗传字母表中的字母。
  2. RNA字母表中有4个碱基——A、C、G、U。
  3. 碱基是定向的：按照惯例，末端被称为五素数和三素数（5'，3'）
  4. RNA 串中的一个碱基可以以“反平行互补对”的形式吸引另一个 RNA 串上的一个碱基，其中 A 粘在 U 上，C 粘在 G 上。
  5. 碱基以 3 个为一组组合形成“密码子”（单词）。
  6. 密码子有 64 种可能的组合 (4^3)。
  7. 每个密码子都可以匹配一个“反密码子”。例如 AUG <-> UAC
  8. 有特殊的载体分子（“tRNA”）具有特殊的反密码子并连接到特定的氨基酸（蛋白质）。

核糖体的操作很简单：

  1. 转录起始于“起始密码子”，它定义了“阅读框”
  2. 转录总是沿 5'->3' 方向进行
  3. 阅读框下的密码子与包含特定氨基酸的特定 tRNA 匹配
  4. 起始密码子总是编码氨基酸蛋氨酸。
  5. 新的氨基酸附着在生长的蛋白质上
  6. 然后框架前进 3 个碱基到下一个密码子，蛋白质不断延伸
  7. 在遇到“终止”密码子时，翻译终止，没有氨基酸连接，核糖体从 mRNA 上解离。

如您所见，这是一个非常简单的图灵机，它执行最复杂的操作——自然本身！

于 2008-10-25T22:31:19.130 回答
6

图灵机是一种理论机器，可用于推理计算机的局限性。简单地说，它是一台具有无限内存的假想计算机。

我们关心图灵机，因为它们帮助我们发现用真正的计算机（比如你的 IBM PC）不可能完成的事情。如果图灵机不可能执行特定的计算（例如决定停机问题），那么您的 IBM PC 也不可能执行相同的计算。

于 2008-10-25T10:02:24.863 回答
3

为什么设计飞机的人会关心莱特兄弟，或者让固定翼飞机飞行的“升力”背后的科学？

艾伦·图灵被誉为现代计算之父。图灵机是所有现代计算机的先驱。

可计算性理论是我在大学里最难的一门课，但我很高兴我上了。它让我思考我永远不会有的事情，或者以我永远不会有的方式思考事情，这些都是好事。

于 2008-10-25T09:02:45.560 回答
2

图灵机是一种能够计算的抽象机器。

来自维基百科：

图灵机是基本的抽象符号操作设备，尽管它们很简单，但可以适应模拟任何计算机算法的逻辑。艾伦·图灵在 1936 年描述了它们。图灵机并不是一种实用的计算技术，而是一种关于机械计算极限的思想实验。因此，它们实际上并没有被建造。研究它们的抽象属性可以对计算机科学和复杂性理论产生许多见解。

能够模拟任何其他图灵机的图灵机称为通用图灵机（UTM，或简称为通用机）。Alonzo Church 引入了一个具有类似“普遍”性质的更面向数学的定义，他在 lambda 演算方面的工作与 Turing 在正式的计算理论中交织在一起，称为 Church-Turing 论文。该论文指出，图灵机确实捕捉到了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。

于 2008-10-25T06:28:35.760 回答
2

图灵机是一种抽象机器，它可以对一系列数据进行操作，并且可以根据某种逻辑在操作时改变自己的状态以及数据。

这是一个构成算法、存储程序和一般计算基础的概念。如果您正在处理算法、状态、数据等，它提供了很好的见解和抽象。

对于大多数人来说，值得深思。

于 2008-10-25T06:44:44.153 回答
1

除了 Wikipedia 条目之外，您可能还想阅读Charles Petzold所著的 The Annotated Turing一书。副标题是“Alan Turing 关于可计算性和图灵机的历史论文的导览”，它包括完整的论文，分成多个块，包含许多关于该主题的论述，包括历史观点。

于 2008-11-02T02:16:04.740 回答
1

图灵机相当于一种算法。它在接受字符串时停止，在不接受字符串时拒绝或进入无限循环。

磁带充当存储器，转换规则充当“if then else”条件

于 2016-02-16T16:55:53.237 回答
-1

图灵机的惊人之处在于，它是现存的最基本的计算机，它可以执行与当今存在的任何计算机一样强大的计算。没有图灵机无法解决的计算机问题。实际上，如果您想这样看，您的计算机就是 TM。

Alan Turing 发明了 TM 并使用它的某个版本来解码纳粹加密机 Enigma。

所以总而言之，它是一个非常强大的机器，在理论计算机科学中有很多应用。（顺便说一句，这也是一个超级有趣和刺激的主题）。

于 2019-11-27T00:55:05.113 回答