Halting Oracles And Law of information Non Growth

[swamidass (S. Joshua Swamidass)]

@BruceS

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

I think his intended point was that they cannot be constructed as logic machines.

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.

@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:

@swamidass

The Proof

This is adapted from here: https://en.wikipedia.org/wiki/Halting_problem#Proof_concept

Suppose that there exists a total computable function halts(f) that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise.

Now consider this program.

def g():
    if halts(g):
       loop_forever()

Now ask, does halts(g) return true or false? Either way we get a contradiction.

1. If halts(g) returns True, then g() will execute loop_forever(), and will therefore not halt, resulting in a contradiction, because halts(g) should have returned False.
2. If halts(g) returns False, then g() will halt, resulting in a contradiction, because halts(g) should have returned True.

Therefore we know that a Halting Oracle is not logically 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?.