# 关于David Deutsch提出的“数学家的误解（mathematicians’ misconception）”的讨论

FOM（https://cs.nyu.edu/mailman/listinfo/fom）是一个讨论数学基础的论坛，汇聚了国际上计算机和数学领域的理论工作者，由Martin Davis（https://fr.wikipedia.org/wiki/Martin_Davis）主持。

1. FOM Digest, Vol 215, Issue 517 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

David Deutsch是在The Philosophy of Constructor Theory这篇文章中谈及可计算性时提出数学家的误解一说的（2.8 The computability of nature），David Deutsch提出自然的可计算性，说：自然的可计算性原则必须是，能够模拟任何物理系统的计算机也是物理上可行的。

• 可计算函数（或递归函数）是由停机的图灵机计算的函数。

• 可计算函数不一定是物理上可计算的，例如，如果其执行时间超过数十亿年。

Jose M. 问：在数学基础的框架中，David Deutsch数学家的误解的现状如何？

• 贯穿图灵论文的可计算序列（数）的概念从现有的计算理论中消失了；

• 现在的图灵机与图灵的计算机器之间存在着一些微妙差别：现在的图灵机完成对一个实例的计算而停机无限长的纸带被解读为无限的内存；而图灵的计算机器完成对一个实例的计算，然后回到初始状态，不停机继续计算下一个实例。

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. FOM Digest, Vol 215, Issue 517 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:

- 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).

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.

[3] J. Gorard, "Some Relativistic and Gravitational Properties of the

Wolfram Model," Complex Systems, 29(2), 2020 pp. 599?654.

[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.

[*] See for example https://cstheory.stackexchange.com/a/4838 and

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.

4. FOM Digest, Vol 215, Issue 8 21 Nov 2020

Sam Sanders

Lew Gordeew saidActually 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.

6FOM 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 …

7. FOM Digest, Vol 215, Issue 11 25 Nov 2020

Joe Shipman

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).

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.

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.

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.

http://wap.sciencenet.cn/blog-2322490-1260167.html

## 全部精选博文导读

GMT+8, 2021-11-28 22:34