静5杰出讲座回顾 | 图灵奖得主Gilles Brassard谈“艾伦·图灵与我”

关键词：CFCS杰出讲座；北京大学大学图灵班

编者按

2026 年 7 月 14 日，2025 年图灵奖得主、量子密码学奠基人之一 Gilles Brassard 教授做客北京大学前沿计算研究中心，带来题为“艾伦·图灵与我”（Alan Turing and Me）的主题报告。

本次报告从艾伦·图灵 1936 年发表的奠基性论文出发，讨论其中关于可计算实数定义的一个看似细微却影响深远的问题，并由此延伸至现代可计算性理论、零值判定的不可判定性以及 Brouwer 的直觉主义数学。

活动吸引了来自各界的专家、学者和学生积极参与，现场交流充分，讨论气氛热烈。报告由图灵班科研导师、北京大学前沿计算研究中心助理教授袁骁主持。

活动现场

活动伊始，北京大学客座讲席教授、前沿计算研究中心主任 John Hopcroft 教授代表北京大学图灵班，邀请 Gilles Brassard 教授担任“北京大学图灵导师”，期待他在未来进一步指导图灵班学生开展学术研究，助力学生成长与发展。随后，Hopcroft 教授现场为 Brassard 教授颁发荣誉证书。

颁发荣誉证书

从图灵可计算数谈起

报告中，Brassard 教授首先回顾了图灵关于可计算数的奠基性工作，并介绍了图灵机、可计算数和可计算函数等基本概念。

按照图灵最初的定义，如果一台图灵机能够将某个实数的数字逐位写出，那么这个实数就是可计算的。为突出这种表示方式的特点，Brassard 教授将这类实数称为“可打印数”（printable numbers）。

在此基础上，他提出了一个基础却容易被忽视的问题：

“能够将一个实数的小数位逐位打印出来”，是否等价于“能够以任意给定精度计算这个实数”？

这两种定义表面上十分接近，却对应着不同的计算表示方式。

Gilles Brassard 教授

相同的实数集合，不同的计算表示

Brassard 教授指出，“逐位打印”和“任意精度逼近”两种定义最终刻画了相同的实数集合，但它们所提供的程序表示并不等价。换言之，对于单个实数而言，两种定义所描述的对象范围相同；然而，并不存在一种统一、有效的方法，可以将任意一种表示转换为另一种表示。

这种“集合等价、表示不可有效转换”的差异会带来一个看似反常的结论：在图灵最初的逐位打印表示下，即使是“将一个实数乘以 3”这样简单的运算，也不一定构成可计算操作。

其关键原因在于，逐位打印要求程序精确确定结果的每一位数字。当某个输入值非常接近会引起进位的位置时，仅凭有限位输入信息，程序可能无法判断输出的某一位是否会受到后续数字的影响。报告中，Brassard 教授对这一结论及其证明思路进行了简要介绍。

从“逐位打印”到“有效逼近”

为解决上述表示方式带来的问题，现代可计算分析通常采用“有效逼近”的方式定义可计算实数。

具体而言，对于任意给定的精度 $n$ ，计算程序不必直接输出实数 $x$ 的第 $n$ 位数字，而只需输出一个有理数

$\frac{pn}{qn},$ 使其满足

$\left|x-\frac{pn}{qn}\right|\leq 10^{-n}.$ 这种定义强调：程序能够按照一个已知且有效的收敛速度，对实数 (x) 进行任意精度的逼近。以这种方式表示的实数，通常被称为现代意义下的可计算实数（computable real numbers）。

活动现场

Brassard 教授进一步总结了两种表示方式的核心区别：

“可打印”要求机器精确确定实数的每一位数字；
“可计算”只要求机器给出误差范围明确且可控的近似值。

这一差异表明，对于连续对象而言，“能够任意精确地逼近一个对象”与“能够逐位精确地输出对象”并不是同一个计算任务。

为什么可计算实函数必须连续

随后，Brassard 教授进一步讨论了哪些实函数 $f:\mathbb{R}\rightarrow\mathbb{R}$ 可以被有效计算，并介绍了可计算分析中的一个基本结论：在标准的可计算实数表示下，可计算实函数必须是连续函数。特别地，在闭区间上，任何不连续的实函数都不可能被这样的计算程序实现。

活动现场

这一结论可以从计算过程对有限信息的依赖得到直观理解。一个在有限时间内终止的程序，只能读取输入实数的有限精度近似。当两个输入足够接近时，程序在有限时间内可能无法将它们区分。因此，函数输出也不可能在输入发生任意微小变化时突然出现有限幅度的跳跃。换言之，计算程序对输入信息的有限访问方式，天然要求输出随输入连续变化。连续性不仅是实函数的数学性质，也反映了计算过程本身的有限性与构造性。

计算对象、表示方式与构造性

图灵最初基于“逐位打印数字”的实数可计算性定义，与现代基于“有效逼近”的定义虽然刻画了相同的实数集合，但两种程序表示无法通过统一的有效过程相互转换。在前一种表示下，甚至“乘以 3”这样的基本运算也可能无法计算；而在后一种表示下，许多常见的算术运算则能够自然实现。这一差异揭示了可计算性理论中的一个根本问题：

一个数学对象是否可计算，不仅取决于对象本身，还取决于程序如何表示和访问这个对象。由此，Brassard 教授进一步将讨论联系到零值判定问题、不可判定性以及 Brouwer 的直觉主义数学，说明经典数学中看似自然的存在性判断，在构造性数学和可计算性理论中可能具有完全不同的含义。

交流与讨论

报告结束后，Brassard 教授与现场师生围绕可计算实数、数学对象的表示方式、人工智能与理论计算机科学的未来发展等问题展开了深入交流。现场师生踊跃提问，Brassard 教授结合自身研究经历，对相关问题作出了细致回应，并分享了他对理论计算机科学发展方向的思考。

交流环节

本次活动不仅加深了师生对可计算性理论基本问题的认识，也展现了从经典理论问题出发重新审视现代计算概念的重要价值，为人工智能、理论计算机科学与数学基础研究的进一步交叉融合提供了新的思考。

活动合影

背景链接

Gilles Brassard 自1979年起担任蒙特利尔大学计算机科学教授，早在无人能够预见量子信息革命将催生出一个价值数十亿美元的产业之时，他便奠定了量子密码学的基础——彼时更无人能料到，联合国会宣布2025年为国际量子科学与技术年，国际计算机学会（ACM）终将图灵奖（Turing Award）授予他，以表彰其在这一领域的开创性贡献。

Gilles Brassard 教授同时是量子隐形传态的发明者之一，该技术是量子信息理论中最根本的支柱之一。他是伦敦皇家学会会士、加拿大勋章和魁北克国家勋章获得者，曾荣获沃尔夫物理学奖（Wolf Prize in Physics）、墨子量子奖（Micius Quantum Prize）、BBVA 基金会基础科学前沿知识奖（BBVA Foundation Frontiers of Knowledge Award in Basic Sciences）、基础物理学突破奖（Breakthrough Prize in Fundamental Physics）以及图灵奖等多项国际顶级荣誉。他先后获得苏黎世联邦理工学院、渥太华大学、卢加诺瑞士意大利大学及滑铁卢大学授予的名誉博士学位。