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.