3 ms·

Does this actually mirror the incompleteness theorem logic or does it just create an infinite recursive loop? They seem distinct.

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 ago
  I 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 ago
    Yes, 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.
CaptainNegative 5y ago
It's more or less the same argument. They key additional ingredient in Godel's proof (besides some slight technicality on soundness vs. omega-consistency) is the encoding of an arithmetic interpreter inside of arithmetic itself. That a bash script can run and capture the output of another bash script is pretty obvious, but the first order logic analogue is not nearly as neat and easy. The argument given here is a modern translation of Turing's work in his original paper introducing Turing Machines and the Halting problem, in which he devotes an entire section to the connection between his proof and that of Godel.
fiatjaf 5y ago
They are definitely distinct. The key insight of Godel's incompleteness theorem is that there is a statement that can't be proved as true but is indeed true and can be perceived as true by an observer outside of the mechanical-logical realm inside of which that statement lives. It says there are something non-mechanical about intelligence. Apparently people think it is just a paradox or some other boring idea. See "Emperor's New Mind" from Roger Penrose.
- denton-scratch 5y ago
  > It says there are something non-mechanical about intelligence. I don't think Gödel drew that conclusion; that's Roger Penrose's reasoning. He uses Gödel's Theorem as an example of correct reasoning that can't be algorithmic (i.e. Gödel's mind cannot be replaced by an algorithm). It's not a proof, and it's controversial. I find it convincing; but then I'm biased - I'm predisposed to the view that the mind is not algorithmic.
  - fiatjaf 5y ago
    Yes, I just used this opportunity to raise this point. I don't know what Gödel himself thought of it. But I find it very disheartening when such an interesting find is presented as simply "a paradox" akin to the phrase "this is a lie". That would be the most uninteresting thing ever. Many articles on the internet thus describe Gödel's theorem, and also that famous book from Douglas Hofstadter.

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 ago
I 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 ago
  Yes, 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.

CaptainNegative 5y ago

It's more or less the same argument. They key additional ingredient in Godel's proof (besides some slight technicality on soundness vs. omega-consistency) is the encoding of an arithmetic interpreter inside of arithmetic itself. That a bash script can run and capture the output of another bash script is pretty obvious, but the first order logic analogue is not nearly as neat and easy. The argument given here is a modern translation of Turing's work in his original paper introducing Turing Machines and the Halting problem, in which he devotes an entire section to the connection between his proof and that of Godel.

fiatjaf 5y ago

They are definitely distinct. The key insight of Godel's incompleteness theorem is that there is a statement that can't be proved as true but is indeed true and can be perceived as true by an observer outside of the mechanical-logical realm inside of which that statement lives. It says there are something non-mechanical about intelligence. Apparently people think it is just a paradox or some other boring idea. See "Emperor's New Mind" from Roger Penrose.

denton-scratch 5y ago
> It says there are something non-mechanical about intelligence. I don't think Gödel drew that conclusion; that's Roger Penrose's reasoning. He uses Gödel's Theorem as an example of correct reasoning that can't be algorithmic (i.e. Gödel's mind cannot be replaced by an algorithm). It's not a proof, and it's controversial. I find it convincing; but then I'm biased - I'm predisposed to the view that the mind is not algorithmic.
- fiatjaf 5y ago
  Yes, I just used this opportunity to raise this point. I don't know what Gödel himself thought of it. But I find it very disheartening when such an interesting find is presented as simply "a paradox" akin to the phrase "this is a lie". That would be the most uninteresting thing ever. Many articles on the internet thus describe Gödel's theorem, and also that famous book from Douglas Hofstadter.