{"id":31157,"date":"2019-10-31T21:39:48","date_gmt":"2019-10-31T18:39:48","guid":{"rendered":"https:\/\/prohoster.info\/blog\/paradoksy-o-szhatii-dannyh\/"},"modified":"2019-10-31T21:39:48","modified_gmt":"2019-10-31T18:39:48","slug":"paradoksy-o-szhatii-dannyh","status":"publish","type":"post","link":"https:\/\/prohoster.info\/nl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxen over datacompressie","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Paradoxen over datacompressie\" src=\"\/wp-content\/uploads\/2019\/04\/d15fed5cc55334e6bb9bc3bbd7cbf50c.jpeg\" style=\"display:block;margin: 0 auto;\" \/> De taak van gegevenscompressie kan in zijn eenvoudigste vorm betrekking hebben op getallen en hun aanduidingen. Getallen kunnen worden aangeduid met numerieke uitdrukkingen (<i>\u2018elf\u2019<\/i> voor het getal 11), wiskundige uitdrukkingen (<i>\u2018twee tot de twintigste\u2019<\/i> voor 1048576), stringuitdrukkingen (<i>\u2018vijf negens\u2019<\/i> voor 99999), eigennamen (<i>\u2018het getal van het beest\u2019<\/i> voor 666, <i>\u2018het jaar van de dood van Turing\u2019<\/i> voor 1954), of willekeurige combinaties daarvan. Elk aanduiding is geschikt, mits de gesprekspartner duidelijk kan bepalen over welk getal het gaat. Het is duidelijk dat het effici\u00ebnter is om de gesprekspartner <i>\u2018de faculteit van acht\u2019<\/i> te melden dan de equivalente aanduiding <i>\u2018veertig duizend driehonderd twintig\u2019<\/i>. Hier rijst de logische vraag: wat is de kortste aanduiding voor een gegeven getal?<\/p>\n<p>De filosoof Bertrand Russell publiceerde in 1908 de <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%91%D0%B5%D1%80%D1%80%D0%B8\">\u2018Bertrand-paradox\u2019<\/a><\/noindex>, die de kwestie van aanduidingen van getallen vanuit een andere kant aanraakt: <b>wat is het kleinste getal waarvoor niet genoeg achtien letters zijn om het aan te duiden?<\/b><br \/>\nZulk een getal moet bestaan: met de tachtig Russische letters en spaties kunnen in totaal slechts 3480 aanduidingen worden gemaakt, wat betekent dat met gebruik van tachtig letters niet meer dan 3480 getallen kunnen worden aangeduid. Dat betekent dat een bepaald getal, niet groter dan 3480, op deze manier niet kan worden aangeduid.<\/p>\n<p>Dus moet er corresponderen met dit getal de aanduiding zijn <i>\u2018het kleinste getal waarvoor niet genoeg tachtig letters zijn om het aan te duiden\u2019<\/i>, waarin in totaal 78 letters zitten! Enerzijds moet dit getal bestaan; anderzijds, als dit getal bestaat, dan komt de aanduiding niet overeen met het getal. Paradox!<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<p>De eenvoudigste manier om deze paradox te negeren, is te verwijzen naar de informaliteit van verbale aanduidingen. Het idee is dat als in de aanduidingen slechts een specifieke set uitdrukkingen was toegestaan, dat <i>\u2018het kleinste getal waarvoor niet genoeg tachtig letters zijn om het aan te duiden\u2019<\/i> geen geldige aanduiding zou zijn, terwijl praktisch nuttige aanduidingen zoals <i>\u2018de faculteit van acht\u2019<\/i> geldig zouden blijven.<\/p>\n<p>Zijn er formele manieren om een reeks (algoritme) van handelingen met getallen te beschrijven? Ja, die zijn er volop \u2014 ze worden programmeertalen genoemd. Laten we in plaats van verbale aanduidingen programma's gebruiken (bijvoorbeeld in Python) die de benodigde getallen genereren. Bijvoorbeeld, voor vijf negens zou het programma werken <code>print(\"9\"*5)<\/code>. We will still be interested in the shortest program for a given number. The length of such a program is called <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9A%D0%BE%D0%BB%D0%BC%D0%BE%D0%B3%D0%BE%D1%80%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C\">Kolmogorov complexity<\/a><\/noindex> of the number; this is the theoretical limit to which a given number can be compressed.<\/p>\n<p>Instead of the Berry paradox, we can now consider a similar one: <b>what is the smallest number for which there is not enough of a kilobyte program to output it?<\/b><\/p>\n<p>We will reason as before: there are 2561024 kilobyte texts, which means that kilobyte programs can output no more than 2561024 numbers. This means that there is some number, not greater than 2561024, that cannot be outputted in this way.<\/p>\n<p>But let\u2019s write a Python program that generates all possible kilobyte texts, runs them, and if they output a number, it adds that number to a dictionary of achievable numbers. After checking all 2561024 possibilities, no matter how long it takes \u2014 the program searches for the smallest number that is absent from the dictionary and outputs that number. It seems obvious that such a program would fit in a kilobyte of code \u2014 and would output that very number which cannot be outputted by a kilobyte program!<\/p>\n<p>So what is the catch now? It can no longer be blamed on the informality of the notation!<\/p>\n<p>If you are worried that our program will require an astronomical amount of memory to run \u2014 a dictionary (or bit array) of 2561024 elements \u2014 then all the same can be accomplished without it: for each of the 2561024 numbers, we can sequentially check all 2561024 possible programs until a suitable one is found. It doesn\u2019t matter that such a search will take a very long time; after checking less than (2561024)2 pairs of number and program, it will indeed complete and find that coveted number.<\/p>\n<p>Or will it not complete? After all, among all the programs that will be tried, we will encounter <code>while True: pass<\/code> (and its functional analogs) \u2014 and further checks of such a program will go nowhere!<\/p>\n<p>Unlike the Berry paradox, where the catch lay in the informality of the notation, in the second case we have a well-masked reformulation of the <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8\">\u2018halting problem\u2019<\/a><\/noindex>. The point is that it is impossible to determine the output of a program within a finite timeframe. In particular, Kolmogorov complexity <noindex><a rel=\"nofollow\" href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F\">is not computable.<\/a><\/noindex>: er is geen algoritme dat het mogelijk maakt om voor een gegeven getal de lengte van het kortste programma te vinden dat dat getal uitvoert; daarom is er ook geen oplossing voor het Berry-probleem \u2014 om voor een gegeven getal de lengte van de kortste verbale notatie te vinden.<br \/>\n<br \/>Bron: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/446976\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 \u0444\u043e\u0440\u043c\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u043a \u0447\u0438\u0441\u043b\u0430\u043c \u0438 \u0438\u0445 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c. \u0427\u0438\u0441\u043b\u0430 \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 (\u00ab\u043e\u0434\u0438\u043d\u043d\u0430\u0434\u0446\u0430\u0442\u044c\u00bb \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u0430 11), \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u043c\u0438 (\u00ab\u0434\u0432\u0430 \u0432 \u0434\u0432\u0430\u0434\u0446\u0430\u0442\u043e\u0439\u00bb \u0434\u043b\u044f 1048576), \u0441\u0442\u0440\u043e\u043a\u043e\u0432\u044b\u043c\u0438 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u043c\u0438 (\u00ab\u043f\u044f\u0442\u044c \u0434\u0435\u0432\u044f\u0442\u043e\u043a\u00bb \u0434\u043b\u044f 99999), \u0438\u043c\u0435\u043d\u0430\u043c\u0438 \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c\u0438 (\u00ab\u0447\u0438\u0441\u043b\u043e \u0437\u0432\u0435\u0440\u044f\u00bb \u0434\u043b\u044f 666, \u00ab\u0433\u043e\u0434 \u0441\u043c\u0435\u0440\u0442\u0438 \u0422\u044c\u044e\u0440\u0438\u043d\u0433\u0430\u00bb \u0434\u043b\u044f 1954), \u0438\u043b\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u043c\u0438 \u0438\u0445 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044f\u043c\u0438. \u0413\u043e\u0434\u0438\u0442\u0441\u044f \u043b\u044e\u0431\u043e\u0435 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23125,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-31157","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.3 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 \u0444\u043e\u0440\u043c\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u043a.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/nl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"nl_NL\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47\u041f\u0430\u0440\u0430\u0434\u043e\u043a\u0441\u044b \u043e \u0441\u0436\u0430\u0442\u0438\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 \u0444\u043e\u0440\u043c\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u043a.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/nl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:39:48+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T18:39:48+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Paradoxen over datacompressie | ProHoster","description":"De datacompressietaak kan in zijn eenvoudigste vorm verwijzen naar.","canonical_url":"https:\/\/prohoster.info\/nl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"nl_NL","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041f\u0430\u0440\u0430\u0434\u043e\u043a\u0441\u044b \u043e \u0441\u0436\u0430\u0442\u0438\u0438 \u0434\u0430\u043d\u043d\u044b\u0445 | ProHoster","og:description":"\u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u0436\u0430\u0442\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 \u0444\u043e\u0440\u043c\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u043a.","og:url":"https:\/\/prohoster.info\/nl\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:39:48+00:00","article:modified_time":"2019-10-31T18:39:48+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"31157","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 04:46:21","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 03:21:33","updated":"2026-01-21 04:46:21","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/nl\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}