图灵机（一）

1.图灵机的定义

1.1图灵的定义

1.2帖子的定义

1.3定义正式化

1.4描述了图灵机的行为

2.用图灵机计算

2.1一些（简单）的例子

2.2可计算数和问题

2.3图灵的通用机器

2.3.1计划和行为的互换性：符号

2.3.2计划和行为的互换性：基本功能

2.4停止问题和OntscheidungsProblus

2.4.1直接和间接明确决策问题的证明

2.4.2图灵的基本问题CIRC？，打印？ 和entscheidungsproblem

2.4.3停止问题

2.5图灵机的变化

3.与图灵机关的哲学问题

3.1人类和机器计算

3.2论文，定义，公理或定理

4.可计算性的替代历史模型

4.1常规递归函数

4.2λ可定义

4.3后生产系统

4.4配方1

5.图灵机器对计算机科学的影响

5.1对理论计算机科学的影响

5.2图灵机和现代计算机

5.3编程理论

参考书目

学术工具

其他互联网资源

繁忙的海狸

停止问题

在线图灵机模拟器

软件模拟器

硬件模拟器

相关条目

1.图灵机的定义

1.1图灵的定义

在数学基础的研究中提出了图灵的图灵机。 更具体地，他使用这些抽象设备来证明没有有效的一般方法或过程来解决，计算或计算以下问题的每个实例：

EntscheidungsProblob解决了一阶逻辑中的每一个语句的问题（所谓的受限功能微积分，请参阅介绍的古典逻辑上的条目）是否可导出在该逻辑中。

请注意，在其原始形式（Hilbert＆Ackermann 1928）中，问题在有效性而不是衍生性方面说明。 鉴于哥德尔的完整性定理（Gödel1929）证明有效的程序（与否）对于衍生能力也是其有效形式问题的解决方案。 为了解决这个问题，人们需要一个正式的“有效手术”的概念，而图灵的机器旨在做到这一点。

然后，在图灵的原始定义中，一个图灵的机器或作为图灵的计算机器，是一种能够有限一组配置Q1，...，Qn（通过图灵所谓的M-Configurations的机器状态）的机器。 它提供单向无限和一维磁带，其分为各自能够携带一个符号的正方形。 在任何时刻，机器都扫描一个平方R的内容，它是空白的（由S0符号化）或包含符号S1，...，SM，S1 = 0和S2 = 1。

该机是一种自动机器（A机器），其意味着在任何给定时刻，机器的行为完全由当前状态和符号（称为配置）扫描。 这是所谓的确定条件（第3节）。 这些A机器与所谓的选择机器形成对比，下一个状态取决于外部设备或操作员的决定（图4936-7：232）。 图灵机能够提供三种类型的动作：

打印si，将一个方形移动到左（L）并转到州QJ

打印Si，将一个方形移动到右侧（R）并转到州QJ

打印si，不要移动（n）并转到州qj

然后，图灵机的“程序”可以写成表单的有限Quintuple：

qisjsi，jmi，jqi，j

如果Qi是当前的状态，SJ被扫描的广场的内容，Si，J是广场的新内容; MI，j指定机器是否将一个平方向左移动到左侧，向右或保持在同一方形，而qi，j是机器的下一个状态。 这些Quintuple也称为给定机器的转换规则。 当从空白磁带开始时，所以当从空白带开始时，所以通过表1计算序列S0S1S0S1 ......

表1：Tsimple的Quintuple表示

; q1s0s0rq2; q1s1s0rq2; q2s0s1rq1; q2s1s1rq1

请注意，Tsimple永远不会进入扫描S1的配置，使得四个Quintuls中的两个是冗余的。 另一种代表图灵机的典型格式以及图灵也使用的格式是过渡表。 表2给出了Tsimple的过渡表。

表2：Tsimple的过渡表

s0s1q1s0rq2s0rq2q2s1rq1s1rq1

