|
Title: Understanding Godel Incompleteness on Bitcoin Post by: saransh on August 21, 2017, 02:54:28 AM Consider Gödel's incompleteness theorems (specifically the second one)
"For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T includes a statement of its own consistency then T is inconsistent." Gödel's second incompleteness theorem proves that your theory, which assumes math is valid (aka "including basic arithmetical truths") and assumes itself to also be true, is inherently inconsistent. Math has been proven to be incomplete. "any consistent effective formal system that includes enough of the theory of the natural numbers is incomplete: there are true statements expressible in its language that are unprovable within the system" (Gödel's first incompleteness theorem). It does, however, mean that it's impossible to prove mathematicians have nothing left to prove, so maybe its good for job security for them. What about Bitcoin Proof Of Work Algorithm and Other Consensus rules Thanks Title: Re: Understanding Godel Incompleteness on Bitcoin Post by: Manfred Macx on August 21, 2017, 08:05:13 AM Gödel's incompleteness theorems concern "formal axiomatic system containing basic arithmetic" to quote Wikipedia. POW is an algorithm not a formal axiomatic system so theorems do not apply.
Title: Re: Understanding Godel Incompleteness on Bitcoin Post by: erikkaplun on March 23, 2022, 10:18:28 AM Gödel's incompleteness theorems concern "formal axiomatic system containing basic arithmetic" to quote Wikipedia. POW is an algorithm not a formal axiomatic system so theorems do not apply. According to the Curry-Howard correspondence, there is an isomorphism between programs (algortihms) and proofs. So the Gödel's incompleteness discoveries should be extendable to algortihms. Title: Re: Understanding Godel Incompleteness on Bitcoin Post by: HeRetiK on March 23, 2022, 11:39:30 AM Gödel's incompleteness theorems concern "formal axiomatic system containing basic arithmetic" to quote Wikipedia. POW is an algorithm not a formal axiomatic system so theorems do not apply. According to the Curry-Howard correspondence, there is an isomorphism between programs (algortihms) and proofs. So the Gödel's incompleteness discoveries should be extendable to algortihms. Interesting necro :) I guess Gödel's incompleteness theorem being applicable to algorithms is more or less reflected in the halting problem? Doesn't seem to be really relevant for PoW though. Both Gödel's incompleteness theorem and the halting problem require a minimum of complexity to be present which you don't have in Bitcoin's PoW algorithm (or even Bitcoin script). Title: Re: Understanding Godel Incompleteness on Bitcoin Post by: odolvlobo on March 24, 2022, 12:58:19 AM One example of how Bitcoin runs into this issue is the fact that a legacy transaction's signature is part of the transaction, so it must be explicitly excluded from the signature's calculation.
Title: Re: Understanding Godel Incompleteness on Bitcoin Post by: larry_vw_1955 on March 24, 2022, 05:17:52 AM According to the Curry-Howard correspondence, there is an isomorphism between programs (algortihms) and proofs. algorithms are proofs. nothing shocking about that i guess. algorithms prove how to solving a problem. |