{"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\/de\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradoxien der Datenkomprimierung","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradoxien Die Aufgabe der Datenkompression kann in ihrer einfachsten Form Zahlen und deren Bezeichnungen betreffen. Zahlen k\u00f6nnen durch Zahlw\u00f6rter bezeichnet werden (\u201eelf\u201c<\/i> f\u00fcr die Zahl 11), mathematische Ausdr\u00fccke (\u201ezwei hoch zwanzig\u201c<\/i> f\u00fcr 1048576), textuelle Ausdr\u00fccke (\u201ef\u00fcnf Neunen\u201c<\/i> f\u00fcr 99999), Eigennamen (\u201eZahl des Biestes\u201c<\/i> f\u00fcr 666, \u201eJahr des Todes von Turing\u201c<\/i> f\u00fcr 1954), oder beliebigen Kombinationen davon. Jede Bezeichnung ist zul\u00e4ssig, wenn der Gespr\u00e4chspartner eindeutig bestimmen kann, um welche Zahl es sich handelt. Offensichtlich ist es effektiver, dem Gespr\u00e4chspartner \u201eFakult\u00e4t von acht\u201c<\/i> zu sagen als die \u00e4quivalente Bezeichnung \u201evierzigtausenddreihundertzwanzig\u201c<\/i>. Hier stellt sich die logische Frage: Welche Bezeichnung f\u00fcr die gegebene Zahl ist die k\u00fcrzeste?<\/p>\n

Der Philosoph Bertrand Russell ver\u00f6ffentlichte 1908 \u201eRussells Paradoxon\u201c<\/a><\/noindex>, das die Frage der Bezeichnungen von Zahlen von der anderen Seite betrachtet: Welche ist die kleinste Zahl, f\u00fcr die nicht genug achtzig Buchstaben zur Verf\u00fcgung stehen?<\/b>
\nEine solche Zahl muss existieren: Aus achtzig russischen Buchstaben und Leerzeichen k\u00f6nnen insgesamt nur 3480 Bezeichnungen gebildet werden, was bedeutet, dass mit achtzig Buchstaben nicht mehr als 3480 Zahlen bezeichnet werden k\u00f6nnen. Das bedeutet, dass eine Zahl, die nicht gr\u00f6\u00dfer als 3480 ist, auf diese Weise nicht benannt werden kann.<\/p>\n

Daher wird dieser Zahl die Bezeichnung \u201edie kleinste Zahl, f\u00fcr die nicht genug achtzig Buchstaben zur Verf\u00fcgung stehen\u201c<\/i>zugeordnet, die insgesamt 78 Buchstaben hat! Einerseits muss diese Zahl existieren; andererseits, wenn diese Zahl existiert, dann stimmt ihre Bezeichnung nicht mit ihr \u00fcberein. Ein Paradoxon!<\/a><\/noindex><\/p>\n

Der einfachste Weg, dieses Paradoxon abzutun, ist, auf die Informalit\u00e4t der verbalen Bezeichnungen zu verweisen. Man k\u00f6nnte sagen, dass, wenn nur eine konkret definierte Sammlung von Ausdr\u00fccken als Bezeichnungen zul\u00e4ssig w\u00e4re, dann \u201edie kleinste Zahl, f\u00fcr die nicht genug achtzig Buchstaben zur Verf\u00fcgung stehen\u201c<\/i> nicht als zul\u00e4ssige Bezeichnung g\u00e4lte, w\u00e4hrend praktisch n\u00fctzliche Bezeichnungen wie \u201eFakult\u00e4t von acht\u201c<\/i> zul\u00e4ssig blieben.<\/p>\n

Gibt es formale Methoden zur Beschreibung der Abfolge (Algorithmus) von Handlungen mit Zahlen? Ja, und in H\u00fclle und F\u00fclle \u2014 diese werden Programmiersprachen genannt. Lassen Sie uns anstelle von verbalen Bezeichnungen Programme verwenden (zum Beispiel in Python), die die ben\u00f6tigten Zahlen ausgeben. Zum Beispiel eignet sich f\u00fcr f\u00fcnf Neunen das Programm print(\"9\"*5)<\/code>. Wir werden weiterhin an dem k\u00fcrzesten Programm f\u00fcr eine gegebene Zahl interessiert sein. Die L\u00e4nge eines solchen Programms wird als kolmogorovsche Komplexit\u00e4t<\/a><\/noindex> der Zahl bezeichnet; dies ist die theoretische Grenze, bis zu der eine gegebene Zahl komprimiert werden kann.<\/p>\n

Anstelle des Berry-Paradoxons k\u00f6nnen wir jetzt ein \u00e4hnliches betrachten: Was ist die kleinste Zahl, f\u00fcr die ein kilobyte-Programm nicht ausreicht, um sie auszugeben?<\/b><\/p>\n

Wir werden die \u00dcberlegungen wie zuvor anstellen: Es gibt 2561024 kilobyte gro\u00dfe Texte, das bedeutet, dass mit kilobyte-Programmen nicht mehr als 2561024 Zahlen ausgegeben werden k\u00f6nnen. Das bedeutet, dass eine Zahl, die nicht gr\u00f6\u00dfer als 2561024 ist, auf diese Weise nicht ausgegeben werden kann.<\/p>\n

Aber wir werden ein Python-Programm schreiben, das alle m\u00f6glichen kilobyte-Texte generiert, sie ausf\u00fchrt, und wenn sie eine Zahl ausgeben \u2013 f\u00fcgt es diese Zahl dem erreichbaren W\u00f6rterbuch hinzu. Nach der Pr\u00fcfung aller 2561024 M\u00f6glichkeiten, egal wie lange das dauert \u2013 sucht das Programm nach der kleinsten Zahl, die im W\u00f6rterbuch fehlt, und gibt diese Zahl aus. Es scheint offensichtlich, dass ein solches Programm in einem kilobyte Code passt \u2013 und diejenige Zahl ausgibt, die mit einem kilobyte-Programm nicht ausgegeben werden kann!<\/p>\n

Was ist also der Haken jetzt? Man kann ihn nicht mehr auf die Unformalit\u00e4t der Bezeichnungen schieben!<\/p>\n

Wenn Sie sich Sorgen machen, dass unser Programm astronomisch viel Speicher ben\u00f6tigt, um zu arbeiten \u2013 ein W\u00f6rterbuch (oder ein Bit-Array) aus 2561024 Elementen \u2013 dann kann man das alles auch ohne es umsetzen: Man kann f\u00fcr jede der 2561024 Zahlen nacheinander alle 2561024 m\u00f6glichen Programme durchprobieren, bis man ein passendes findet. Es spielt keine Rolle, dass ein solches Durchprobieren sehr lange dauern wird: Nach der \u00dcberpr\u00fcfung von weniger als (2561024)2 Paaren aus Zahl und Programm wird es schlie\u00dflich enden und die besagte Zahl finden.<\/p>\n

Oder wird es nicht enden? Denn unter all den Programmen, die ausprobiert werden, wird man while True: pass<\/code> (und ihre funktionalen Analoga) treffen \u2013 und dann wird die \u00dcberpr\u00fcfung eines solchen Programms bereits nicht weitergehen!<\/p>\n

Im Gegensatz zum Berry-Paradoxon, in dem der Haken in der Unformalit\u00e4t der Bezeichnungen lag, haben wir im zweiten Fall eine gut maskierte Umformulierung der \u00abHalteproblem\u00bb<\/a><\/noindex>. Das Problem ist, dass man mit einem Programm nicht in endlicher Zeit dessen Ausgabe bestimmen kann. Insbesondere ist die kolmogorovsche Komplexit\u00e4t nicht berechenbar<\/a><\/noindex>Es gibt keinen Algorithmus, der es erm\u00f6glicht, f\u00fcr eine gegebene Zahl die L\u00e4nge des k\u00fcrzesten Programms zu finden, das diese Zahl ausgibt; das bedeutet, es gibt keine L\u00f6sung f\u00fcr die Berry-Aufgabe \u2014 die L\u00e4nge der k\u00fcrzesten verbalen Bezeichnung f\u00fcr eine gegebene Zahl zu finden.
\n
Quelle: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\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 […]<\/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\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Paradoxien der Datenkompression | ProHoster","description":"Das Datenkompressionsproblem kann in seiner einfachsten Form mit etwas in Verbindung gebracht werden.","canonical_url":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"de_DE","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\/de\/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\/de\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/de\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}