当我的目前的图灵机目前的定义通常只有一种类型的符号（通常只需0和1; Shannon被证明，任何图灵机都可以减少到二进制图定型机（Shannon 1956）），以他所谓的计算机器的原始定义，使用了两种符号：完全由0s和1s和第二种符号组成的数字。 这些通过使用第二种数字和符号的交替平方的系统来区分图拉机带。 一个交替正方形的一个序列包含数字并且被称为F正方形的序列。 它包含由机器计算的序列; 另一个被称为E形方块的序列。 后者用于标记F正方形，并在那里“辅助存储器”（图4936-7：232）。 E形方块的内容易于改变。 然而，不能改变F正方案，这意味着一个人无法实现算法，从而需要更改前面的计算数字。 此外，如果尚未计算的F范围，机器将永远不会在F-Square上打印符号。 F和E-Squares的这种使用可能非常有用（请参阅第2.3秒）但是，如Emil L.帖子所示，它会导致许多并发症（见第1.2章）。

关于图灵机设置有两个重要的事情要注意到。 首先涉及机器本身的定义，即机器的磁带可能是无限的。 这对应于假设机器的存储器（可能）无限的假设。 第二个涉及图灵计算的定义，即如果存在一组指令，则函数将是计算的可计算，这将导致图灵机计算函数而无论它所需的时间量如何。 人们可以考虑这一点，假设可能无限时间完成计算。

这两个假设旨在确保结果的定义结果不是太窄。 这是，它确保不完全没有可计算的功能将无法计算，因为没有足够的时间或内存来完成计算。 因此，可能存在一些现有计算机不能执行的可计算功能，可能是因为没有现有机器具有足够的存储器来执行任务。 一些图灵可计算功能可能无法在实践中可计算，因为它们可能需要更多的存储器，而不是使用宇宙中的所有（有限数量）原子构建。 如果我们之前假设物理计算机是图灵机的有限实现，因此图灵机用作计算机的良好形式模型，结果表明函数不是计算的计算非常强大，因为它意味着我们可以构建的计算机无法执行计算。 在第2.4节中，示出了存在不计算可计算的功能。

1.2帖子的定义

通过1947年帖子的帖子的修改是标准化的定义。在1947年的帖子中，证明了称为Thue问题的数学或半组的词问题的一定问题不是在递归的情况下进行计算（或以帖子的话语）无法解决的）。 帖子的主要策略是表明，如果它是可判定的，那么来自1936-7的以下决策问题也将是可判定的：

打印？ 决定每个图灵机的问题它是否会打印一些符号（例如，0）。

然而，通过图灵打印证明了这一点？ 不是计算的，所以你的问题也是如此。

虽然印刷的无疑性？ 邮政在帖子证明中发挥着核心作用，据信“确定了”虚假图案“的证明受”虚假图案“（第1947：9），VIZ的影响。 F和E范围的系统。 因此，发布引入了图灵机的修改版本。 帖子和图灵定义之间最重要的差异是：

邮政的图灵机，当处于给定状态时，打印或移动，因此其过渡规则更为“原子”（它没有移动和打印的复合操作）。 这导致图灵机的四重符号，其中每个四级是表3的三种形式之一：

表3：帖子的四重符号

qisjsi，jqi，jqisjlqi，jqisjrqi，j

帖子的图灵机只有一种符号，因此不依赖于F和E-Squares的图灵系统。

柱的图灵机具有双向无限磁带。

帖子的图灵机会在到达没有定义任何操作的状态时停止。

注意，TING Machine的帖子的重构非常植根于1936年的帖子中。（一些）帖子的图灵定义的修改成为图灵机的定义的一部分标准工程，如Kleene 1952和Davis 1958。从那时起，几个时间（逻辑上等效）已经介绍了定义。 如今，在某些方面，图灵机的标准定义更接近邮政的图灵机比图灵的机器。 在下文中，我们将使用Minsky 1967的标准定义上的变体，它使用了Quintuple符号，但没有E和F正方形，包括特殊的停留状态H.它还只有两个移动操作，viz，l和r，所以行动不使用机器打印。 除了机器启动时，磁带是空白的，除了磁带的一些有限部分。 注意，空白方块也可以表示为包含符号S0或简单的方形的正方形。磁带的有限含量也将被称为磁带上的DataWord。

1.3定义正式化

谈论“磁带”和“读写头”旨在帮助直觉（并揭示某些时间的图灵写入的时间），但在图灵机的定义中发挥着重要作用。 在需要进行图灵机的正式分析的情况下，在更多数学术语中阐明机械和程序的定义是合适的。 纯粹是正式的图测机器可以指定为四重奏T =（Q，σ，s，δ），其中：

