Intelligence and Halting Oracles

Conversation Side Conversation
21

So the Halting Oracle is a really good example to study further. It is proven that they do not exist in a proof by contradiction (Proof by contradiction - Wikipedia).

The Problem

Does a program exist that can examine the code of any other program to determine if it halts?

The Proof

This is adapted from here: Halting problem - Wikipedia

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.

Intelligence is Not a Halting Oracle

@EricMH, I thought I’d give you an example of some code that demonstrates that humans are not halting oracles. This is describe here:

For example, the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop.
NP-hardness - Wikipedia

The satisfiability problem is defined here: NP-hardness - Wikipedia
Boolean satisfiability problem - Wikipedia

So it is fairly easy to construct a question that in principle no amount of human intelligence can solve. I’ll just ask a human, does this algorithm halt?

def f():
  if is_satisfiable(VERY_LARGE_SAT_PROBLEM):
    loop_forever()

It is easy to construct a hard SAT problem that cannot be solved by human intelligence. Therefore we are demonstrating that humans are not halting oracles.

The Proof Against ID

Let’s look at your claim.

You claim:

  1. CSI can only be created by intelligence.
  2. Therefore, according to your application of Levin, intelligence is a halting oracle.

That is the starting point you claim. We can add to this.

  1. Halting oracles are a logical impossibility (see above).
  2. That means the “intelligence” that creates CSI is a logical impossibility.
  3. Therefore, either claim #1 is false, or CSI is a logical impossibility.
  4. If claim #1 is false, there other sources of CSI than intelligence, then CSI is not a unique signature for intelligence.
  5. If CSI is a logical impossibly, then CSI does not exist.

Either #6 or #7 mean that ID is false.

6 Likes