turing是什么意思ing在线翻译读音例句

什么是图灵完备性（Turingcomplete）？

这是⼀篇旨在帮助理解图灵机及相关概念是什么，⽽⾮证明其正确性的回答，它包含以下内容：

1.什么是图灵机

2.图灵机可以解决什么问题

3.什么是图灵完备

4.直观理解图灵完备——Brainfuck语⾔

1.什么是图灵机

图灵机（TuringMachine）是图灵在1936年发表的\"OnComputableNumbers,withanApplicationtothe

Entscheidungsproblem\"（《论可计算数及其在判定性问题上的应⽤》）中提出的数学模型。既然是数学模型，它就并⾮⼀个实体概念，

⽽是架空的⼀个想法。在⽂章中图灵描述了它是什么，并且证明了，只要图灵机可以被实现，就可以⽤来解决任何可计算问题。

图灵机的结构包括以下⼏个部分：

1.⼀条⽆限长的纸带（tape），纸带被分成⼀个个相邻的格⼦（square），每个格⼦都可以写上⾄多⼀个字符（symbol）。

2.⼀个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含⼀个特殊的空⽩字符（blank），意思是此

格⼦没有任何字符。

3.⼀个读写头（head），可理解为指向其中⼀个格⼦的指针。它可以读取/擦除/写⼊当前格⼦的内容，此外也可以每次向左/右移动⼀

个格⼦。

4.⼀个状司马懿后代下场有多惨 态寄存器（stateregister），它追踪着每⼀步运算过程中，整个机器所处的状态（运淡妆浓抹的意思 ⾏/终⽌）。当这个状态从运⾏变为终

⽌，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它便对应着有限状态机⾥的状态。

5.⼀个有限的指令集（instructionstable），它记录着读写头在特定情况下应该执⾏的⾏为。可以想象读写头随⾝有⼀本操作指南，⾥

⾯记录着很多条类似于“当你⾝处编号53的格⼦并看到其内容为0时，擦除，改写为1，并向右移⼀格。此外，令下⼀状态为运⾏。

”这样的命令。其实某种意义上，这个指令集就对应着程序员所写下的程序了。

图灵机结构

在计算开始前，纸带可以是完全空⽩，也可以在某些格⼦⾥预先就有写上部分字符作为输⼊。运算开始时，读写头从某⼀位置开始，严格按

照此刻的配置（configuration），即：

当前所处位置

当前格⼦内容

来⼀步步的对照着指令集去进⾏操作，直到状态变为停⽌，运算结束。⽽后纸带上留下的信息，即字符的序列（⽐如类

似“...”）便作为输出，由⼈来解码为⾃然语⾔。

要重申⼀下，以上只是图灵机模型的内容，⽽⾮具体的实现。所谓的纸带和读写头都只是图灵提出的抽象概念。为便于理解打⼀个⽐⽅。算

盘虽然不是图灵机（因为它没有⽆限长的纸带，即⽆限的存储空间），但它的⾏为与图灵机⼀致。每⼀串算珠都是纸带上的⼀格，⼀串算珠

上展⽰的数字便记录着当前格中的字符（可以是空⽩，可以是12345）。⼈类的⼿即是读写头，可以更改每串算珠的状态。算盘的运⾏遵

循⼈脑中的算法，当算法结束，算盘停机。

2.图灵机可以解决什么问题

在⽂章中，图灵所做的事是证明了，假设上述模型⾥所说的功能都能被以某种形式物理实现，那么任意可计算问题都可以被解决。这⾥所说

的可计算问题，涉及到计算理论（ComputationTheory）的概念。这个领域的概念很繁杂，先简单梳理⼀下。

在计算机领域，或者说⾃动机领域，我们研究的⼀切问题都是计算问题（ComputationalProblem）。它泛指⼀切与计算相关的问题。

Acomputationalproblemisamathematicalobjectrepresentingacollectionofquestionsthatcomputersmightbeable

tosolve.

计算问题的⼀些举例：

1.给定⼀个正整数n，判断它是否是质数

2.给定⼀个01序列，把它们按位取反

3.给定⼀个字符串，判断某个字符是否存在，及查找存在位置

4.给定⼀个逻辑蕴含的命题，求它的逆否命题

⾮计算问题的例⼦：

今晚吃什么

为什么太阳从东边升起

计算问题有的可以解决，有的不可解决。这就引出了计算问题的可计算性（Computability）。它可以被理解为“是否存在⼀个算法，能解

决在任何输⼊下的此计算问题”。如上⾯的问题1，我们当然可以找到⼀个算法来解决判断任意正整数n是否为质数的问题（⽐如从2遍历

到n-1，看n是否可以整除它）。所以，问题1就是可计算的。

