{"id":4101,"date":"2018-07-07T19:57:07","date_gmt":"2018-07-07T19:57:07","guid":{"rendered":"https:\/\/www.novonon.com\/blog\/?p=4101"},"modified":"2018-07-07T19:57:07","modified_gmt":"2018-07-07T19:57:07","slug":"john-baez-chaitlins-incompleteness-theory","status":"publish","type":"post","link":"https:\/\/www.novonon.com\/blog\/2018\/07\/07\/john-baez-chaitlins-incompleteness-theory\/","title":{"rendered":"John Baez: Chaitlin&#8217;s Incompleteness Theory"},"content":{"rendered":"<p>Attention conservation notice: only of interest to computer science nerds. The web page discusses a number of topics, but the section on Chaitlin is all I&#8217;m really suggesting here.<\/p>\n<blockquote><p>So, amazingly complex things can be compressed into fairly little information. You can&#8217;t help but wonder: how complex can something be?<\/p>\n<p>The answer: arbitrarily complex! At least that&#8217;s true if we&#8217;re talking about the\u00a0<a href=\"http:\/\/en.wikipedia.org\/wiki\/Kolmogorov_complexity\">Kolmogorov complexity<\/a>\u00a0of a string of bits: namely, the length of the shortest computer program that prints it out. Lots of long strings of bits can&#8217;t be compressed. You can&#8217;t print out most of them using short programs, since there aren&#8217;t enough short programs to go around.<\/p>\n<p>Of course, we need to fix a computer language ahead of time, so this is well-defined. And we need to make sure the programs are written in binary, so the comparison is fair.<\/p>\n<p>So, things can be arbitrarily complex. But here&#8217;s a more interesting question: how complex can we\u00a0<i>prove<\/i>\u00a0something to be?<\/p>\n<p>The answer is one of the most astounding facts I know. It&#8217;s called\u00a0<a href=\"http:\/\/en.wikipedia.org\/wiki\/Chaitin%27s_incompleteness_theorem#Chaitin.27s_incompleteness_theorem\">Chaitin&#8217;s incompleteness theorem<\/a>. It says, very roughly:<\/p>\n<div align=\"center\"><b>There&#8217;s a number\u00a0<i>L<\/i>\u00a0such that we can&#8217;t prove the Kolmogorov complexity of any specific string of bits is more than\u00a0<i>L<\/i>.<\/b><\/div>\n<\/blockquote>\n<p>Source: <em><a href=\"http:\/\/math.ucr.edu\/home\/baez\/surprises.html\">surprises<\/a><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Attention conservation notice: only of interest to computer science nerds. The web page discusses a number of topics, but the section on Chaitlin is all I&#8217;m really suggesting here. So, amazingly complex things can be compressed into fairly little information. You can&#8217;t help but wonder: how complex can something be? The answer: arbitrarily complex! At [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-4101","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3pfIY-149","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/posts\/4101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/comments?post=4101"}],"version-history":[{"count":1,"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/posts\/4101\/revisions"}],"predecessor-version":[{"id":4102,"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/posts\/4101\/revisions\/4102"}],"wp:attachment":[{"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/media?parent=4101"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/categories?post=4101"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.novonon.com\/blog\/wp-json\/wp\/v2\/tags?post=4101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}