{ localUrl: '../page/most_complexity_incompressible.html', arbitalUrl: 'https://arbital.com/p/most_complexity_incompressible', rawJsonUrl: '../raw/4v5.json', likeableId: '2860', likeableType: 'page', myLikeValue: '0', likeCount: '3', dislikeCount: '0', likeScore: '3', individualLikes: [ 'EricBruylant', 'JoeZeng', 'EricRogstad' ], pageId: 'most_complexity_incompressible', edit: '1', editSummary: '', prevEdit: '0', currentEdit: '1', wasPublished: 'true', type: 'wiki', title: 'Most complex things are not very compressible', clickbait: 'We can't *prove* it's impossible, but it would be *extremely surprising* to discover a 500-state Turing machine that output the exact text of "Romeo and Juliet".', textLength: '2748', alias: 'most_complexity_incompressible', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'EliezerYudkowsky', editCreatedAt: '2016-06-27 02:06:10', pageCreatorId: 'EliezerYudkowsky', pageCreatedAt: '2016-06-27 02:06:10', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '0', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '114', text: 'Although the [46h halting problem] means we can't *prove* it doesn't happen, it would nonetheless be *extremely surprising* if some 100-state Turing machine turned out to print the exact text of Shakespeare's *Romeo and Juliet.* Unless something was specifically generated by a simple algorithm, the Vast supermajority of data structures that *look* like they have high [5v algorithmic complexity] actually *do* have high algorithmic complexity. Since there are at most $2^{101}$ programs that can be specified with at most 100 bits (in any particular language), we can't fit all the 1000-bit data structures into all the 100-bit programs. While *Romeo and Juliet* is certainly highly compressible, relative to most random bitstrings of the same length, it would be shocking for it to compress *all the way down* to a 100-state Turing machine. There just aren't enough 100-state Turing machines for one of their outputs to be *Romeo and Juliet*. Similarly, if you start with a 10 kilobyte text file, and 7zip compresses it down to 2 kilobytes, no amount of time spent trying to further compress the file using other compression programs will ever get that file down to 1 byte. For any given compressor there's at most 256 starting files that can ever be compressed down to 1 byte, and your 10-kilobyte text file almost certainly isn't one of them.\n\nThis takes on defensive importance with respect to refuting the probability-theoretic fallacy, "Oh, sure, Occam's Razor seems to say that this proposition is complicated. But how can you be sure that this apparently complex proposition wouldn't turn out to be generated by some very simple mechanism?" If we consider a [1rd partition] of 10,000 possible propositions, collectively having a 0.01% probability on average, then all the arguments in the world for why various propositions might have unexpectedly high probability, must still add up to an average probability of 0.01%. It can't be the case that after considering that proposition 1 might have secretly high probability, and considering that proposition 2 might have secretly high probability, and so on, we end up assigning 5% probability to each proposition, because that would be a total probability of 500. If we assign prior probabilities using an algorithmic-complexity Occam prior as in [11w Solomonoff induction], then the observation that "most apparently complex things can't be further compressed into an amazingly simple Turing machine", is the same observation as that "most apparently Occam-penalized propositions can't turn out to be simpler than they look" or "most apparently subjectively improbable things can't turn out to have unseen clever arguments that would validly make them more subjectively probable".', metaText: '', isTextLoaded: 'true', isSubscribedToDiscussion: 'false', isSubscribedToUser: 'false', isSubscribedAsMaintainer: 'false', discussionSubscriberCount: '1', maintainerCount: '1', userSubscriberCount: '0', lastVisit: '', hasDraft: 'false', votes: [], voteSummary: 'null', muVoteSummary: '0', voteScaling: '0', currentUserVote: '-2', voteCount: '0', lockedVoteType: '', maxEditEver: '0', redLinkCount: '0', lockedBy: '', lockedUntil: '', nextPageId: '', prevPageId: '', usedAsMastery: 'false', proposalEditNum: '0', permissions: { edit: { has: 'false', reason: 'You don't have domain permission to edit this page' }, proposeEdit: { has: 'true', reason: '' }, delete: { has: 'false', reason: 'You don't have domain permission to delete this page' }, comment: { has: 'false', reason: 'You can't comment in this domain because you are not a member' }, proposeComment: { has: 'true', reason: '' } }, summaries: {}, creatorIds: [ 'EliezerYudkowsky' ], childIds: [], parentIds: [ 'Kolmogorov_complexity' ], commentIds: [ '4vf', '5cr' ], questionIds: [], tagIds: [ 'start_meta_tag' ], relatedIds: [], markIds: [], explanations: [], learnMore: [], requirements: [], subjects: [], lenses: [], lensParentId: '', pathPages: [], learnMoreTaughtMap: {}, learnMoreCoveredMap: {}, learnMoreRequiredMap: {}, editHistory: {}, domainSubmissions: {}, answers: [], answerCount: '0', commentCount: '0', newCommentCount: '0', linkedMarkCount: '0', changeLogs: [ { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '14632', pageId: 'most_complexity_incompressible', userId: 'EliezerYudkowsky', edit: '0', type: 'newParent', createdAt: '2016-06-27 02:06:11', auxPageId: 'Kolmogorov_complexity', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '14633', pageId: 'most_complexity_incompressible', userId: 'EliezerYudkowsky', edit: '0', type: 'newTag', createdAt: '2016-06-27 02:06:11', auxPageId: 'start_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '14630', pageId: 'most_complexity_incompressible', userId: 'EliezerYudkowsky', edit: '1', type: 'newEdit', createdAt: '2016-06-27 02:06:10', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }