3 ms·
It isn't so much coming up with the specific operations, but the realization that TMs can emulate every other machine, i.e. the Church-Turing thesis. This seem
by yters 8y ago
It isn't so much coming up with the specific operations, but the realization that TMs can emulate every other machine, i.e. the Church-Turing thesis. This seems to be beyond the capability of TMs as it ventures into the domain of the halting problem.
- adrianN 8y agoSolving 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.
- yters 8y agoThe 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.
- adrianN 8y agoThere is no proof that human brains are capable of deciding uncomputable sets and really no reason to believe that they should be able to.
- yters 8y agoThat'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.