{"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":"Datenkompressions-Paradoxien","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Datenkompressions-Paradoxien\" Die Aufgabe der Datenkompression kann in ihrer einfachsten Form auf Zahlen und deren Bezeichnungen bezogen werden. Zahlen k\u00f6nnen mit numerischen W\u00f6rtern (\u201eelf\u201c<\/i> f\u00fcr die Zahl 11), mathematischen Ausdr\u00fccken (\u201ezwei hoch zwanzig\u201c<\/i> f\u00fcr 1048576), Zeichenfolgen (\u201ef\u00fcnf Neunern\u201c<\/i> f\u00fcr 99999), Eigennamen (\u201eZahl des Tieres\u201c<\/i> f\u00fcr 666, \u201eJahr des Todes von Turing\u201c<\/i> f\u00fcr 1954) oder beliebigen Kombinationen davon bezeichnet werden. Jegliche Bezeichnung, die es dem Gespr\u00e4chspartner erm\u00f6glicht, eindeutig zu bestimmen, von welcher Zahl die Rede ist, ist zul\u00e4ssig. Offensichtlich ist es effektiver, dem Gespr\u00e4chspartner zu sagen \u201eFakult\u00e4t von acht\u201c<\/i> als die \u00e4quivalente Bezeichnung \u201evierzigtausenddreihundertzwanzig\u201c<\/i>. Hier stellt sich die logische Frage: Welche Bezeichnung f\u00fcr eine gegebene Zahl ist die k\u00fcrzeste?<\/p>\n

Der Philosoph Bertrand Russell ver\u00f6ffentlichte 1908 \u201eBerrys Paradox\u201c<\/a><\/noindex>, das die Frage der Zahlbezeichnungen von der entgegengesetzten Seite betrachtet: Welches ist die kleinste Zahl, f\u00fcr die nicht achtzig Buchstaben ausreichen?<\/b>
\nEine solche Zahl muss existieren: Aus achtzig russischen Buchstaben und Leerzeichen k\u00f6nnen insgesamt nur 3480 Bezeichnungen gebildet werden, was bedeutet, dass mit den achtzig Buchstaben nicht mehr als 3480 Zahlen bezeichnet werden k\u00f6nnen. Somit ist es unm\u00f6glich, eine bestimmte Zahl, die kleiner oder gleich 3480 ist, auf diese Weise zu bezeichnen.<\/p>\n

Daher wird dieses Zahl eine Bezeichnung erhalten \u201edie kleinste Zahl, f\u00fcr die nicht ausreichend achtzig Buchstaben zur Verf\u00fcgung stehen\u201c<\/i>, die nur 78 Buchstaben umfasst! Einerseits muss diese Zahl existieren; andererseits, wenn diese Zahl existiert, dann entspricht ihre Bezeichnung nicht ihr. Ein Paradoxon!<\/a><\/noindex><\/p>\n

Der einfachste Weg, dieses Paradoxon abzutun, ist, sich auf die Unformalit\u00e4t sprachlicher Bezeichnungen zu berufen. Es w\u00e4re sozusagen nicht zul\u00e4ssig, nur einen konkret definierten Satz von Ausdr\u00fccken zuzulassen, denn \u201edie kleinste Zahl, f\u00fcr die nicht ausreichend achtzig Buchstaben zur Verf\u00fcgung stehen\u201c<\/i> w\u00e4re keine zul\u00e4ssige Bezeichnung, w\u00e4hrend praktisch n\u00fctzliche Bezeichnungen wie \u201eFakult\u00e4t von acht\u201c<\/i> zul\u00e4ssig bleiben w\u00fcrden.<\/p>\n

Gibt es formale M\u00f6glichkeiten, die Abfolge von Aktionen mit Zahlen zu beschreiben? Ja, und zwar reichlich \u2013 diese werden Programmiersprachen genannt. Statt schriftlicher Bezeichnungen verwenden wir Programme (zum Beispiel in Python), die die gew\u00fcnschten Zahlen ausgeben. Beispielsweise k\u00f6nnte folgendes Programm f\u00fcr f\u00fcnf Neunen verwendet werden: print(\"9\"*5)<\/code>. Auch hier interessiert uns weiterhin das k\u00fcrzeste Programm f\u00fcr eine gegebene Zahl. Die L\u00e4nge eines solchen Programms bezeichnet man als Kolmogorov-Komplexit\u00e4t<\/a><\/noindex> der Zahl; dies ist die theoretische Grenze, bis zu der eine bestimmte Zahl komprimiert werden kann.<\/p>\n

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

Wir werden ebenso argumentieren wie zuvor: Es gibt 2561024 Kilobyte-Textinhalte, das hei\u00dft, mit Kilobyte-Programmen k\u00f6nnen nicht mehr als 2561024 Zahlen ausgegeben werden. Das bedeutet, dass eine bestimmte Zahl, die nicht gr\u00f6\u00dfer als 2561024 ist, auf diese Weise nicht ausgegeben werden kann.<\/p>\n

Aber wir schreiben ein Programm in Python, das alle m\u00f6glichen Kilobyte-Texte generiert, sie zur Ausf\u00fchrung bringt und, falls sie eine Zahl ausgeben, diese Zahl dem W\u00f6rterbuch der erreichbaren Zahlen hinzuf\u00fcgt. Nachdem alle 2561024 M\u00f6glichkeiten \u00fcberpr\u00fcft sind, egal wie viel Zeit das in Anspruch nimmt \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 Platz finden kann und genau die Zahl ausgeben wird, die mit einem Kilobyte Programm nicht ausgegeben werden kann!<\/p>\n

Was ist jetzt der Haken? Man kann die Informalit\u00e4t der Bezeichnungen jetzt nicht mehr darauf abw\u00e4lzen!<\/p>\n

Wenn Sie besorgt sind, dass unser Programm eine astronomische Menge an Speicher f\u00fcr die Ausf\u00fchrung ben\u00f6tigt \u2013 ein W\u00f6rterbuch (oder Bit-Array) aus 2561024 Elementen \u2013 dann kann man all das auch ohne erreichen: F\u00fcr jede der 2561024 Zahlen nacheinander alle 2561024 m\u00f6glichen Programme durchprobieren, bis das passende gefunden wird. Es ist unerheblich, dass ein solcher Versuch sehr lange dauern wird: Nach der \u00dcberpr\u00fcfung von weniger als (2561024)2 Paaren aus Zahl und Programm wird es schlie\u00dflich enden und diese eine geheime Zahl finden.<\/p>\n

Oder wird es nicht enden? Denn unter all den Programmen, die ausprobiert werden, trifft man auf while True: pass<\/code> (und ihre funktionalen Analogien) \u2013 und damit wird die Pr\u00fcfung eines solchen Programms nicht vorankommen!<\/p>\n

Im Gegensatz zum Berry-Paradoxon, wo die Irref\u00fchrung in der Unformalit\u00e4t der Bezeichnungen lag, haben wir hier eine gut getarnte Umformulierung \u201eHaltbarkeitsproblem\u201c<\/a><\/noindex>. Die Sache ist die, dass es f\u00fcr das Programm unm\u00f6glich ist, innerhalb einer endlichen Zeit dessen Ausgabe zu bestimmen. Insbesondere ist die kolmogorovsche Komplexit\u00e4t unberechenbar<\/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; somit gibt es auch keine L\u00f6sung f\u00fcr das Berry-Problem \u2013 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":"Die Datenkompression kann in ihrer einfachsten Form mit Zahlen und deren Bezeichnungen in Verbindung gebracht werden. Zahlen k\u00f6nnen durch Ziffern (\"elf\" f\u00fcr die Zahl 11), mathematische Ausdr\u00fccke (\"zwei zur zwanzigsten\" f\u00fcr 1048576), Textausdr\u00fccke (\"f\u00fcnf Neunen\" f\u00fcr 99999), Eigennamen (\"Zahl des Tieres\" f\u00fcr 666, \"Jahr des Todes von Turing\" f\u00fcr 1954) oder beliebige Kombinationen davon bezeichnet werden. Jede Bezeichnung ist zul\u00e4ssig, solange sie klar ist.","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 \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","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"},"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}]}}