Take a look at this.
https://www.am-nat.org/site/halting-oracles-as-intelligent-agents/
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 www.am-nat.org/site/law-of-information-non-growth. For Q&A on this article, please see: https://news.ycombinator.com/item?id=18381723.
