可计算数及其在判定问题中的应用
A. M. Turing。
[收到 1936 年 5 月 28 日。——宣读于 1936 年 11 月 12 日。]
“可计算”数可以简要地描述为：其十进制表示能够通过有限手段计算出来的实数。虽然本文表面上讨论的是可计算数，但定义和研究整变量或实变量、可计算变量的可计算函数，以及可计算谓词等，几乎同样容易。不过，在各种情形中所涉及的基本问题都是相同的，而我选择对可计算数作明确处理，是因为这样所需的技术最为简洁。我希望不久后能说明可计算数、函数等彼此之间的关系。这将包括用可计算数来表述实变量函数理论的发展。按照我的定义，如果一个数的十进制表示可以由一台机器写出，那么这个数就是可计算的。
在 §§ 9, 10 中，我给出一些论证，旨在说明可计算数包含所有通常可以自然地视为可计算的数。特别地，我证明了某些很大的数类是可计算的。例如，它们包括所有代数数的实部、贝塞尔函数零点的实部，以及数 等。