1

Consider the following thesis (aka Church-Turing (CT) Thesis): Every function that can be calculated by an effective method is Turing-computable.

Suppose there is a physical process that allows for the calculation of functions not computable by any Turing machine ("Physical process” is any process that is in accordance with the actual laws of physics). Would the existence of such a process refute the Church-Turing Thesis?

My idea: If the process provides an effective method, then it refutes the CT thesis by definition. Otherwise, not necessarily. But the existence of such a physical process is granted by some advanced exotic physics. Any insights?

4
  • 1
    As usual, you have to look at the exact details of the claim and the exact definitions used. The thesis is more of a definition than an attempt at describing any fact, so it it probably immune to your argument.
    – Frank
    May 7, 2023 at 2:36
  • 1
    Analog computers are likely the closest such thing to your "physical process". See, e.g., cs.stackexchange.com/questions/35343, and you can continue googling further discussion from there. May 7, 2023 at 4:21
  • 4
    I am curious as to what the "advanced exotic physics" might be and what "effective method" it provides that cannot be emulated by a Turing machine? As far as I know, all that (known) exotic physics does so far is reduce time complexity of computations (as in prime factorization by quantum computers), it does not make the uncomputable computable. Also, "effective method" is rather ambiguous. Turing allowed, for example, that human brain might be capable of something that a Turing machine is not, but whatever that might be it would not be a "mechanistic procedure" he intended to formalize.
    – Conifold
    May 7, 2023 at 5:14
  • I've just made the title more specific by including the on-going philosophical literature in systems of physical computation(SEP) which defines computers as a property-dualistic artifact instead of a mere set-theoretic abstraction. Great philosophical question, btw. I recommend Shagrir and Piccinini's books for more nuanced philosophical material.
    – J D
    May 9, 2023 at 19:02

3 Answers 3

1

The phrasing itself implies that there may exist functions that can be calculated, can't be calculated by an effective method, and aren't Turing-compatible, otherwise there's no need for the qualifier "by an effective method". If you're sure you have the right expression of the thesis, then insofar as calculation is a wholly contained subset of physical processes, the answer must be "No," with no need to examine any physical processes or even the definitions of the terms used.

3
  • If we discovered processes that weren't physical, we would probably just expand the definition of 'physical' to include them. This is partly why the debate about Determinism is hopeless.
    – Scott Rowe
    May 7, 2023 at 11:48
  • By a diagonal argument, there must indeed be functions not computable by an effective method. As for the second part, I don't quite see how this inclusion helps us answer the question.
    – Johan
    May 7, 2023 at 13:39
  • @ScottRowe I don't know about expanding the definition of physicalism. Physics, chemistry, and biology, the hard sciences, are very thoroughly understood at this point. The real question is what to do with processes that aren't empirical, but seem clearly linked to the physical. A probabilistic wave function, for instance. I don't see any "processes" that aren't covered under the same class.
    – J D
    May 9, 2023 at 19:32
1

Suppose there is a physical process that allows for the calculation of functions not computable by any Turing machine ("Physical process” is any process that is in accordance with the actual laws of physics). Would the existence of such a process refute the Church-Turing Thesis?

Not necessarily. Because the Church-Turing thesis is about what kinds of machines humans are able to engineer. If there is a physical process that does something uncomputable by a Turing machine, it doesn't refute the Church-Turing thesis unless humans can also harness that process to find answers to computational questions (that a Turing machine can't answer).

For example, space and time may be continuous (a.k.a. "infinite precision"), which might make physics beyond a Turing machine's ability to calculate, since a Turing machine must always deal with some finite number of digits. But if humans can't ever perfectly measure those continuous values, even in principle, then the Church-Turing thesis is not refuted.

0

According to WP:

[The Church-Turing thesis] states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

Important in this definition is that the functions are on the natural numbers, and this is important, because computability and Turing machines are related to arithmetization very strongly, which relates to the topics like arithmetization of analysis (encyclopediaofmath.org) and reverse mathematics. In fact, if you've done coursework in language and automata, you'll know that alphabets and strings constructed from them are all sequences, and mathematically, a sequences is a mapping of any symbols to the naturals. Thus, the naturals, languages, and Turing machines which serves as a mathematical model for computability are all interrelated.

Suppose there is a physical process that allows for the calculation of functions not computable by any Turing machine... Would the existence of such a process refute the Church-Turing Thesis?

SO, the answer to your question is a qualified yes, and it is easy to see because in the definition cited the biconditional operator (IFF) is used, and therefore where you have a system modeled by a Turing machine, then you have a system of physical computation (SEP). Deterministic TMs and probabilistic TMs are great for determining deductive proofs and stochastic systems, resp. Non-deterministic TMs as an even larger class, which likely excludes quantum computer systems in theory since they can be restated in terms of deterministic TMs (QMSE) by simply reformulating complexity requirements, still seems to encompass every known physical system. This correspondence can be taken as a metaphysical necessity (SEP) such as a view held by Piccinini:

The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the physical Church–Turing thesis states: "All physically computable functions are Turing-computable."

So, the class of formalisms related to TMs seems to encompass all traditional notions of computation (as differentiated from pancomputationalist computation) and if suddenly, a physical process were discovered, say in some new theory of quantum gravity, that would, based on the definition invalidate the equivalence between the LHS (functions on naturals) and RHS (TM) by showing they're not equivalent, that there is some physical system that a Turing Machine of some form can't model.

BUT, it's hard to imagine what a physical system that can't be arithmetized in some form would be. Arithmetic is built into our very systems of mathematical physics that undergird our theories of the physical. So, from a practical perspective, Piccinini's position is intuitively very secure, and it may be indication that the computer as a physical artifact, which encompasses both hardware and software, are evidence of some form of property dualism such as the position Chalmer's has put forth to square the magical relation between the physical (hardware) and the mental (software).

1
  • That's a shot from the hip. If you have an objection I didn't think of, by all means relay it so I might correct my response.
    – J D
    May 9, 2023 at 18:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .