Intelligence as a Halting Oracle

Take a look at this.

Intelligence as a Halting Oracle

November 4, 2018 | Eric Holloway

In his paper “Using turing oracles in cognitive models of problem-solving” Jonathan Bartlett proposes halting oracles as first class citizens in our explanations for the world, such as modeling the human mind as a halting oracle.

A brief explanation: the famous computer scientist Alan Turing invented a universal machine that can copy any other machine. However, this machine has a critical limitation. It cannot determine whether an arbitrary machine will run forever or not. This is known as the halting problem. A halting oracle is some non-mechanical entity that can solve the halting problem for all machines.

A common objection to Jonathan’s idea is that humans are clearly not halting oracles because we embed any unsolvable math problem as the halting condition for a loop, and a human cannot tell us whether the loop will halt or not.

What this objection misses is that there are a range of oracles between plain Turing machines and a complete halting oracle. These inbetween oracles we call partial halting oracles.

We can see the concept of partial halting oracles is coherent by considering the set of problems solvable by a complete halting oracle. This set is infinite and undecidable (no Turing machine can decide on the correct answer for every problem). Now we remove one item from the set. We still have an infinite and undecidable set, yet it is less than what a complete halting oracle can solve. This partial set lists the problems that can be solved by a partial halting oracle. We can even remove an infinite number of problems from the set and still have an infinite and undecidable set. So, the objection that humans cannot solve every problem only shows that humans might not be complete halting oracles, but cannot show that humans are not partial halting oracles.

If a partial halting oracle is a coherent concept, what can it tell us about the world, empirically?

We can think of Turing machines as mappings between bitstrings. All Turing machines can be represented as bitstrings, and their outputs are also represented as bitstrings. Further, we can think of the Turing machine bitstrings as sorted into two groups: the halting and non halting group.

Now, let’s say we are trying to invent the next major Facegramizon. However, we are lazy and do not want to invent Facegramizon ourselves. Since Facegramizon is a piece of software, it is a Turing machine that produces a certain result. Aha! So, instead of inventing Facegramizon, all we have to do is tell our computer what the result looks like, and then have the computer do the hard lifting of scanning all Turing machines until it finds the Facegramizon.

The problem is there are a large number of Turing machines that do not halt, an infinite number, in fact. So the Facegramizon scanner risks getting stuck on one of these infinitely running machines. There are methods of interleaving Turing machines to avoid getting stuck, but this results in a very slow search process. If we were able to bring in a halting oracle, the oracle can eliminate all the non halting machines, greatly speeding up the search process. If we only have a partial halting oracle, we still get a speed up by eliminating the non-halting programs that can be identified by our partial oracle.

Our scenario provides the insight that a halting oracle, partial or complete, has a tangible impact on our search process. This has two implications. First, we can improve computational processing, perhaps dramatically, by the inclusion of a halting oracle of some variety. Second, we can use inference to the best explanation to identify the involvement of a halting oracle in a computational process.

For a formal proof of how partial halting oracles break the law of information non-growth, also known as information conservation, please see For Q&A on this article, please see:

1 Like

@EricMH did mention that he intended to write up his thoughts into a white paper. Gently and kindly, it would be good for us to look at it, think about it, and engage when he is ready. Right now he has everyone’s attention @TSZ . and at Panda’s Thumb. I’m curious to see how they respond.

Also republished here:

1 Like

I did look at it. It has the same mistakes. It hasn’t changed. He is repeating the same nonsense over and over again.

Thus far, they have responded with skepticism. And I don’t expect that to change.

1 Like

I don’t think he is fooling anyone at either place. It really is a sad story.

1 Like

This is a DI publication. There is much here. As you showed all of his Information Theory work is wrong. There is no connection with biological systems. It is just a lot of incorrect math disguised as Information Theory supporting ID. It doesn’t come close. And this halting oracle stuff is just more nonsense.

To me, the idea of “intelligence as a halting oracle” seems quite implausible.

The halting problem is the problem of determining whether a given Turing machine will halt. It is a problem of the infinite. There is only a halting problem because the Turing machine is an infinite machine (it has an infinite tape).

If we limit ourselves to finite machines, say to finite automata, then there is no halting problem. A finite automaton could loop, but we can tell whether it is looping because then it would repeat itself. And we can test for that using only a finite automaton, albeit a larger one than what we are testing.

So the halting problem has to do with the infinite.

Humans are finite beings. We observe human behavior that we consider to be intelligent. Since we observe intelligent behavior in finite beings, intelligence cannot be just a problem about the infinite. And therefore it seems implausible that a halting oracle would have anything to do with intelligence.


I’m disappointed that their work on AI is including this publiation. I was hoping this would be a fresh start, where they could break away from the ID arguments.

1 Like

Have you noticed that DI is more overtly Christian now? I think there funders are pushing them in that direction and away from disproving evolution. Linking ID with AI has a future and is forward looking. The Christian God has to be the IDer who makes AI possible.

Yes, I have noticed.

No, I do not think that is why. I think, rather, after 25 years, they are realizing the unspecified designer gambit isn’t going to get them around methodological naturalism. They are giving up on that strategy.

In my view, this is a good thing. The doublespeak gambit was a very risky strategy. I wouldn’t fault them for trying, but they should have given it up a long time ago.


I’m waiting for references to blockchains… :yum:


Coherency-wise, I don’t see why a Turing machine couldn’t be a Partial Halting Oracle.

1 Like