FOM（https://cs.nyu.edu/mailman/listinfo/fom）是一个讨论数学基础的论坛，汇聚了国际上计算机和数学领域的理论工作者，由Martin Davis（https://fr.wikipedia.org/wiki/Martin_Davis）主持。
最近在讨论英国学者David Deutsch在文章“The Philosophy of Constructor Theory”（https://arxiv.org/pdf/1210.7439.pdf）中提出的“数学家的误解（mathematicians’ misconception）”。
我将部分内容翻译成中文与大家分享。
目录：
一，我们的发言
二，FOM关于David Deutsch"s claim about "mathematicians? misconception »的讨论
1. FOM Digest, Vol 215, Issue 5（17 Nov 2020）
2. FOM Digest, Vol 215, Issue 6 （18 Nov 2020）
3. FOM Digest, Vol 215, Issue 7 （19 Nov 2020）
4. FOM Digest, Vol 215, Issue 8 （21 Nov 2020）
5. FOM Digest, Vol 215, Issue 9 （23 Nov 2020）
6. FOM Digest, Vol 215, Issue 10 （23 Nov 2020）
7. FOM Digest, Vol 215, Issue 11 （25 Nov 2020）
一，我们的发言 - FOM Digest, Vol 215, Issue 11 （25 Nov 2020）
我想谈谈对David Deutsch关于“数学家的误解”议题的看法。
David Deutsch是在The Philosophy of Constructor Theory这篇文章中谈及“可计算性”时提出“数学家的误解”一说的（2.8 The computability of nature），David Deutsch提出“自然的可计算性”，说：自然的可计算性原则必须是，能够模拟任何物理系统的计算机也是物理上可行的。
所以一种可能的解读是，他认为现有的可计算性理论中存在着理论与实践脱节的现象，比如可计算函数不一定是“物理上可计算的”。
让我引法语wiki关于“可计算函数”总结性的一段话：
可计算函数（或递归函数）是由“停机”的图灵机计算的函数。
可计算函数不一定是“物理上可计算的”，例如，如果其执行时间超过数十亿年。
Jose M. 问：在数学基础的框架中，David Deutsch称“数学家的误解”的现状如何？
让我们追本溯源回到图灵1936年那篇奠基可计算性理论的论文《论可计算数及其在判定问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem），回想图灵是如何建立起“可计算性”概念的。
如果对比现有的“可计算性”与图灵的“可计算性”，不知你们是否注意到了二个现象：
贯穿图灵论文的“可计算序列（数）”的概念从现有的计算理论中消失了；
现在的“图灵机”与图灵的“计算机器”之间存在着一些微妙差别：现在的“图灵机”完成对一个实例的计算而“停机”，“无限长的纸带”被解读为“无限的内存”；而图灵的“计算机器”完成对一个实例的计算，然后回到初始状态，“不停机”继续计算下一个实例。
Dear FOM members,
I would like to share my opinions about the topic of mathematicians’ misconception due to David Deutsch.
David Deutsch made this claim in his paper The Philosophy of Constructor Theory when he talked about the computability (chapiter 2.8) [1], where he said :
The principle of the computability of nature must be that a computer capable of simulating any physical system is physically possible.
So a possible interpretation of mathematicians’ misconception is that, David Deutsch perhaps refers to phenomena in the current computability theory where theory and practice are out of touch, that is, a computable function is not necessarily physically possible, that is, physically computable.
Let me quote a similar commentary from the wiki in French [2] :
A computable function (or recursive function) is one computed by a Turing machine that halts .
A computable function is not necessarily physically computable, for example, if its execution time exceeds billions of years.
Jose M. asked : what could be the status of what David Deutsch calls the mathematicians’ misconception in the framework of foundations of mathematics?
Let us go back to Turing’s 1936 paper that laid the foundation for the theory of computability (On Computable Numbers, with an Application to the Entscheidungsproblem) to recall how Turing established the concept of computability.
I wonder to know if you have noticed that :
1, The computable number (sequence), a concept throughout Turing"s paper and even as a key word in the title of paper, has disappeared from the current computational theory;
2, There are some subtle differences between the current Turing machine and Turing"s computing machine : the current Turing machine finishes the computation of an instance of a problem and then halts , where the infinite tape is interpreted as unlimited memory for computing an instance; while Turing"s computing machine finishes the computation of an instance, returns to the initial state, and continues to compute the next instance without halting.
Best regards
Yu Li
Reference:
[1] https://arxiv.org/pdf/1210.7439.pdf
[2] https://fr.wikipedia.org/wiki/Fonction_calculable
[3] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
二，FOM关于David Deutsch"s claim about "mathematicians? misconception »的讨论
1. FOM Digest, Vol 215, Issue 5（17 Nov 2020）
Jose Manuel Rodriguez Caballero ：
Reading [1], I found the following claim, due to David Deutsch, about the relevance of the laws of physics in foundations of mathematics:
阅读文献[1]，我发现以下David Deutsch关于物理定律在数学基础中的相关性的主张：
- there was a widespread assumption -- which I shall call the mathematicians’ misconception -- that what the rules of logical inference are, and hence what constitutes a proof, are a priori logical issues, independent of the laws of physics.
有一个广泛的假设 - 我称之为“数学家的误解” - 逻辑推理的规则，由此构成的证明，是先验于逻辑问题，独立于物理定律的。
It is well-known that logical inference is formally rather similar to causality in spacetime, in the sense that both relations are reflexive, antisymmetric, transitive. Using this analogy it is possible to develop a common framework for special and general relativity on the one hand and proof theory on the other hand [3]. But even in this case, the logical inference is considered as independent of the laws of physics (mathematicians’s misconception according to David Deutsch).
众所周知，逻辑推理与时空中的因果关系在形式上类似，两种关系都是自反的，不对称的，可传递的。使用这种类比，一方面可以发展出一种狭义相对论和广义相对论的共同框架，另一方面发展出证明理论[3]。但是即使在这种情况下，推理被认为独立于物理定律（根据David Deutsch的说法，mathematicians’s misconception）。
Rather close to David Deutsch"s approach was William Rowan Hamilton’s proposal [4] that Algebra is the science of pure time [2]. Indeed, Hamilton defined the real numbers of ratios of steps between moments of time and derived some properties of the real numbers in this way.
与David Deutsch的方法更接近的是William Rowan Hamilton的提议[4]，认为代数是纯时间的科学[2]。的确，Hamilton定义时刻与时刻之间步数比的实数，通过这种方式得出实数的一些属性。
What could be the status of what David Deutsch calls the “mathematicians’s misconception” in the framework of foundations of mathematics? Could be in the same category as Platonism, Formalism, and Intuitionism?
David Deutsch所说的“mathematicians’s misconception”在数学基础框架中是什么状况？与柏拉图主义，形式主义和直觉主义属于同一类别吗？
References:
[1] Deutsch, David. "Constructor theory." Synthese 190.18 (2013): 4331-4359.
URL =
http://constructortheory.org/portfolio/the-philosophy-of-constructor-theory/
[2] Ohrstrom, Peter. "WR Hamilton"s view of algebra as the science of pure
time and his revision of this view." Historia Mathematica 12.1 (1985):
45-55.
URL = https://www.sciencedirect.com/science/article/pii/0315086085900679
[3] J. Gorard, "Some Relativistic and Gravitational Properties of the
Wolfram Model," Complex Systems, 29(2), 2020 pp. 599?654.
URL = https://www.complex-systems.com/abstracts/v29_i02_a03/
[4] William Rowan Hamilton, "Theory of Conjugate Functions, or Algebraic
Couples; with a Preliminary and Elementary Essay on Algebra as the Science
of Pure Time." Transactions of the Royal Irish Academy, volume 17 (1837),
pp. 293-422.
URL =
https://www.maths.tcd.ie/pub/HistMath/People/Hamilton/PureTime/PureTime.pdf
2. FOM Digest, Vol 215, Issue 6 （18 Nov 2020）
Tim :
Very interesting...thanks for mentioning this.
The following link might work better:
https://arxiv.org/pdf/1210.7439.pdf
To quote a little bit more:
The theory of computation was originally intended only as a mathematical technique of studying proof (Turing 1936), not a branch of physics. Then, as now, there was a widespread assumption---which I shall call the mathematicians" misconception---that what the rules of logical inference are, and hence what constitutes a proof, are a priori logical issues, independent of the laws of physics. This is analogous to Kant"s (1781) misconception that he knew with certainty what the geometry of space is. In fact proof and computation are, like geometry, attributes of the physical world. Different laws of physics would in general make different mathematical assertions provable. (Of course that would make no difference to which mathematical assertions are *true*.) They could also make different physical states and transformations simple---which determines which computational tasks are tractable, and hence which logical truths can serve as rules of inference and which can only be understood as theorems.
计算理论最初仅旨在作为一种用于研究证明的数学技术（Turing 1936），而不是物理学的一个分支。然后，现在存在一个广泛的假设（我将其称为“数学家的误解”），即逻辑推论的规则，因此构成的证明，先验于逻辑问题，与物理定律无关。这类似于康德（1781）的误解，他确定自己知道空间几何。实际上，证明和计算就像几何一样，是物理世界的属性。不同的物理定律通常会使可计算函数不同，因此数学证明不同。 （当然，对数学命题的正确性没有任何区别。）它们还可以使不同的物理状态和转换变得简单-确定哪些计算任务是易处理的，因此哪些逻辑真理可以用作推理规则，而哪些只能被理解为定理。
I don"t feel like dissecting Deutsch"s view in detail here---I have voiced objections to similar ideas in the context of discussions of hypercomputation [*]---but will just say that the misconceptions seem to me to be on Deutsch"s part and not on the mathematicians" part. If we want to attach an "ism" then I would attach it not to the "mathematicians" misconception" itself, but rather to Deutsch"s own misconceptions; I"d propose the term "Deutschism" since I don"t think his views on this point are widely shared.
我不想在这里详细剖析Deutsch的观点 — 在讨论hypercomputation中我已经表达了反对类似的观点 —但对我来说，误解似乎在Deutsch那，而不是在数学家那。要是我们想要加一个“主义”，那么我就不加“数学家的误解”上，而是加到Deutsch自己的误解上；我会提出“Deutschism”一词，因为我不认为他的观点能被广泛认同。
[*] See for example https://cstheory.stackexchange.com/a/4838 and
https://cs.nyu.edu/pipermail/fom/2004-February/007932.html
3. FOM Digest, Vol 215, Issue 7 （19 Nov 2020）
Lew Gordeew ：
In support of Tim"s opinion, recall that (even in propositional logic) there is no general consensus on "what the rules of logical inference are". After all, apart from classical model of inference (implication) there are other ideas coming from non-classical logics -- from minimal and intuitionistic to modal and fuzzy (and even paraconsistent) ones.
Analogously there are different ideas about "what constitutes a proof". Proof theory is treated differently by math. logicians and its modern versions are virtually unknown to most experts on the laws of physics. Actually it"s the other way around -- apparently the laws of physics are derived from earlier, abstract mathematical concepts of inference.
支持Tim的观点，请记住（即使在命题逻辑中）关于“什么是逻辑推理规则”没有普遍共识。毕竟，除了经典的推论模型（implication）还有其他想法来自非经典逻辑-从最小直觉到模态模糊（甚至paraconsistent）的模态。
类似地，关于“什么构成一个证明”有不同的观点。证明理论有数理逻辑学家不同处理，对于大多数物理学定律的专家来说，几乎不了解它的现代版本。其实是另一回事-显然是物理学源于早期的抽象数学概念推理。
4. FOM Digest, Vol 215, Issue 8 （21 Nov 2020）
Sam Sanders：
Lew Gordeew said, Actually it"s the other way around -- apparently the laws of physics are derived from earlier, abstract mathematical concepts of inference.
Lew Gordeew说，实际上，是另一回事 - 显然物理定律源于早期关于推理的抽象的数学概念。
That sounds a little exaggerated: what abstract concepts of inference were at the basis of e.g. quantum mechanics or relativity? What concepts did Newton base himself on?
这听起来有点夸张：推理的抽象概念是如量子力学或相对论的基础？ 牛顿以什么概念为基础？
Zitat von Sam Sanders :
Well, consider Aristotle"s syllogism BARBARA:
好吧，考虑亚里斯多德的三段论 ：
All objects fall down.
Apple is an object.
Therefore, Apple falls down.
所有物体会掉落。
苹果是一个物体。
因此，苹果会掉落。
Similar inferences are used in natural sciences while seeking for general laws in the material world. As well as in logic and
mathematics (re: formulas) ever since ancient times, thus prior to Newton. Also note that many abstract mathematical objects are more sophisticated than "real" objects currently investigated in physics or elsewhere in natural sciences.
类似的推论用在自然科学中寻求物质世界中的一般规律，甚至从远古时代开始，在牛顿之前，在逻辑和数学（关于公式）中也是如此。还要注意，许多抽象数学对象比目前在物理学或自然科学中研究的“真实”物体更复杂。
5. FOM Digest, Vol 215, Issue 9 （23 Nov 2020）
Mikhail Katz：
Arguably, Newton wasn"t specializing via the Barbara syllogism, but on the contrary generalizing by means of induction (in its generic sense) FROM apples TO objects.
可以说，牛顿不是通过三段论来研究具体的，相反是通过归纳（一般意义）从苹果到对象进行概括的。
6，FOM Digest, Vol 215, Issue 10 （23 Nov 2020）
Sam Sander：
Actually it"s the other way around -- apparently the laws of physics are derived from earlier, abstract mathematical concepts of inference.
That sounds a little exaggerated: what abstract concepts of inference were at the basis of e.g. quantum mechanics or relativity? What concepts did Newton base himself on?
Well, consider Aristotle"s syllogism BARBARA:
All objects fall down.
Apple is an object.
Therefore, Apple falls down.
Similar inferences are used in natural sciences while seeking for general laws in the material world.
One could perhaps make a case for this in principle. In practise, it goes a little more like this: 原则上，也许有人会为此提出这样的情况。 实际上，它更像这样：
The fundamental procedure of the natural science seems to be to formulate theories which are then tested against experimental data. If the data are consistent with the predictions, this counts towards the theory being (more) reliable. If the data contradicts the theory, the latter needs adjustment (or rejection in worst case). What and where adjustment (or rejection) is needed is part of the “magic” of science and will never be cast into logical rules (in my opinion).
自然科学的基本过程似乎是形式化理论，然后针对实验数据进行检验。 如果数据与预测相符，则该理论可认为（更可靠）。 如果数据与理论相矛盾，则后者需要调整（或在最坏的情况下拒绝）。 什么需要在什么地方进行调整（或拒绝）是科学的“魔术”的一部分，（我认为）永远不会被套成逻辑规则。
As well as in logic and mathematics (re: formulas) ever since ancient times, thus prior to Newton. Also note that many abstract mathematical objects are more sophisticated than "real" objects currently investigated in physics or elsewhere in natural sciences.
This greatly depends on what you mean by “sophisticated”:
这在很大程度上取决于您“复杂”的意思：
On one hand, infinite objects have nice closure properties, allowing for a nice, smooth, and elegant theory.
一方面，无穷大的对象具有良好的闭合特性，从而可以实现美观，流畅和优美的理论。
Bigger and bigger infinite structures can be build, with ever more complicated properties.
可以构建更大的具有更复杂的属性的无限结构。
On the other hand, if by “sophisticated” one would mean “mirrors the physical world”, the math shall become very finite and very messy rather quickly.
另一方面，如果用“复杂”来表示“镜像物理世界”，则数学将变得非常有限且非常混乱。
Lew Gordeew：
What I kept in mind is a more sophisticated treatment of infinity. In the set theory we consider infinite inner models, ordinals and cardinals, etc. Where are physical counterparts? They consider only plain, pre-Cantor, infinity of the space-time. My naive question: what is beyond black holes? Maybe something comparable to ordinals beyond omega? Or take proof theory. There are infinite ordinals, too. For example what could be physical evidence of Friedman"s generalization of Kruskal theorem that deals with simple physical objects like finite trees labeled with natural numbers (which also are easily interpretable in a finite physical world). We know that logical proofs require infinite ordinals …
我牢记的是对无穷大的更复杂的处理。 在集合论中，我们考虑无限的内部模型，序数和基数等。物理对应物在哪里？ 他们只考虑pre-Cantor之前时空的无穷大。 我的天真问题：黑洞之外还有什么？ 也许可以和欧米茄以外的普通东西相提并论吗？ 或采用证明理论。 也有无限的序数。 对于例如，弗里德曼（Friedman）推广Kruskal定理的物理证据是什么，该定理涉及简单的物理对象，例如标有自然数的有限树（在有限的物理世界中也很容易解释）。我们知道逻辑证明需要无穷序数…
7. FOM Digest, Vol 215, Issue 11 （25 Nov 2020）
Joe Shipman：
Most of this discussion seems to miss what I find interesting about this.
大多数讨论似乎都错过了我认为感兴趣的地方。
Deutsch doesn?t distinguish between logic and mathematics here:
that what the rules of logical inference are, and hence what constitutes a proof, are a priori logical issues, independent of the laws of physics.
Deutsch在这里没有区分逻辑和数学：
- 逻辑推论的规则，因此构成的证明，是与物理定律无关，先验于逻辑问题的。
On one hand, one feels that what a human will accept as a valid argument is partly an issue of language and convention and partly an issue of a priori abstract thought, in neither case depending on the laws of physics beyond the minimal structure necessary to support the existence of minds and of physically instantiated symbolic expressions.
一方面，人们认为，人类所接受的有效论证，部分是关于语言和惯例的问题，部分是关于先验抽象思想的问题，在二种情况下都不取决于物理定律，除了需要支持思想存在的最小结构，也不取决物理实例化符号表达的定律。
On the other hand, given that humans will accept as valid machine-generated proofs far too large to be humanly surveyable, depending on their understanding of the laws of physics to gain confidence that the machine performed as designed, the theoretical possibility of checking such a proof by hand seems no longer to be essential. One can imagine experimental verification of mathematical statements following from the axioms of a physical theory, without there being an algorithm to correctly generate such statements (for example, if some measurable dimensionless quantity had a value that was a definable but not a recursive real).
另一方面，鉴于人类会接受太大而无法人类验证（surveyable）的有效机器生成的证明，这取决于他们对物理定律的理解，从而获得对机器按设计方式执行的信心，因此用手（by hand）检查这种证明的理论可能性似乎不再是必不可少的。可以想象根据物理理论的公理对数学陈述进行实验验证，而没有一种算法可以正确生成这样的陈述（例如，如果某个可测量的无量纲量的值是可定义的，但不是递归实数）。
My view is that these are both valid ways of looking at it, the difference turning on the definitions of the terms ?inference? and ?proof?. The second viewpoint seems to be expanding the definition of ?prove? to mean ?obtain knowledge of with the highest achievable degree of scientific or practical certainty?, but I would rather adjust terminology and talk about ?demonstration? or ?verification? rather than ?proof?, and ?inductive? or ?scientific? rather than ?logical? inference.
我的观点是，这是二种看待的有效方法，区别在于术语“推理（inference）”和“证明（proof）”。 第二个观点似乎是在扩展“证明（prove）”的定义，意思是“获得具有最高科学或实践确定性的知识”，但是我宁愿调整术语并谈论“示范（demonstration）” 或“验证（verification）”， 而不是“证明（proof）”和“归纳（inductive）” ，或者“科学（scientific）”而不是“逻辑（logical）”推理。
With these distinctions established, the problem goes away as far as logic is concerned. But an issue remains for mathematics, because some mathematics is manifestly not related to scientific theories of any types ever usefully developed (CH and AC being obvious examples, Borel Determinacy being perhaps a better example). One may sidestep this by taking a formalist attitude and only talking about proofs from axioms in a formal language with the usual nice properties, but one would like to talk about whether a mathematical statement is ?provable? informally without specifying an axiomatic system, using my second, broader sense which can also be rendered as ?demonstrable? or ?knowable? or ?verifiable?. It may be a genuine and contingent property of our-universe -as-we-are-capable-of-experiencing-it that CH is simply *not knowable*, while universes with different constitutions might have such phenomenological plenitude that there would be a way in which its beings could come to *know* whether CH is true in a way that we can’t.
建立了这些区别之后，就逻辑而言，问题就消失了。但是在数学上仍然存在问题，因为某些数学显然与任何有用的科学理论都不相关（CH和AC是明显的例子， Borel Determinacy也许是更好的例子）。可以采取一种形式主义的态度来回避这一问题，只谈论具有一般惯用属性的形式语言中的公理证明，但有人想谈一谈数学陈述是否非正式可证（provable），不指定公理系统，使用我的第二种更广泛的意义，呈现为demonstrable，knowable，verifiable。这可能是关于我们可以经验的宇宙的真正和或然的属性（genuine and contingent property），CH只是简单的“not knowable”，然而具有不同构成的宇宙可能具有如此丰富的现象，以至于存在一种方式“知道（know）” CH是否为真，但是我们不能。
In this last way of looking at it, the laws of physics have something important to say about what is mathematically knowable, and therefore maybe about the logical concepts of inference and proof too, despite my earlier distinctions which tried to get rid of the issue.
用最后一种方式来看，物理定律对于数学上可知的东西还有重要的话要说，因此也可能关于推理和证明的逻辑概念，尽管我较早做了试图解决这个问题的区分。
