In a recent thread, commenter Eric Holloway links to an article in which he claims to have proven that halting oracles are logically possible.
The one-page article can be found here:
I’ve taken a look at the article, and the proof contains a blatant circularity. That is, it assumes that halting oracles are possible in order to demonstrate that they are possible.
Eric’s proof depends on the construction of an infinite table (which he calls an ‘index’, for some reason) containing an entry for every possible finite Turing machine. The entry includes a specification of the machine in question and a “halting status” that indicates whether the machine halts or runs forever.
Another machine (the “search machine”) is set up that can search through the infinite table to find any particular finite state machine. If it finds a match, it returns the associated halting status. The search machine together with the infinite table thus constitute a halting oracle, according to Eric.
The problem is simple: To populate the infinite table, you need to know the halting status of each finite machine, and to get the halting status, you need a halting oracle. Eric thus assumes the logical possibility of a halting oracle in order to prove the logic possibility of a halting oracle.
It’s plainly circular.
There are additional problems with the article that we can discuss in the comment thread.
Yes, I agree. And thanks for starting this thread.
Don’t worry, folks, Eric Holloway gets a bit confused sometimes. One can be both an atheist & an IDist too, according to Eric H. As long as anyone can become an IDist, it doesn’t seem to really matter to him how that happens. http://appliedintelligentdesign.blogspot.com/2012/07/intelligent-design-and-atheism-are.html
So for infinity to be a logically possible concept does someone have to count out all the numbers first? I guess we can discard much of mathematics and the science that depends on it.
I think you misunderstand the concept of logically possible. It is not the same as physically possible. It just means free from contradiction. 2+2=5 is not logically possible. Married bachelors are not logically possible. Square circles are not logically possible. But there is no similar logical contradiction with the notion of infinity or the lookup table I describe.
Eric,
I understand the difference between logical and physical possibility.
Nothing in what you just wrote addresses the circularity I identified in your proof.
In mathematics, the word “infinity” is shorthand for a complex set of concepts. So talk whether infinity is a logically possible concept seems confused.
Your argument depends on enumerating Turing machines. And then you look at the proposition (or, really, the infinite sequence of propositions) “Machine N halts”. Your lookup table supposedly indicates whether those propositions are true or false.
But what if some (perhaps most) of those propositions are Gödel undecidable propositions (as shown possible by Gödel’s incompleteness theorem)?
Is it logically possible that undecidable propositions are decidable?
I don’t think this is a problem in Eric’s paper. I agree that there’s almost certainly no way to create such a list, and maybe that it couldn’t physically exist (if the universe turns out to be finite), but neither of those rules out the logical possibility of it existing (unless we find a proof that the universe logically must be finite).
But I do have a couple of objections to the paper. First, I don’t think it’s “commonly thought that halting oracles are logically impossible”, only that they’re impossible in practice (e.g. not allowed by physics). In fact, it’s generally assumed they are logically consistent, and their implications have been explored theoretically. You can define “oracle machines” consisting of a normal Turing machine augmented with a halting oracle; this defines a new class of problems “computable” on such an oracle machine. It can be shown (by trivial modification of Turing’s original proof) that these oracle machines can solve halting-like problems for normal Turing machines, but not themselves. So then you can define second-level oracle machines which are augmented with an oracle for the first-level-oracle-machine halting problem. It turns out they can solve the halting problem for regular Turing machines as well as first-level oracle machines, but not for themselves. You can (logically) add as many levels as you want, and you’ll always get something that can solve the halting problem for all lower-level oracle machines, but not for its own level (or anything higher).
So, the paper is trying to prove something that’s already widely accepted. But there’s a worse problem: it depends on a logical fallacy. It argues that a halting list is logically possible, and a search machine to find answers on such a list is logically possible, and “If neither component is logically impossible, then neither is their composition in the form of the search machine.” But two things being logically possible does not imply that their composition is. For a trivial example, consider “X = 1” and “X = 2”; either one is logically possible by itself, but if you put them together you get a contradiction.
So, I think the conclusion is correct, but the logic used to support it doesn’t work.
BTW, I should add a technical quibble about how the halting problem is defined. It’s sometimes defined as trying to decide if a particular Turing machine will halt, but that’s actually not well-defined, because whether a Turing machine will halt often depends on what it’s given as input (technically, what’s on the tape when it starts). The question is sometimes defined as whether a TM will halt given a blank tape as input, or given itself (in appropriate notation) as input, or pretty much any thing else you want to choose.
This turns out not to matter at all to its computability. Each of these variants of the halting problem would give different answers for particular Turing machines (and hence a different “index” in Eric’s paper), but all of the variants are Turing-reducible to each other. That is, they’re all essentially equal in difficulty; given an oracle for any of them, you can compute (on a Turing machine) answers for any of the other variants.
So, this doesn’t actually matter. Unless you really want to be rigorous, in which case you need to deal with these technical details.
I think you are right, Keith. We need something other thing a TM to compute the whether the nth TM will halt for given input, like the accelerated TMs I outline in my note in the other thread.
Here is a paper which carefully defines accelerated Turing Machines and deals with subtleties such as specification of their output versus their end state.
https://oronshagrir.huji.ac.il/sites/default/files/oronshagrir/files/do_accelerating_turing_machines_compute_the_uncomputable.pdf
ETA: This article is careful to define the halting problem as deciding whether TM n halts with given input data m.
But I believe Eric’s table is meant to be about all possible TMs with all possible inputs. That too would be countable, in the same way that the rational numbers are countable.
So does that imply that an ATM could fill in Eric’s table in a finite time? Or am I missing some subtlety. For example, the wiki article on halting oracles says
[start of quote]
Halting on all inputs
The universal halting problem, also known (in recursion theory) as totality, is the problem of determining, whether a given computer program will halt for every input (the name totality comes from the equivalent question of whether the computed function is total). This problem is not only undecidable, as the halting problem, but highly undecidable. […]
This means, in particular, that it cannot be decided even with an oracle for the halting problem.
[end of quote]
https://en.wikipedia.org/wiki/Halting_problem#Halting_on_all_inputs
Would that mean that Eric’s table could not be filled in even with a halting oracle?
If the proposition is of the form “Does any integer possess the property P” then it seems that yes, an Accelerated TM could always answer that question.
More generally, I have seen in many places the claim that the impossibility of solving the halting problem with a TM implies Godel’s results. Here is Scott A with a detailed description.
https://www.scottaaronson.com/blog/?p=710
But I am not sure what the existence of a halting oracle means for Godel’s results in general. Do you or anyone have any thoughts on that?
I think that’s right. Gödel’s proof and Turing’s proof both use the same kind of diagonal argument.
Maybe the question is not a proper one.
People tend to look at Gödel undecidable propositions in terms of non-standard arithmetic. Such a proposition might be true in some varieties of non-standard arithmetic but false in others.
Here, non-standard arithmetic is something that satisfies the Peano axioms but is different from the way that we normally think about arithmetic. For example, a non-standard arithmetic might have infinite numbers (numbers that are greater than all of the ordinary finite numbers.
No let’s suppose that we go about trying to build an actual Turing machine. This includes an infinite tape. Maybe the world is such that whenever we try to add an infinite tape, many other infinite tapes pop into existence, and we finish up with a non-standard Turing machine.
As far as I can tell, you cannot rule that out.
It is really a limitation of logic. Everything works fine as long as we stick to the finite. But once we want to allow the infinite, as in the infinitude of integers or in the infinite Turing tape, our intuition breaks down.
Gordon,
It’s still a problem in Eric’s article, because in it he specifies that we construct the list. It isn’t a found object:
You can’t construct the list without a halting oracle, so the circularity remains.
The theological assumption of IDism is likewise based on imago Dei theology. Thaxton, Bradley, Olsen, Johnson, Meyer, Behe, Nelson, et al. All carry the same theological assumption into their IDism, whether they’ll say it publicly or not.
We don’t need to trust IDists to tell the truth. They’ve tried to replace the circularity in IDism by refusing to identify the Designer, which they believe gives the imago Dei.
It’s a whipped, double-talking USAmerican religious trickster approach the IDists have taken. Going by the responses here, it’s working. = P
Bruce,
I think the answer is “no”. A single ATM could process an unbounded number of halting cases, but it would get stuck as soon as it reached a non-halting case.
However, you wouldn’t need Eric’s infinite table if you were just consulting your oracle for the halting status of a single program.
Gordon,
You cite halting oracle machines as proving the logical possibility of halting oracles, but a halting oracle machine requires a halting oracle that it can consult.
This looks like another circularity issue to me. The logical possibility of halting oracles is being assumed in order to demonstrate the logical possibility of halting oracles.
Keith, I’m not claiming that oracle machines prove the logical possibility of halting oracles. What I was primarily claiming is that Eric’s initial statement, “It is commonly thought that halting oracles are logically impossible,” is wrong. Over on the “Demise of ID” thread, Eric said that was “Entirely due to the conversation over at PS where Swamidass ‘proved’ halting oracles are not logically possible due to a butchered version of the halting argument.” What the theoretical work on oracle machines shows is that Swamidass is on his own here, and is going against a lot of theoretical work that hasn’t found any contradictions based on the assumption of halting oracles.
Actually, I’ll go further than that: If Swamidass’ “proof” is equivalent to the argument Eric summarizes in paragraphs 2-4, then Eric’s objection to it is correct: it only applies to Turing machines and other Turing-equivalent computing devices.
Concerning the point that Eric’s argument “specifies that we construct the list. It isn’t a found object.” I don’t think this is quite correct; he doesn’t talk about constructing the list, just constructing an oracle using the list. But I agree that this isn’t the best way to approach it. Talking about constructing something out of materials you probably have around the home is one thing; talking about constructing something out of materials that probably don’t (/can’t) exist in our universe is something else.
Anyway, as far as I can see it’s pretty irrelevant. Swamidass’ proof appears to be wrong, there’s no good reason to think halting oracles are logically impossible, and we don’t need a proof that they’re logically consistent to talk about them.
Gordon,
Take a closer look at the sentence I highlighted:
He’s adding an entry to the list for each Turing machine, which surely qualifies as constructing the list.
Either way, the proof is still circular.
Right, and so here is one possibility to address that:
– define an enhanced ATM which also has a defined “ready for next” state it reaches when a single value h(n, m) has been computed., where h(n,m) is the halting function for TM n, input m.
– when it reaches that “ready for next” state, its next computation takes 1/2 as long (eg for second computation, total time is 1/2 + 1/4 + 1/8+…).
– give it two tapes, one for normal use, one to record the table
– have it go through all possible ordered pairs h(n.m).
After 4 time units, the table should be filled in.
There may very well be logical contradictions in this. For example, as per our discussion in the other thread, specifying a state for the machine at the end of each “infinite” computation is problematic. (See related Supertask discussion at SEP). But there are papers cited in the pdf I link above which do attempt to define such machines, so I am guessing it is not a logical contradiction at least according to these authors. I have not read any of those papers.
I linked to his proof in the other thread. It’s just a proof that TMs cannot solve the halting problem. But of course that is irrelevant to the discussion about whether a logically possible entity could.
But it is helpful to have an idea of how one could conceive of one without contradiction, such as the Accelerated TMs Keith and I have been discussing. See the Copeland and Shagrir paper I linked upthread.
ETA: Lacking something definite like that, some may complain that a halting oracle is logically inconsistent: a more sophisticated version of square circle.
After I wrote this post, I found the paper by Ord
The many forms of hypercomputation
(It’s available on SciHub via DOI search)
The paper includes the following description of a logically possible machine which does seem to be able to compute and record h(n, m) for all (n, m).
[start of quote]
“This process of using an infinite computation length can be extended. Joel Hamkins and Andy Lewis [21,20] have presented a model of a Turing machine that operates for a transfinite number of steps: an infinite time Turing machine. We could imagine, for instance, a machine that included an accelerating Turing machine (M) as a part. It could initiate M’s computation, then after two time units, stop M’ movements and reset M to its initial state, leaving the tape as it was at the end of the computation. It could then restart M with its tape head on the first tape square, running it for another two time units. In such a manner, this machine would perform two infinite sequences of steps in succession. One could even imagine a succession of infinitely many restarts, with M performing the whole sequence twice as fast each time, leading to an infinite sequence of infinite sequences of steps.”
Bruce,
The problem is that the ATM never reaches a point, in the non-halting case, where it knows that a value has been successfully computed. As far as it’s concerned, the program is still running and might still halt, so any transition to the “ready for next” state would be premature.
I think the information has to come from outside, in the form of a signal indicating that two units of time have elapsed. But that signal would be effectively the same as Ord’s reset signal.
Eric fancies himself a great explainer, but he regularly makes a mess of things with his indifference to formal definitions and other “little details.” He hasn’t given, and does not claim to have given, an effective method for deciding the truth or falsity of the propositions. His infinitary machine has the truth values of the propositions by definitional fiat. I know that Eric seems to suggest, in his description of the machine, that we can construct the “index”:
Emphasis added. The “we can” is just bad writing. Eric has already argued (poorly) that the “halting status” is undecidable. Furthermore, his conclusion requires only that there be a logically consistent definition of the “index.” A reading in which Eric tries to establish more than is required for his conclusion is ungenerous.
Some other defects in Eric’s note:
1. The “proof” that the Halting Problem is unsolvable by any Turing machine is wrong. The gist of what’s wrong with it is that Eric confuses functions with Turing machines that compute functions. He also ignores the distinction of Turing machines and descriptions of Turing machines, but I wouldn’t say that the error is egregious.
2. Eric silently departs from the Halting Problem. He starts out correctly, addressing whether machine p halts on input i. But then he drops the input from consideration. His “index” should be defined in terms of a 1-to-1 correspondence of the set of positive integers and the set of all program-input pairs. [ETA: A program, in this context, is a Turing machine description.]
3. Eric is reinventing the wheel, and making a very bad job of it. There’s already a definition of an oracle tape, attributed to Soare in the Wikipedia article on oracle machines, that’s similar to, but more straightforward than, what he’s attempting with his “index.”
I know how things play out from here with keiths, so I will make no further comments on this thread. Why did I comment at all? I think my credibility suffers, with Eric at the very least, if I say nothing about the charge of circularity.
I never was able to track down something useful to me on the extra end state specifications machines mentioned in the C&S paper — one of the citations was a Master’s thesis at an Australian university. So I don’t know how they added that new state to the open-ended ATM definition C&S prefer.
But I agree that an external watchdog timer will do it. The transfinite machine that Ord cites is logically conceivable and so is sufficient to show that the full (n, m) table could conceivably be populated in finite time.
Maybe something simpler is all that is needed, though. Something like an external “semi-accelerated TM” which executes exactly two primitive operations at the initial rate of the current cycle of the ATM being watched.
Another idea is in the supertask SEP article I linked upthread ; it involves an idealized bouncing ball mechanism.
I took a quick look at Eric’s other article which he calls empirical in the other thread. I am not sure why he used that word in association with the math models it discusses. In my quick skim, I noticed idiosyncratic definitions of “genius” and “creative” and a conditional probability argument that uses the max entropy principle to quantify probabilities.
I’ve questioned Eric on that principle before, since it is meant to mandate use of the probability distribution that maximizes entropy using prior information. But in ID it seems to be used to justify an equal-probability distribution, regardless of known and applicable physical processes and constraints (cue Mike Elzinga ).
I’ll wait to see if Eric wants to explain that paper by commenting or OPing here before devoting more time to the paper.
I see what you are saying. Yes, the wording is not great. I’m not intending a literal construction of the list in this description. It is merely meant to illustrate to the reader what the list contains: an index, the corresponding turing machine, and its halting status.
Yes, I’m just creating the list fiat, not providing any details about its construction. I am not a fan of hypercomputation, since the idea of traversing an actual infinite series seems problematic. The only intent in the article is to illustrate the halting oracle is logically possible, in response to the halting problem argument at the beginning.
The fundamental issue is the halting problem argument most people are taught in CS class is a simplified form that gives the impression that halting oracles are fundamentally impossible, hence Swamidass’ error over at PS that motivated the article. The original argument by Turing is a diagonalization argument, and avoids the simplistic inference that halting oracles are impossible.
My article illustrates why this is the case, since the oracle itself cannot be an entry in its lookup table, as each entry is finite and the oracle is infinite.
Totally agree with this.
Yes the basic idea is the output of a TM with a halting oracle is different than one without when you pump random bits into the machine, so you can differentiate the two after the fact.
The maximum entropy principle is mostly to simplify the argument and illustrate the main point. Alternatively, I can go the CSI route and also apply things like probabilistic resources, tractability, and so on.
But, still the point remains is there is an empirically detectable difference between TMs with and without halting oracles allowing us to infer from observed phenomena the responsible cause. Thus, halting oracles provide one alternative to the ‘methodological computationalism’ of current science that is committed to purely computable and probabilistic descriptions of causes.
I don’t have time for lengthy involved argumentation, so cannot promise an OP on the article anytime soon. Hopefully my brief blurb here answers enough of your questions.
Thanks for the clarification, Eric.
I don’t agree with you on how science works in general and the nature of MN in particular.
I think you mentioned in the other thread that there was an empirical element to this paper, but I don’t see any practical experiment there, as has been discussed by many in the other thread.
By ’empirical’ I mean two things can be distinguished by physical measurements.
I very much appreciate your comment. My opinion has changed, and now I no longer think you are only trying to cast ID in a bad light every opportunity you get. Most of the time, but not all the time 🙂 You have my respect as a man of principle!