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? More.
Follow UD News at Twitter!
See also: Also by Eric Holloway: Does information theory support design in nature?
Artificial intelligence is impossible
Could one single machine invent everything?