1936年11月30日出版的《伦敦数学学会会刊》，有一篇标题看来平平无奇的文章︰〈论可计算数及其在判定问题上的一个应用〉，作者是图灵。
2012年，图灵诞生100周年，学界将该年订为「图灵年」，举办活动以纪念其重大贡献。2014年电影
《模仿游戏》也讲述了图灵于
二战时协助破解德军密码的故事（虽然忽略了
波兰数学家的贡献），相信不少人对图灵的名字、贡献及其因同性恋倾向被迫害的经历略有所闻。
图灵的众多贡献当中，最为重要的正是1936年这份论文，因为在文中他首次提出「
图灵机」这个概念——文中他称为a-机器，a代表「自动」（automatic）——为现代计算机、
计算机科学及计算理论奠下数学基础。
当然，除图灵以外，他之前及之后均有不少人对计算机发展贡献良多。不过在这篇文章，让我们先看一看他的「图灵机」为何如此重要。
数学基础
一切源自一个貌似非常奇特、与计算机毫不相干的问题︰我们如何确定数学知识可靠？
19世纪，数学发展越来越抽象，因此亦出现了各种公理系统——公理是指被视作「不证自明」的命题，数学家以公理为基础，再用逻辑推论出不同数学定理。但到了20世纪初，有批数学家（以及关心数学的哲学家）开始担心数学知识不够稳固，他们想确保由特定公理出发时，不会推论出现矛盾——假如有矛盾的话，数学就完了。
他们不是杞人忧天，当时集合论中出现了数个悖论（指一种导致矛盾的命题），或许会导致数学出现矛盾。幸运的话，有些悖论可以透过引入新概念去解决，例如自数学界出现「极限」的严格定义后，甚少人会认为「阿基利斯永远无法追上乌龟」的
芝诺悖论是个问题。
那个时候这批数学家大概分成三派，其中一派是数学家
主导的「
形式主义」。简略来说，形式主义者希望藉由把数学还原成纯粹符号的形式系统，再用（有限制的）数学去证明这个系统不会出现「0=1」之类的矛盾句，从而确保数学不会产生矛盾。
罗素及怀海德三大册
《数学原理》，则是从逻辑主义出发，尝试以逻辑公理推导出整个数学系统——他们想的是，既然逻辑不可能自相矛盾，只要证明数学是由逻辑延伸出来，就可以确保数学一致。
两人终告失败（原因并非本文重点），不过书中改良自弗雷格（Gottlob Frege）的逻辑系统，促进了数理逻辑发展。其后逻辑学家整理出一套现称为「一阶逻辑」的系统，包含若干逻辑公理和推导规则，由此出发可以推导出不少已知的逻辑定理，是个很好用的系统。
判定问题
回到
希尔伯特，他想完全将数学化约成一个仅有符号的形式系统（这方面罗素及怀海德贡献了不少），只要按照规则，完全不懂数学、不知道符号意义的人也可以推演出「数学定理」，这样就可以撇除人为错误（例如受直觉误导）。
他又希望找到一套清晰的判定程序，去确认如何判断一个逻辑公式是否属于逻辑系统的定理，假如成功，下一个目标自然是判断数学命题是否数学定理——这样数学家就不用再苦苦思索那些悬而未决的数学猜想，只要一起运行这个「判定程序」，就可以获得答案，简单直接。
不过，希尔伯特于1928年提出的这个「判定问题」，在1935至1936年期间，分别由数学家邱奇及图灵先后得出答案︰不可能。
要解决判定问题，首先需要厘清一个概念︰何谓「清晰的判定程序」？当然，有一些条件非常明显，例如程序必须是有限的——仅包含有限条规则、能够在有限时间完成。程序当中的规则也必须极之简单，以符合希尔伯特的要求。
举个例，假如我要教一位小学生判定一个数字以否
质数，可以利用他懂得「整数」、「除数」、「
余数」和「比较大小」等概念，去让他按照程序执行，然后他就会发现7是质数、8不是质数、9不是质数…
但希尔伯特所要求的还要更少——执行规则的人只能够辨认符号（不会把不同的符号混淆）、抄写符号、按照规则把符号串转换等，甚至不懂「加减乘除」等基本数学运算，也不会知道
数学符号的意思。
图灵机
终于回到图灵的论文，在〈论可计算数〉中他设想以下一部机器，包含以下部份︰
·一条纸带，这条纸带分成一格一格的（好吧听起来的确有点像厕所卫生纸），每格可以印一个符号。第一格的编号为0，然后是1、2、3…没有尽头，以 表示空格。
·可以在纸带上左右移动的读写头，它每次能够读取所处位置那一格的内容（同一时间只可读取一格），亦可以改变其内容——改写其他符号或变成空格。
·会存在机器目前状态（state）的状态缓存器，每部机器的可能状态数目有限，其中一个称为「开始状态」，就是机器一开始时所处的状态。
·储存所有规则的指令集，机器会根据其目前状态以及读写头当时读取的方格内容来执行指令，进行下一步动作。
上述4个部份当中，决定机器如何运作的是指令集及状态。为方便说明，以下机器的状态以颜色表示，而符号只有0、1及（空格）。图灵把指令限制在这个形式︰
·当处于A状态并读取到符号X时，写入符号Y，移动读写头，并转至B状态。
以下是一些例子︰
·当处于红色状态并读取到符号0时，写入符号1，读写头左移一格，并转至蓝色状态。
·当处于黄色状态并读取到符号1时，写入符号1（即维持原状），读写头留在原处，并维持在红色状态。
·当处于蓝色状态并读取到符号0时，清除符号（变成空格），读写头右移一格，并转至黄色状态。
如果没有适用的指令时，这部设想中的机器——后世称为图灵机——就会停止运作。
一个图灵机模型
不同图灵机分别，在于它们拥有不同的可能状态以及指令集——事实上，我们只需要看一部图灵机的指令集，就知道它可以有甚么状态，因此可以说，图灵机的指令集（以及一开始时纸带上的内容）决定了它如何运作。
这些看似非常简陋的图灵机其实可以做非常多事情，图灵在论文中举了两个图灵机作例子︰一个可以在纸带上不断印出「01010101….」，另一个可以印出「001011011101111...」。事实上，我们也能设计出会进行加法、减法、乘法、除法、比较两个数字大小…的图灵机（在图灵机中，数字可用符号「1」的数量来表示，例如用「111」代表3、「1111111」代表7，数字与数字之间则用符号「0」去分隔）。
通用图灵机
图灵的〈论可计算数〉没有在此打住，正如上文所述，一部图灵机的指令集可以抽述了它如何运作，因此图灵就想到把图灵机（的指令集）编码，换言之，用不同的数字就可以表述不同的图灵机——就这样，每个图灵机都获得一个标准编号。
下一步，图灵构造了一部特别的图灵机，称为「通用图灵机」。通用图灵机可以「扮演」不同的图灵机——只要输入某部图灵机M的标准编号，它就可以像M一样印出相同的符号序列。
如果上面的句子太过抽象，不妨换个（灵异一点的）说法︰有了通用图灵机以后，理论上我们不再需要制造其他图灵机——因为其他图灵机都可以由「硬件」变成「软件」，「附上」通用图灵机来运作。
对，那就是为何我们打开手机、计算机上的计算数件，便能够使用计算器的功能——现代计算机某程度上是一部通用图灵机（当然，计算机没有无限长的纸带）。通用图灵机成为现代计算机的理论模型，图灵这篇论文也奠定了计算机科学、可计算性理论等学科的基础。
当然，由纸上理论代为现实，中间还有一大段历史发展，图灵亦有参与，在此先行略过。（停机问题也是〈论可计算〉的重要结果，篇幅所限同样略过。）
邱奇—图灵论题
在图灵之前，数学家——特别是关心数理逻辑的数学家——已经在思考如何严格定义「机械程序」或者「算法」，因为缺乏这个定义的话，界定「形式系统」时会出现一个问题︰怎样的符号变换规则可以接受？
哥德尔（Kurt Gdel）在1931年证明其著名的
不完备定理时，引入了（原始）递归函数的概念，以便从数学角度讨论形式系统，其后他跟英年早逝的埃尔布朗（Jacques Herbrand）将之发展成广义递归函数。但要直到图灵的论文面世后，哥德尔才认为人们能「精确及毫无疑问充足」地定义形式系统。
文首提到比图灵稍早解决判定问题的邱奇，在他1936年的论文中使用了λ演算（λ-calculus）去地义何谓「λ可计算函数」。而对于任何（以
自然数为定义域的）函数f(x)，如果存在一部可以顺序印出f(0), f(1), f(2)…的图灵机，那么这个函数就称为「图灵可计算函数」。
邱奇和图灵证明了这三种函数——广义递归函数、λ可计算函数及图灵可计算函数——等价，换言之，虽然它们有非常不同的定义，但实际上还是一样。〈论可计算数〉发表以后，也有各种计算模型出现，但没有一个能够超越图灵机——它们所定义的函数，都是可以用图灵机（或λ演算、广义递归函数）去定义。
邱奇及图灵认为，任何可以计算的函数，都是λ可计算／图灵可计算函数，这称为「邱奇—图灵论题」。他们把「可以计算的函数」这个直观概念，跟数学上有严格定义的「λ可计算／图灵可计算函数」划上等号，由于论题涉及直观概念，本身无法以数学证明。
根据理论计算机科学这80年来的发展，邱奇—图灵论题几乎无人质疑︰即使计算机速度突飞猛进，能够完成各种以往无法想象的任务，现实中我们仍然未能找到一个超越图灵机的计算模型（理论上倒有一些，但不包括现时的量子计算机模型）。
未来发展会怎样？不知道，可能他日人工智能的数学家、逻辑学家会发现到一个超越图灵机的计算模型——而我们无法理解？或者明天就有人发现了？（当然我认为这不可能。）
没有〈论可计算数〉，我们也许还有「计算机」可用，但那些「计算机」应会截然不同，发展也慢得多。在图灵机面世80年后，我只想介绍一下这个对人类历史有深刻影响的故事。
看完本文有什么想说的吗？欢迎大家留言讨论哦~