Halting Oracles And Law of information Non Growth

Another side point: LoING seems to be the AIT version of the Rao-Blackwell theorem in statistics theory. Its very useful.

@dga471, looking over this thread again, I did not describe it precisely correctly. Rather than the proof of compressibility is uncomputable. Instead, this is example of an implementation that would work if and only if we had a complete halting oracle. This does not prove that all other implementations would fail too. Of course, all other implementations would fail, and we can prove this, but that is another poof.

Just to be sure I’m not propagating any errors here. I’m leaving this not of the framing error here, and going to fix the wording in the main post.

What these halting oracle implementations do is push all the illogical bits into the “halts” subroutine. This, however, is impossible in practice. Here is another algorithm that would produce an optimal compression, if we had a halting oracle, This one works by iterating over all possible self-extracting compression programs.

def optimal_compression(X):
  for i in 1 to infinity:
    for p in all programs of length ==  i:
      if halts(p): pass    #without this line, the function will never terminate
      if execute(p) == X: return p

This is another program, perhaps a little clearer than the first one I gave, that would be able to produce an optimal compression if we had a halting oracle. The proof that no algorithm is possible is a different proof. In a way, this is also a proof that halting oracles are logically impossible. If they weren’t impossible, the proof that compressibility is uncomputable would be incorrect.

Dr Swamidass:
I am puzzled by why you say oracles are logically impossible.

First, let me be very clear that I am not questioning your demonstrations that Turing machines cannot be used to implement oracles.

But for me, something is logically possible if we can reason consistently about it.

Of course, Turing himself invented oracles to help him reason about uncomputability. Scott Aaronson has a nice summary of his work in section 3 of this course excerpt.

Since then, the philosopher Jack Copeland and many others have explored oracles through his concept of hypercomputation. I’ve linked the Wikipedia article. It cites many papers on the topic.

So it seems to me that it is possible to reason consistently about oracles and hypercomputation, and therefore it is fair to say oracles are logically possible.

Are they physically possible in our universe? The SEP article on Computation in Physical Systems briefly considers that issue. It claims there is a slight possibility that they might be: “Relativistic hypercomputers exploit the properties of a special kind of spacetime called Malament-Hogarth spacetime, which is physically possible in the sense of constituting a solution to Einstein’s field equations for General Relativity. … The first question is whether our spacetime is Malament-Hogarth. The answer is currently unknown. Even if our spacetime is not Malament-Hogarth globally, it might still contain regions that have the Malament-Hogarth property locally.”


I think his intended point was that they cannot be constructed as logic machines. That’s a different meaning for “logically impossible”.

1 Like

Well, OK, but what is a logic machine? If it is equivalent to a Turing machine, then saying oracles cannot be logic machines is pointless, since that is true by definition of an oracle.

So are logic machines not equivalent to UTMs? (Wiki has an article on "logical machines"logics for computability but neither seems to go beyond UTMs).


@BruceS this is merely a reference to the proof that a total, complete halting oracles are uncomputable. They require some view of infinity in a finite machine. That is not possible:

That might seem a jump for you, but it is not for me. The hypercomuptation machines you discuss do cram in some view of infinity. I would agree with Martin Davis:

Martin Davis, in his writings on hypercomputation[34][35] refers to this subject as “a myth” and offers counter-arguments to the physical realizability of hypercomputation. As for its theory, he argues against the claims that this is a new field founded in the 1990s. This point of view relies on the history of computability theory (degrees of unsolvability, computability over functions, real numbers and ordinals), as also mentioned above. In his argument he makes a remark that all of hypercomputation is little more than: " if non-computable inputs are permitted then non computable outputs are attainable. "[36]
Hypercomputation - Wikipedia

Should I use a world other than “illogical”? Perhaps. It means “leads to logical contradiction”.

The larger conversation on information non-growth and ID. There was an argument being made that only a halting oracle can produce information (not true), and a halting oracle is required for information (not true), so therefore intelligence is a halting oracle (not true). None of these claims are true. We were trying to penetrate the circularity of it all. When pressed, it was granted that “partial halting oracles” can create information, and intelligence is a partial halting oracles. This then obviates the whole argument, but apparently this was difficult for some people to realize.

You might also find this discussion interesting: Is God a Halting Oracle?.

My dog is a partial halting Oracle. He has determined that when his ball is thrown uphill, the doesn’t have to run as fast to get it because it will stop. Throw the ball downhill and he’ll run harder to get it before the ball disappears into the pond.


I think we are disagreeing about what is logically possible.

I see physical possibility, as discussed eg by the Davis paper, as a separate question. Physical possibility is a subset of logical possibility (although Max Tegmark might disagree with that!).

I also agree that claiming that Turing machines can solve the halting problem leads to a logical contradiction.

But what about hypercomputation, that is computation beyond what a Turing machine can do? Is that possible in the sense that it does not involve a logical contradiction?

I think the answer is yes. For example, hypercomputation can be implemented as a supertask. From the linked Wiki article: “In philosophy, a supertask is a countably infinite sequence of operations that occur sequentially within a finite interval of time.” Mathematics deals with infinities of many types, without logical contradiction. So I conclude the hypercomputation is a logical possibility and so oracles are not logically impossible.

I had already read with interest the thread on God and oracles. I know nothing of theology, but my naive view is that God being omniscient would simply know the answer to any logically consistent question. But I’d go on to say that God could also create a physical universe where hypercomputers could be built, taking advantage of eg some of the possibilities of GR.

On ID and oracles: I posted on halting oracles only to understand why you thought they were logically impossible. Regarding ID I have have enjoyed the exchanges between you and Dr Holloway and you and Dr Durston and have learned from them. I appreciate the time you take to explain where you see the errors in their reasoning. I do think Dr Holloway has a deep understanding of the math, but, as many have said, is unable to relate that convincingly to biology.

1 Like

So you think these two things can be true at the same time?

A supertask requires a view of infinity. Just as I stated above. It also cannot be implemented. Without a similar view of infinity (such as a supertask), there is no way to solve this problem. We know this because if it was solvable it would lead to a logical contradiction. I do not see what you are disputing here.

Yes, I agree. But I am also saying that there is nothing that is logically contradictory about dealing with infinities. That is where we disagree.

I believe I understand your concerns with my position, and I am fine with leaving our disagreement at that.

You really want to disagree with me, don’t you? I can’t actually identify a disagreement yet.

Even better!

Given that Josh is open to the idea of God being a halting oracle, it shows that he doesn’t think HOs are logically contradictory in all cases like a square circle would.

1 Like

Exactly. Reading the reasoning it’s clear we mean logically contradictory in the relevant context, a context that intelligence doesn’t magically overcome.