# Intelligence and Halting Oracles

**URL:** https://discourse.peacefulscience.org/t/intelligence-and-halting-oracles/1124
**Category:** Side Conversation
**Created:** [August 11, 2018, 11:56am UTC](https://discourse.peacefulscience.org/t/intelligence-and-halting-oracles/1124 "2018-08-11T11:56:30Z")
**Posts on this page:** 1
**Showing post:** 21

<div class="post-metadata">

### Author: ![swamidass](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/swamidass/32/3_2.png) [@swamidass](https://discourse.peacefulscience.org/u/swamidass)
#### Post date: [September 18, 2018, 12:52am UTC](https://discourse.peacefulscience.org/t/intelligence-and-halting-oracles/1124/21 "2018-09-18T00:52:35Z")

</div>

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 ([Reductio ad absurdum - Wikipedia](https://en.wikipedia.org/wiki/Proof_by_contradiction)).

## 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](https://en.wikipedia.org/wiki/Halting_problem#Proof_concept)

Suppose that there exists a [total](https://en.wikipedia.org/wiki/Total_function) [computable function](https://en.wikipedia.org/wiki/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](#):
>
> Somehow we programmers write a whole lot of code that reliably halts. And we cannot write programs to do the same. That’s pretty surprising if we are not halting oracles.

@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](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) can be reduced to the halting problem by transforming it to the description of a [Turing machine](https://en.wikipedia.org/wiki/Turing_machine) that tries all [truth value](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/NP-hardness)

The satisfiability problem is defined here: [NP-hardness - Wikipedia](https://en.wikipedia.org/wiki/NP-hardness)  
[Boolean satisfiability problem - Wikipedia](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Unrestricted_satisfiability_(SAT))

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.

> [@EricMH](#):
>
> Yes, I’m just arguing by definition here. I define intelligence as that which can create CSI from scratch per Levin. Therefore, intelligence is a halting oracle.

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.

---

_[View the full topic](https://discourse.peacefulscience.org/t/intelligence-and-halting-oracles/1124)._