{"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\/es\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","title":{"rendered":"Paradojas sobre la compresi\u00f3n de datos","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Paradojas La tarea de compresi\u00f3n de datos en su forma m\u00e1s simple puede referirse a n\u00fameros y sus designaciones. Los n\u00fameros pueden ser representados por numerales (\u00abonce\u00bb<\/i> para el n\u00famero 11), expresiones matem\u00e1ticas (\u00abdos a la veinte\u00bb<\/i> para 1048576), expresiones en cadena (\u00abcinco nueves\u00bb<\/i> para 99999), nombres propios (\u00abel n\u00famero de la bestia\u00bb<\/i> para 666, \u00abel a\u00f1o de la muerte de Turing\u00bb<\/i> para 1954), o combinaciones arbitrarias de estos. Cualquier designaci\u00f3n que permita al interlocutor identificar de manera inequ\u00edvoca de qu\u00e9 n\u00famero se trata es v\u00e1lida. Es evidente que comunicar al interlocutor \u00abel factorial de ocho\u00bb<\/i> es m\u00e1s eficiente que la designaci\u00f3n equivalente \u00abcuarenta mil trescientos veinte\u00bb<\/i>. Surge la pregunta l\u00f3gica: \u00bfcu\u00e1l designaci\u00f3n es la m\u00e1s corta para un n\u00famero dado?<\/p>\n

El fil\u00f3sofo Bertrand Russell public\u00f3 en 1908 \u00abel paradoja de Berry\u00bb<\/a><\/noindex>, que aborda la cuesti\u00f3n de las designaciones de n\u00fameros desde el lado opuesto: \u00bfcu\u00e1l es el n\u00famero m\u00e1s peque\u00f1o para el cual no hay suficientes letras para su designaci\u00f3n?<\/b>
\nTal n\u00famero debe existir: de ochenta letras rusas y espacios se pueden formar solo 3480 designaciones, por lo que usando ochenta letras no se puede designar m\u00e1s de 3480 n\u00fameros. Por lo tanto, hay un n\u00famero que no puede ser designado de esta manera, que es a lo sumo 3480.<\/p>\n

Por lo tanto, a este n\u00famero le corresponder\u00e1 la designaci\u00f3n \u00abel n\u00famero m\u00e1s peque\u00f1o para el cual no hay suficientes letras para su designaci\u00f3n\u00bb<\/i>, que contiene solo 78 letras. \u00a1Por un lado, este n\u00famero debe existir; por otro, si este n\u00famero existe, entonces su designaci\u00f3n no le corresponde. \u00a1Paradoja!<\/a><\/noindex><\/p>\n

La manera m\u00e1s sencilla de deshacerse de esta paradoja es referirse a la informalidad de las designaciones verbales. Se dir\u00eda que si solo se permitieran un conjunto espec\u00edfico de expresiones, entonces \u00abel n\u00famero m\u00e1s peque\u00f1o para el cual no hay suficientes letras para su designaci\u00f3n\u00bb<\/i> no ser\u00eda una designaci\u00f3n permisible, mientras que designaciones pr\u00e1cticamente \u00fatiles como \u00abel factorial de ocho\u00bb<\/i> seguir\u00edan siendo permisibles.<\/p>\n

\u00bfExisten formas formales de describir una secuencia (algoritmo) de acciones sobre n\u00fameros? S\u00ed, y en abundancia: se denominan lenguajes de programaci\u00f3n. En lugar de designaciones verbales, utilizaremos programas (por ejemplo, en Python) que generen los n\u00fameros necesarios. Por ejemplo, para cinco nueves se puede usar el programa print(\"9\"*5)<\/code>. Seguiremos interesados en el programa m\u00e1s corto para un n\u00famero dado. La longitud de dicho programa se llama complejidad de Kolmogorov<\/a><\/noindex> del n\u00famero; este es el l\u00edmite te\u00f3rico al que se puede comprimir un n\u00famero dado.<\/p>\n

En lugar del paradoja de Berry, ahora podemos considerar uno similar: \u00bfcu\u00e1l es el n\u00famero m\u00e1s peque\u00f1o que no puede ser producido por un programa de kilobyte?<\/b><\/p>\n

Razonaremos de la misma manera que antes: existen 2561024 textos de kilobyte, lo que significa que con programas de kilobyte se pueden producir no m\u00e1s de 2561024 n\u00fameros. Por lo tanto, existe un n\u00famero, no mayor que 2561024, que no se puede generar de esta manera.<\/p>\n

Pero escribamos un programa en Python que genere todos los textos posibles de kilobyte, los ejecute, y si producen alg\u00fan n\u00famero, lo agregue al diccionario de alcanzables. Despu\u00e9s de verificar todas las 2561024 posibilidades, por mucho tiempo que tome, el programa busca cu\u00e1l es el n\u00famero m\u00e1s peque\u00f1o que falta en el diccionario y lo imprime. Parece obvio que tal programa cabr\u00eda en un kilobyte de c\u00f3digo y producir\u00eda ese n\u00famero que no se puede generar con programas de kilobyte.<\/p>\n

\u00bfCu\u00e1l es entonces el truco ahora? \u00a1No se puede atribuir esto a la informalidad de los t\u00e9rminos!<\/p>\n

Si te preocupa que nuestro programa requiera una cantidad astron\u00f3mica de memoria para funcionar \u2014un diccionario (o un array de bits) de 2561024 elementos\u2014 se puede hacer todo lo mismo sin ello: para cada uno de los 2561024 n\u00fameros, probar uno a uno todos los 2561024 programas posibles, hasta encontrar uno que funcione. No importa que tal esfuerzo dure mucho tiempo: tras comprobar menos de (2561024)2 pares de n\u00fameros y programas, el proceso terminar\u00e1 y encontrar\u00e1 ese n\u00famero tan anhelado.<\/p>\n

\u00bfO no terminar\u00e1? Despu\u00e9s de todo, entre todos los programas que se probar\u00e1n, se encontrar\u00e1 while True: pass<\/code> y sus an\u00e1logos funcionales \u2014y ah\u00ed se detendr\u00e1 cualquier verificaci\u00f3n de dicho programa!<\/p>\n

A diferencia de la paradoja de Berry, donde el truco estaba en la informalidad de los t\u00e9rminos, en este segundo caso tenemos una reformulaci\u00f3n bien disfrazada de el 'problema de la detenci\u00f3n'.<\/a><\/noindex>El hecho es que no se puede determinar su salida en un tiempo finito. En particular, la complejidad de Kolmogorov es no computable.<\/a><\/noindex>: no hay ning\u00fan algoritmo que permita, para un n\u00famero dado, encontrar la longitud del programa m\u00e1s corto que produzca ese n\u00famero; por lo tanto, no hay soluci\u00f3n para el problema de Berry: encontrar la longitud de la representaci\u00f3n verbal m\u00e1s corta de un n\u00famero dado.
\n
Fuente: 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\udd47Paradojas sobre la compresi\u00f3n de datos | ProHoster","description":"El problema de compresi\u00f3n de datos en su forma m\u00e1s simple puede referirse a.","canonical_url":"https:\/\/prohoster.info\/es\/blog\/administrirovanie\/paradoksy-o-szhatii-dannyh","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"es_ES","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\/es\/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\/es\/wp-json\/wp\/v2\/posts\/31157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/comments?post=31157"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts\/31157\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media\/23125"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media?parent=31157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/categories?post=31157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/tags?post=31157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}