statue of Alan Turing/Antoine Taveneaux (CC BY-SA 3.0)

In his paper, “Using Turing oracles in cognitive models of problem-solving” Jonathan Bartlett proposes to model the human mind as a halting oracle.

A brief explanation: Computer science pioneer Alan Turing (1912–1954) imagined a universal machine that can copy any other machine. However, this machine has a critical limitation: It cannot determine whether any given machine will run forever or not. This is known as the halting problem: “There can be no general procedure to decide if a self-contained computer program will eventually halt.”

A halting oracle is a non-mechanical entity that can solve the halting problem for all machines.

A common objection to Bartlett’s idea is that humans cannot be 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.

This objection misses the fact that there is a range of oracles between plain Turing machines and a complete halting oracle. We call these in-between oracles “partial halting oracles.”

We can see that 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.

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 “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 that there is 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 machines that run indefinitely. 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 could eliminate all the non-halting machines, greatly speeding up the search process. If we only have a partial halting oracle, we can still speed the process 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 Breaking the Law of Information Non-Growth.

Note: This story is adapted from Intelligence as a Halting Oracle (Eric Holloway, November 4, 2018) at AM-Nat: Alternatives to Methodological Naturalism

Eric Holloway has a Ph.D. in Electrical & Computer Engineering from Baylor University. He is a current Captain in the United States Air Force where he served in the US and Afghanistan He is the co-editor of the book Naturalism and Its Alternatives in Scientific Methodologies. Dr. Holloway is an Associate Fellow of the Walter Bradley Center for Natural and Artificial Intelligence.

Also by Eric Holloway: Does information theory support design in nature?

Artificial intelligence is impossible

and

Could one single machine invent everything?