Re:A first for physics: Fundamental quantum physics problem ...
by incepted on Thursday December 10, 2015 @03:25AM
(#10709552)
Uncomputable or unsolvable?
[ Parent
| on HN ]
Re:A first for physics: Fundamental quantum physics problem ...
by pygy_ on Thursday December 10, 2015 @07:31AM
(#10710292)
Undecidable.
https://en.wikipedia.org/wiki/Undecidable_problem
See here for a concrete example of a similar problem (props to adrianN for the link in the first place):
Re:A first for physics: Fundamental quantum physics problem ...
by jordigh on Thursday December 10, 2015 @09:17AM
(#10710669)
These two are roughly the same thing. Formally, a proof is just a computation within an axiomatic system. A computation is just transforming one expression into another according to a set of rules. Whether this transformed expression is an algebraic or a logical formula is not a huge difference.
In terms that may be more familiar to programmers, lisp's homoiconicity of data and code corresponds roughly to how Gödel was able to express logical formulae as arithmetic statements via Gödel numbering. Once you are able to encode logical formulae as natural numbers, you can then use laws of arithmetic (e.g. Peano's axioms) to compute/prove other statements/numbers.