Q是一组有限的状态Q

σ是有限符号

s是初始状态s∈q

Δ是确定下一个移动的过渡功能：

δ：（q×σ）→（σ×{l，r}×q）

机器T的转换功能是从计算状态到计算状态的函数。 如果δ（qi，sj）=（si，j，d，qi，j），则当机器的状态是qj时，读取符号sj，t替换si，j，方向移动d∈{l，r}并转到州qi j。

1.4描述了图灵机的行为

我们介绍了一个表示，它允许我们描述图灵机TN的行为或动态，依赖于今天也知道的完整配置（图4 1936-7：232）的符号作为瞬时描述（ID）（Davis 1982：6）。 在TI计算的任何阶段，其ID由：

（1）磁带的内容，即其数据字

（2）阅读头的位置

（3）机器的内部状态

因此，考虑到在状态Qi扫描符号SJ的一些图灵机T，它的ID由PQISJQ给出，其中P和Q是包含符号SJ的正方形的左侧和右侧的有限字。 图1给出了状态qi扫描磁带的一些图灵机T的ID的视觉表示。



图1：一些图灵机T的完整配置。[图1的扩展描述是补充。]

因此，表示法允许我们通过其连续ID捕获机器及其磁带的开发行为。 图2使用图形表示给出了Tsimple的前几个连续的ID。

图2：Tsimple图形表示的动态。 （动画可以通过单击图片来开始，然后使用左箭头和右箭头来移动它。）[图2的扩展说明在补充中。]

使用其符号表示，人们还可以明确打印连续的ID。 这导致了图灵机的行为的状态图。 所以，对于我们得到的Tsimple（请注意，¯0表示0s的无限重复）：

¯0q10¯0¯00q20¯0¯001q10¯0¯0010q20¯0¯00101q10¯0¯001010q20¯0⋮

2.用图灵机计算

正如秒所解释的那样。 1.1，图灵机最初旨在将可计算性的概念正式化，以解决数学的基本问题。 独立于图灵，Alonzo教堂提供了不同但逻辑上等效的制定（见第4章）。 如今，大多数计算机科学家都同意图灵或任何其他逻辑上等效的正式概念捕获了所有可计算问题，viz。 对于任何可计算问题，有一个计算它的图灵机。 这被称为教会图论论文，图灵的论文（当参考只参考工作时）或教会的论文（当参考只对教会的工作）时。

它意味着，如果接受，则无需任何有限的装置而不可通过任何有限装置计算的任何问题。 事实上，由于它是为了捕获“[全部]可以在计算数字中进行的可能进程而设计的雄心，因此，如果我们接受图灵的分析：

无需通过图灵机可计算的任何问题在绝对意义上不是“可计算”（至少，相对于人类绝对），参见第3节）。

对于我们认为可计算的任何问题，我们应该能够构建计算它的图灵机。 把它放在图灵的措辞中：

我的争论是[计算机器] [计算机]的操作包括所有在计算的计算中使用的所有争论。 （图灵1936-7：231）

在该部分中，将给出示例，其示出了图灵机模型的计算功率和边界。 第3节然后讨论了与图灵论文相关的一些哲学问题。

2.1一些（简单）的例子

为了谈谈从人类角度有所了解的东西，我们必须提供对磁带上记录的符号的解释。 例如，如果我们想设计一台将计算一些计算一些数学函数的机器，那么我们将需要描述如何解释作为数字上显示的磁带上的零和零。

在遵循的示例中，我们将表示数字n作为磁带上符号'1'的n + 1份的块。 因此，我们将表示为单个“1”的数字0，而第3号作为四个'1的块。 这称为一元符号。

当机器启动时，我们还必须对磁带的配置进行一些假设，并且在完成时，以解释计算。 我们将假设如果要计算的函数需要n个参数，则图灵机将以其头部扫描1的N块块的最左侧的“1”开始。 表示参数的'1的块必须通过符号'0'的单个发生来分隔。 例如，为了计算SUM 3 + 4，图灵机将以图3所示的配置开始。



