Halting Oracles And Law of information Non Growth

I think I’m starting to understand what you mean. However, I’m trying to understand whether this “impossibility” is fundamental, or something that is simply because we don’t have computing power to simulate the mechanics of atoms precisely.

I think I have convinced myself that the impossibility is fundamental. As you said, you have to be able to compress all possible inputs. So in the case of the 2-atom universe, you have to be able to find an algorithm to compress any 4-tuple (x_1, x_2, v_1, v_2) for any x_1, x_2, v_1, v_2 \in R. This seems fundamentally impossible - because it would basically mean discovering every possible theorem in number theory.

1 Like

OK, but imagine we were living in 1910, before people knew much about QM. (OK, Shannon was not born yet.) So we have only a classical, mostly deterministic universe. (Yes, there are edge cases like Space Invaders and Norton’s Dome, but do we need to rely on them?) Would this have any impact on whether information could increase via determinism alone?


Remember too that most real numbers are incompressible because they have infinite significant digits, and no obvious construction. So simpler numbers are more compressible. Usually we can ignore this detail by just discretizing space…or using a descreet problem (such as a sequence). Thinking about an MD simulation of fixed precision might be how this is done, however keep in mind that this system is no longer reversible. You need infinite precision for reversibility. However, you are physicist, so I thought we’d use this example.

Just a side point. We can ignore this detail. LoING is in a theoretical construct. It is a separate question whether or not this applies to the real world.

1 Like

Yes, but going back to a QM universe, position and velocity is discretized, in the sense that it doesn’t make sense to talk about anything smaller than the Planck length. So even in our actual universe we should be able to represent positions and velocities with a finite number of significant digits.

That being said, I don’t think this breaks the fundamental impossibility of finding optimal compression with a single formula. Even with a finite set of numbers, there could be an infinite number of theorems to relate them. (Unless if there is a mathematical proof against that.)


The real challenge is if I give you an arbitrary list of numbers, without explaining to you the process that constructed them. In that case, you will quickly find it is impossible to solve, even for very short lists.

Take, for example, this list: Open Challenge to ID Advocates. It is framed differently, but we can repose the problem. What is the optimal compression of those five sequences? Not an easy thing to solve. In fact, as we’ve seen, you cannot figure it out. I’m almost guaranteed (because I produced the numbers) to be able to come up with a better compression than you. However, even that is not guaranteed to be optimal. There might be a better compression I did not envision. It is an undecidable problem.


True, but in the model we’ve been discussing here, you don’t even have to invoke QM for randomness to inject information into DNA. In this model, the only information is the digital information in the order of the bases in the DNA. Even if the chemistry that causes a mutation is deterministic, as far as this model is concerned the mutation represents new information from a random source.

As a number of people have observed here, it’s not just the mathematics of the model that matters; the mapping of the model elements to the physical world is just as important in drawing valid conclusions.


Definetely true.

That is precisely the point. It is also why appeals to “well it is just a proven established fact that information can’t grow” are hollow appeals. It reminds me more of Aristotelian philosophy than anything in science.


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.