Monday, October 3, 2022

The Church-Turing Thesis and generalized Molinism

The physical Church-Turing (PCT) thesis says that anything that can be physically computed can be computed by a Turing machine.

If generalized Molinism—the thesis that for any sufficiently precisely described counterfactual situation, there is a fact of the matter what would happen in that situation—is true, and indeterminism is true, then PCT seems very likely false. For imagine the function f from the natural numbers to {0, 1} such that f(n) is 1 if and only if the coin toss on day n would be heads, were I to live forever and daily toss a fair coin—with whatever other details need to be put in to get the "sufficiently precisely described". But only countably many functions are Turing computable, so with probability one, an infinite sequence of coin tosses would define a Turing non-computable function. But f is physically computable: I could just do the experiment.

But wait: I’m going to die, and even if there is an afterlife, it doesn’t seem right to characterize whatever happens in the afterlife as physical computation. So all I can compute is f(n) for n < 30000 or so.

Fair enough. But if we say this, then the PCT becomes trivial. For given finite life-spans of human beings and of any machinery in an expanding universe with increasing entropy, only finitely many values of any given function can be physically computed. And any function defined on a finite set can, of course, be trivially computed by a Turing machine via a lookup-table.

So, either we trivialize PCT by insisting on the facts of our physical universe that put a finite limit on our computations, or in our notion of “physically computed” we allow for idealizations that make it possible to go on forever. If we do allow for such idealizations, then my argument works: generalized Molinism makes PCT unlikely to be true.


William said...

Perhaps "sufficiently precisely described" includes the value of n. Then the function is no longer infinite, since we stop at the time for n.

Walter Van den Acker said...

Molinism isn't true if indeterminism is true.

William said...

Can there be determinism in some things and indeterminism in others?

Walter Van den Acker said...


Yes, that's possible, but it doesn't save molinism.