It seems very plausible that for any specific Turing machine M there is a fact of the matter about whether M would halt. We can just imagine running the experiment in an idealized world with an infinite future, and surely either it will halt or it won’t halt. No supertasks are needed.
This commits one to realism about Σ1 arithmetical propositions: for every proposition expressible in the form ∃nϕ(n) where ϕ(n) has only bounded quantifiers, there is a fact of the matter whether the proposition is true. For there is a Turing machine that halts if and only if ∃nϕ(n).
But now consider a Π2 proposition, one expressible in the form ∀m∃nϕ(m,n), where again ϕ(m,n) has only bounded quantifiers. For each fixed m, there is a Turing machine Mm whose halting is equivalent to ∃nϕ(m,n). Imagine now a scenario where on day n of an infinite future you build and start Mm. Then there surely will be a fact of the matter whether any of these Turing machines will halt, a fact equivlent to ∀m∃nϕ(m,n).
What about a Σ3 proposition, one expressible in the form ∃r∀m∃nϕ(r,m,n)? Well, we could imagine for each fixed r running the above experiment starting on day r in the future to determine whether the Π2 proposition ∀m∃nϕ(r,m,n) is true, and then there surely is a fact of the matter whether at least one of these experiments gives a positive answer.
And so on. Thus there is a fact of the matter whether any statement in the arithmetical hierarchy—and hence any statement in the language of arithmetic—is true or false.
This argument presupposes a realism about deterministic idealized machine counterfactuals: if I were to build such and such a sequence of deterministic idealized machines, they would behave in such and such a way.
The argument also presupposes that we have a concept of the finite and of countable infinity: it is essential that our Turing machines be run for a countable sequence of steps in the future and that the tape begin with a finite number of symbols on it. If we have causal finitism, we can get the concept of the finite out of the metaphysics of the world, and a discrete future-directed causal sequence of steps is guaranteed to be countable.
2 comments:
An odd skeptic with intuitionist tendencies could challenge this by denying that there is any fact of the matter about whether an arbitrary machine will never halt due to this being unprovable in general by finite means (per the Church-Turing Thesis and the undecidability of the halting problem). Perhaps mathematical truth should be equated with provability. This would fit well with the intuitionist rejection of LEM. Sometimes neither p nor ~p is provable, in which case (on this view) neither is “true.” If a (Turing) machine halts, it will do so in a finite amount of time. So, we can in principle prove that it will halt by finitistic means. But the same cannot be said of proving that a machine will not halt. So, such a skeptic might allow for facts of the matter about it being the case that a machine will halt but not about it being the case that a machine will not halt.
But here is a way that we can arguably reach at least Σ2 of the arithmetical hierarchy (which is where the halting problem is located). We can solve the halting problem using an infinity of provably halting machines. Suppose we are given an arbitrary Turing machine M with arbitrary input x. On day 1, we build a machine M1 that simulates M on x for 1 step. If M halts within 1 step, M1 will output 1 and halt. Otherwise, M1 will output 0 and halt. On day 2, we build a machine M2 that simulates M on x for 2 steps. If M halts within 2 steps, M2 will output 1 and halt. Otherwise, M2 will output 0 and halt. On day k, we build machine Mk that simulates M on x for k steps. If M halts within k steps, Mk will output 1 and halt. Otherwise, Mk will output 0 and halt. We do this for all k ∈ ℕ (which we can do with a countably infinite future). Every machine is guaranteed to halt and output either 0 or 1, and M will halt on x if and only if some machine will output 1.
If there is a fact of the matter about it being the case that each machine will halt (as there surely is and as even the skeptic should concede), then there is surely a fact of the matter about what each machine will output. After all, each machine writes its output just before halting. So, it seems like if the skeptic concedes that there is a fact of the matter about it being the case that the machines will halt, then there is a fact of the matter about whether M does not halt on x, since if each machine will output 0, then M will not halt on x after any finite number of steps, and this is just what it is for M to not halt on x simpliciter.
As I’m writing this, though, I am now suspicious about how much dialectical value (if any) this has over your original setup. For the output of Mk is determined by whether or not M will halt on x within k steps. But if there are facts about whether or not M will halt on x within k steps for any finite k, then we should simply be able to build M directly and run it on x and the facts about M not halting on x within k steps for any finite k should be sufficient to determine the fact that M will never halt on x.
In fact, I think the proof that Mk halts must rely on LEM.
Post a Comment