semper studēns

81 notes

Logicians on safari

Some cute examples of computability theory applied to specific problems.

  1. We now know that, if an alien with enormous computational powers came to Earth, it could prove to us whether White or Black has the winning strategy in chess. To be convinced of the proof, we would not have to trust the alien or its exotic technology, and we would not have to spend billions of years analyzing one move sequence after another. We’d simply have to engage in a short conversation with the alien about the sums of certain polynomials over finite fields.
  2. There’s a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof of the Riemann Hypothesis. Indeed, every formal proof of the Riemann Hypothesis with at most (say) a million symbols corresponds to some way of packing the boxes into your trunk, and vice versa. Furthermore, a list of the boxes and their dimensions can be feasibly written down.
  3. Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact, without revealing anything other than the fact that you proved it. It’s also possible to write the proof down in such a way that someone else could verify it, with very high confidence, having only seen 10 or 20 bits of the proof.

Filed under computer science computability

  1. clazzjassicalrockhop reblogged this from isomorphismes
  2. spetharrific reblogged this from isomorphismes
  3. mylifeisborromean reblogged this from isomorphismes
  4. logicianmagician reblogged this from isomorphismes
  5. 500daysofsumeria reblogged this from isomorphismes
  6. t33j reblogged this from isomorphismes
  7. esteparium reblogged this from isomorphismes
  8. clockworkfox reblogged this from isomorphismes
  9. a-bittersweet-blessing reblogged this from isomorphismes
  10. mathochism reblogged this from isomorphismes
  11. natthebuddhist reblogged this from isomorphismes
  12. pizzagoras reblogged this from isomorphismes
  13. theazerilime reblogged this from isomorphismes
  14. isomorphismes reblogged this from studeo and added:
    by Scott Aaronson, via studeo
  15. myaxiomofchoice reblogged this from intothecontinuum
  16. studeo posted this