图3：用于两个数字n和m的计算的初始配置。 [图3的扩展描述是补充。]

这里假设的加法机需要两个代表要添加的数字的参数，从第一个参数的最左边启动。 参数根据需要由单个0分隔，第一个块包含四个'1的，表示数字3，第二个块包含五个'1，表示数字4。

机器也必须以标准配置完成。 必须有一个单个符号块（表示表示某种输出的一些数字或符号的1S序列，并且机器必须扫描该序列的最左侧符号。 如果机器正确计算函数，则此块必须表示正确的答案。

采用该公约用于终止配置图定型机器意味着我们可以通过将一台机器的最终状态识别下一个的初始状态来编写机器。

添加两个数字n和m

表4给出了图灵机TADD2的过渡表，它增加了两个自然数N和M。 我们假设机器在状态Q1中开始扫描N + 1的最左侧1。

表4：TADD2的过渡表

01q1 / 0rq2q21lq31rq2q30rq41lq3q4 / 0rqhalt

使用Unary表示时，使用图灵机进行添加的想法是将最左边的N个正方形转移到右侧。 这是通过擦除N + 1的最左侧1来实现的（这在状态Q1）中，然后在N + 1和M + 1到1之间设置0（状态Q2）。 然后我们有n + m + 2，因此我们仍然需要擦除一个额外的1.这是通过擦除最左边的1（状态Q3和Q4）来完成的。 图4显示了3 + 4的该计算。

图4：TADD2的计算3 + 4（可以通过单击图片来启动动画，然后使用左右箭头来移动透过它。）[图4的扩展说明在补充中。]

添加n个数字

我们可以将TADD2概括为图灵机Taddi，以添加整数N1，N2，...，NJ的任意数量I。 我们再次假设机器在状态Q1中扫描N1 + 1的最左侧1。 表5中给出了这种机器Taddi的过渡表。

表5：TADDI的过渡表

01q1 / 0rq2q21rq31rq2q30lq61lq4q40rq51lq4q5 / 0rq1q60rqhalt1lq6

机器TADDI使用将添加剂转移到右侧的附加物的原理，该原则也用于TADD2。 更具体地，Taddi从左到右计算N1 + 1，N2 + 1，... Ni + 1的总和。 它根据以下计算此总和：

n1个= n1个+氮气+ 1n2 = n1个+ n3n3 = n2的+ n4⋮ni = ni-1 + ni + 1

TADD2和TADDI之间最重要的区别在于TADDI需要验证最左边的ADDID NJ，1 ＜J≤I等于NI。 这是通过检查NJ右侧的第0个是否遵循另一个0或不（Q2和Q3）来实现的。 如果不是这种情况，则还有至少一个待添加的添加NJ + 1。 请注意，与TADD2的情况一样，机器需要从ADDID NJ + 1擦除通过状态Q5完成的附加器。 然后它返回到州Q1。 另一方面，如果NJ = NI，则机器移动到NI = N1 + N2 + ... + NI + 1的最左侧1并停止。

2.2可计算数和问题

图灵的原文涉及可计算（真实的）数字。 如果存在用于将任意精确的近似值计算到该数字的图定机器，则（Real）编号是可计算的。 所有代数数（具有代数系数的多项式的根）和许多超越数学常数，例如e和π是图4的计算。 图灵提供了通过图灵机可计算计算的数量的若干示例（参见图10所计算的大类数字的示例，其计算为1936-7所可计算的）作为启发式参数，示出可以通过图灵机来计算广泛的数量的类别的类别。

但是，有人可能怀疑与数字，viz有什么意义计算。 计算，捕获非数值但可计算问题，因此图灵机如何捕获所有一般和有效的程序，这些过程确定是否是这种情况。 这些问题的例子是：

“决定任何给定的x是否表示X表示素数”

“决定任何给定的x是否是x是图灵机的描述”。

通常，这些问题是表单：

“决定任何给定的x是否有x具有属性x”

计算机计算中的一个重要挑战和具体进步（通常在与其他学科的界面处）已成为提供X解释的问题，使得它可以计算地解决。 为了只给出一个具体的例子，在日常计算实践中，有一个方法可以决定任何数字“源”是否可以信任，所以需要一种对信任的计算解释。