目录

一，解读王培老师的文章：计算机不是只会 “计算”，图灵机也不是一台“机器” 

二，计算机理论基本概念的溯源

三，给王培老师的提问

一，解读王培老师的文章：计算机不是只会 “计算”，图灵机也不是一台“机器”

作者开篇说，在讨论人工智能的潜力和限度时，常常有人拿 “图灵机” 和 “可计算性” 说事。其论证大致是这样几步：

（1）既然人工智能是在计算机中实现的，其能力自然在计算机能力范围之内；

（2）现有计算机的计算能力都和图灵机相同；

（3）那些图灵机不能解决的问题，当然也就是人工智能所无法解决的。

接着作者运用一个举一反三的简单例子，试图从图灵机的初态与终态变易的角度，解读图灵机的“确定性计算”与人工智能的“不确定性计算”的异同，以分析上述论证混淆了图灵计算与人工智能，并指出这样的认知混淆与“顾名思义”有关，属于认知上的“稻草人”谬误。

1，图灵机的初态与终态的变易

作者举了3个图灵机的例子，说明图灵计算与人工智能的区别：确定性与不确定性。

- 机器甲：判定输入中1的个数是否为偶数

状态变换规则：

A 0 # A -> (状态A, 关注的符号是0，把它改成 #，状态不变, 右移）

B 0 # B -> (状态B, 关注的符号是0，把它改成 #，状态不变, 右移）

A 1 # B -> (状态A, 关注的符号是1，把它改成 #，状态变为B, 右移）

B 1 # A -> (状态B, 关注的符号是1，把它改成 #，状态变为A, 右移）

A # # Z ^  (状态A, 关注的符号是#，进入终态Z）

初态为A

如：

0 1 1 0 1 1 #

# # # # # # #

A A B A A B A Z 

达到了终止状态Z，停止运行，接受。

0 1 1 0 1 1 1 #

# # # # # # # 

A A B A A B A B

B由于没有变换规则可以应对当前情况，停止运行，拒绝。

- 机器乙: 判定输入中的1的个数的奇偶性。

状态变换规则与机器甲相同，初态为B。

如：

0 1 1 0 1 1 #

# # # # # # 

B B A A B A B 

B由于没有变换规则可以应对当前情况，停止运行，拒绝。

0 1 1 0 1 1 1 #

# # # # # # # #

B B A B B A B A Z

达到了终止状态Z，停止运行，接受。

- 机器丙

与机器甲基本相同，只是取消了状态 Z和最后一条变换规则。这样一来，当所有符号都成为 #，机器不再有适用变换规则，就会停在当前状态，而这个状态同样可以代表输入中1的个数的奇偶性，因此也可以被用作机器丙的计算结果。这台机器在处理完一个输入序列后，只要将状态重新初始化为A，即可以处理下一个序列。

如：

0 1 1 0 1 1 #

# # # # # # 

A A B A A B A   （A对应于偶数）

0 1 1 0 1 1 1 #

# # # # # # # 

A A B A A B A B （B对应于奇数）

一个有趣的问题是：如果不做状态重新初始化，情况会怎样？显然，如果机器丙在一次计算之后状态停在B，则下次计算这个机器就变成机器乙了，并且后面会不断在机器甲和机器乙之间转换，而不再完成一个“确定的计算”。这个机器的处理结果不仅仅取决于当前输入，还取决于开始处理这个输入时的系统状态，而这个状态是系统的历史决定的。

图灵计算：一个符号串里面有多少个1，与处理机制的历史和状态不应该有任何关系，所以对应的计算当然必须从同一个初始状态开始，这才能保证过程和结果的确定性，或者说“可重复性”。

严格说来，一个不断学习的系统是不重复先前的内部状态的，因此即使是相同的输入，处理过程和结果都未必相同。在这种情况下，相对于这个输入而言，这台装置就不是一个图灵机，尽管它可以具有图灵机定义中的前面5个成分，就像机器丙那样。

2，“问题求解”（Problem-Solving）：“下棋” 与“学棋”

如果这个系统在学下棋，那么我们通常会把每盘棋看作一个要解决的问题，而这和把整个 “学下棋过程” 当作一个问题是非常不同的。

相对前者而言，系统的解题行为应该是随着时间而变的，因此不是一个 “下棋图灵机” 。这种变化是因为前面解题周期的终态成为了后面解题周期的初态，而不需要引入其它因素来解释。

