Re:Intelligence as a Halting Oracle
by adrianN on Tuesday November 06, 2018 @10:07AM
(#18391618)
Solving the Halting problem requires you to decide for all TMs whether they halt or not. Nothing is preventing you from deciding it for a useful subset of TMs. For example deciding it for all TMs that have an encoding that uses fewer bits than the number of atoms in the observable universe is totally possible. There are also infinite families of TMs for which you can solve the halting problem. Again, a lot of what compilers do sounds like it would require solving the halting problem, when in fact it doesn't because they only handle a subset of all possible cases.
[ Parent
| on HN ]
The parent article discusses the idea of a partial halting oracle (PHO), which decides for an undecidable subset of problems. A TM cannot meet this requirement, by definition. It seems like humans are in the category of PHOs.
There is no proof that human brains are capable of deciding uncomputable sets and really no reason to believe that they should be able to.
That's a bit of a tangent. Here we were discussing whether the concept itself makes sense.
But, as for empirical evidence, max entropy + Bayesian hypothesis selection makes the PHO hypothesis much more plausible than the TM hypothesis.