News for hackers. Stuff that matters.
Re:Gödel’s first incompleteness theorem – an interactive tut... by koyanisqatsi on Monday October 17, 2022 @02:26PM (#33237695)
One way to think of incompleteness/halting is that the future is not computable. Meaning that to see the result of some symbolic/computational process you have to actually run the program and there is no shortcut to making a prediction one way or the other if we want to know for certain what the result would actually be.

There is something called abstract interpretation that can tell you what the result of some computation will be but by necessity it can only be an approximation because it must halt in some finite amount of time. Type systems are a good example of abstract interpretation because type systems assign a logical/mathematical semantics to code and allow one to determine in a finite amount of time whether some code is logically coherent according to the rules of the type system.

The larger philosophical implication of all this is that symbolic models of reality are always approximations. Whatever one can know for certain has either already happened and is in the past or there is some symbolic model/approximation which must necessarily have some degree of uncertainty and error.

Re:Gödel’s first incompleteness theorem – an interactive tut... by oulipo on Monday October 17, 2022 @03:03PM (#33238092)
Well the correct statement would be "to know the result of ANY computational process, in some cases you would have to run it".

For instance, there are many "simple programs" for which you can give the results by way of formal methods without running them. The incompleteness theorem says that there will exist one program for which you can't.

Re:Gödel’s first incompleteness theorem – an interactive tut... by occamrazor on Monday October 17, 2022 @03:14PM (#33238226)
It says something more than that. There are necessarily infinitely many programs like that.
Re:Gödel’s first incompleteness theorem – an interactive tut... by fspeech on Monday October 17, 2022 @03:08PM (#33238156)
Even if you can predict halting (which for the large class of decidable problems you can) you still have to run the computation to see the results.

To me it's more about the expressiveness of languages.