也有⼀些不可计算的计算问题，⽐如著名的停机问题（HaltingProblem）。它的表述是这样庐山必去的三个景点 的：给定⼀段程序的描述和该程序的⼀个有效

输⼊，运⾏此程序，那么程序最终是会终⽌，还是会死循环下去？

HaltingProblem:giventhedescriptionofanarbitraryprogramandafiniteinput,decidewhethertheprogramfinishes

runningorwillrunforever.

这个问题很绕⼈，有点像那个著名的理发师悖论，但它确实是⼀个计算问题。更具体的，它是⼀个不可判定问题（Undecidable

Problem）。即不存在⼀个通⽤算法，可以在任意输⼊下解决此问题。图灵在⽂章⾥很优雅的⽤反证法推翻了假设“假设有这么⼀个算法可

以解决任何停机问题”，从⽽证明了这样的算法并不存在。具体证明过程⽹上的资料⾮常丰富，我就不再花篇幅了。

回到这⼀节的主题。简⽽⾔之，对于⼀个问题，对于任意输⼊，只要⼈类可以保证算出结果（不管花多少时间），那么图灵机就可以保证算

出结果（不管花多少时间）。

3.什么是图灵完备

图灵完备性（TuringCompleteness）是针对⼀套数据操作规则⽽⾔的概念。数据操作规则可以是⼀门编程语⾔，也可以是计算机⾥具体

实现了的指令集。当这套规则可以实现图灵机模型⾥的全部功能时，就称它具有图灵完备性。直⽩⼀点说，图灵完备性就是我给你⼀⼯具箱

的东西，包括⽆限内存、if/else控制流、while循环……那么你现在图灵完备了吗？

概念本⾝倒是⾮常直观，但整件事似乎还是让⼈云⾥雾⾥。我曾经⼀直不懂的就是为什么图灵给出的那个命题是正确的。换句话说，凭什么

有了纸带以及其他的那⼀套东西，就可以⾃信解决任意可计算问题呢？尽管我不能通读他的那篇论⽂⾥的证明，但是通过⼀门叫做

Brainfuck的编程语⾔，还是可以获得⼀些直觉。

4.直观理解图灵完备——Brainfuck语⾔

如今主流的编程语⾔（C++，Java，Python，以及等等等等）都是图灵完备的语⾔。关于语⾔优劣之争也只是在其封装、优化等⽅⾯，以

及因为这些区别⽽产⽣的“不同语⾔适⽤于不同情况”的争执。如果我们回到最底层，就会发现它们可以实现的功能其实完全⼀样，并且本

质上就是⼀个图灵机。

在1993年，UrbanMller发明了Brainfuck语⾔。这门语⾔可以说是编程语⾔界的helloworld了——它⼀共只含有8个有效字符，无处话凄凉的整首诗句 每

个有效字符就是⼀条指令。语⾔虽然极致轻量，它却是⼀门图灵完备的编程语⾔。如果能理解它的⼯作原理，那么对于理解图灵机是有很⼤

帮助的。

BrainfuckisfullyTuring-complete.

先贴上⼀段BF的代码，体验⼀下它的画风：

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++

.------.--------.>>+.>++.

这个程序编译运⾏后，控制台打印\"HelloWorld!\"。

BF的⼯作机制与图灵机⾼度⼀致。⾸先它存储数据的⽅式是⼀个不限长的⼀维整数数组，⾥⾯的数值全部初始化为0。此外，有⼀数据指

针，每⼀时刻都指向数组的某⼀任意元素。指针可以向左/右争奇斗艳的近义词 移动，也可以读取/修改当前值。

语⾔⾥的8个有效字符分别是：

>

指针向右移动⼀格

<

指针向左移动曹操的诗以什么见长 ⼀格

+

使指针当前格数值加⼀

-

使指针当前格数值减⼀

.

把当前格数值按ASCII表输出到终端

,

从终端接受⼀byte的数据，存储其ASCII数值到当前格

[

当指针当前值为0时，程序跳转⾄与之对应的]之后；否则程序正常执⾏

]

程序跳转回与之对应的[处

有了这些⼯具，我们可以很快做出⼀个计算乘法的程序稳字组词 。因为ASCII表中\'A\'对应的值为65，可以使⽤5*13算出65并输出得到字符

\'A\'。

+++++

[

>+++++++++++++

<-

]

>.

把指针初始处的格⼦命名为cell0，cell0右边的那个格⼦命名为cell1。那么第⼀句将其递增5次变为5。然后，循环执⾏“右移指针，

递增13次，左移指针，递减1次”。推进的近义词是什么 当cell0的值最终被递减为0的时候，循环结束。此时cell1的值执⾏了5次“递增13次”的

操作，即65。指针右移⾄cell1，输出此格⼦，则在终端会看到\'A\'。

编译运⾏上述代码块