二，计算机理论基本概念的溯源

1，图灵工作概述

1900年，希尔伯特提出Entscheidungsproblem：是否存在解决任何可定义的数学问题的判定方法或过程？Entscheidungsproblem这一词由于历史时间不同，具有有不同的具体表达形式。

1931年，哥德尔不完备定理：任何无矛盾的公理体系，只要包含初等算术的陈述，则必定存在一个不可判定命题，用这组公理不能判定其真假。

1936年，图灵在论文《论可计算数及其在判定问题上的应用》中证明：不存在通用的过程可以判定给定的函数演算K的公式。

1950年，图灵论文《计算机器与智能》（Computing Machinery and Intelligence)。

1952年，图灵论文《形态发生的化学基础》（The Chemical Basis of Morphogenesis）。

2，可计算性与丘奇－图灵论题

“可计算性（Computability）”是可计算性理论的核心概念。图灵通过递进的方式定义这个概念：

首先，图灵在论文中开门见山提出“可计算数”的概念，表达“可计算性”指机器能把“结果”实际写下来：“按照我的定义，一个数是可计算的，如果它的十进制的表达能被机器写下来。”

至于，为什么定义“可计算数”，而不是“可计算函数”，“可计算谓词”，图灵解释：“在每种情况下，基本的问题是一样的，我选择可计算数来解释，是因为这样可以涉及最少的技术细节。”

然后，图灵开始设计今天所说的“图灵机”：computing machine。

是有“丘奇－图灵论题”：任何在算法上可计算的函数同样可由图灵机计算。

但是，图灵设计图灵机的目的是为了解决“判定问题”（Entscheidungsproblem）

3，“判定问题”与人工智能

图灵在《计算机器与智能》谈及9个典型“机器能思考吗？”辩论中的反对观点，其中（３）来自数学的异议：

数理逻辑中的一些结果可以用来指出离散状态机器能力的局限，其中最著名的就是哥德尔定理，此定理声称，在任何充分的逻辑系统中都能形成陈述，在本系统中既不能被证真，也不能被证伪，除非这个系统本身就是不一致的，丘奇、克利、罗瑟和图灵等人也得到了相似的结果。

我们知道机器必定无法回答的问题是下述这类问题：“考虑有以下特点的机器。。。这台机器会不会对任何问题作出’Yes’的回答？”这里省略的是如§5中对某台标准形式机器的描述。如果所描述的机器与那台被提问的机器具有某些相对简单的联系，那么，我们就能知道，答案不是错了，就是没有答案。这就是数学的结论：此结论认定机器能力有限，而人类智能则没有这种局限性。

机器不能判断自己的“可计算性”，图灵认为，这是数理逻辑的结果。

所以图灵提出“机器思维”，意味着加入“人”的因素。这就是涉及到，人机关系，图灵计算与人工智能的复杂关系，。。。

三，给王培老师的提问

1，王培说：在那时计算机 (computers) 尚未出现，而图灵的本意也不是要设计这样的机器，而是要为在数学中广泛使用的 “可计算” 这一概念提供一个严格的定义。由于人们（甚至以严谨著称的数学家们）往往对同一个概念有不同理解，图灵试图用一个想象的机械装置来避免歧义。

一方面，图灵提出“图灵机”为 “可计算” 这一概念提供一个严格的定义；另一方面，提出“图灵机”的目的却是为了证明希尔伯特提出的“判定问题（Entscheidungsproblem）”。那么怎么看“判定问题”与“人工智能”的关系？

2，怎么看人工智能中“人”的干预，比如：机器学习中参数的调节，数据标签，神经网络层次数及神经元数确定？

3，王培说“一个不断学习的系统是不重复先前的内部状态的”，那么您是否认为人工智能与图灵计算的主要区别与图灵计算的初态与终态的变易相关？

4，在“计算”与“智能”之间是否应考虑“判断”这一层级？

5，怎么看待NP问题与人工智能所解决的问题？它们之间是否有联系？

参考文献：

【1】王培，计算机不是只会 “计算”，图灵机也不是一台“机器”：https://www.thepaper.cn/newsDetail_forward_7683950

【2】A.M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

【3】A.M. Turing, Computing machinery and intelligence, Mind,59, 433- 460，1950. https://www.csee.umbc.edu/courses/471/papers/turing.pdf