2 ms·
It's showing that the halting problem is unsolvable, using an infinite recursive loop as an example. The halting problem is related to the incompleteness theore
by QuercusMax 5y ago
It's showing that the halting problem is unsolvable, using an infinite recursive loop as an example. The halting problem is related to the incompleteness theorem.
- BizarroLand 5y agoI wonder if it could be solvable by an algorithm that was capable of operating at a higher level. Mayhaps the issue is approaching the problem at the same dimensional level that the problem originated from. After all, humans can come at the problem from a higher cognitive level and, given enough time, resolve that an infinite loop is taking place, so the problem is not fundamentally unsolvable. Einstein said, "No Problem Can Be Solved From The Same Level Of Consciousness That Created It", so it is feasible to assume that, say, a quantum computer running every possible iteration of an algorithm could easily identify which iterations of the algorithm's parameters would induce infinite loops by simple attrition.
- blackbrokkoli 5y agoYes, definitely. But then the next task is just to solve the incompleteness problem on the level of the higher algorithm, because there must always be incompleteness. Hofstaedter discusses this at length in his book Gödel, Escher, Bach if you are interested in this topic.