La problemo de kunpremado de datumoj, en sia plej simpla formo, povas rilati al nombroj kaj iliaj notacioj. Nombroj povas esti signitaj per numeraloj ("dek unu" por la numero 11), matematikaj esprimoj ("du en la dudeka" por 1048576), ĉenaj esprimoj ("kvin naŭoj" por 99999), propraj nomoj ("nombro de la besto" por 666, "jaro de la morto de Turing" por 1954), aŭ arbitraj kombinaĵoj de tio. Ajna nomo taŭgas, per kiu la interparolanto povas klare determini, pri kiu nombro ni parolas. Evidente, diru al via interparolanto "faktoro de ok" pli efika ol ekvivalenta notacio "kvardek mil tricent dudek". Logika demando ekestas ĉi tie: kio estas la plej mallonga notacio por donita nombro?
La filozofo Bertrand Russell publikigis en 1908 , kiu tuŝas la aferon de nombronotacio de la kontraŭa flanko: Kio estas la plej malgranda nombro, kiu ne postulas okdek literojn?
Tia nombro devas ekzisti: el okdek rusaj literoj kaj spacoj oni povas konsistigi nur 3480 nomojn, kio signifas, ke uzante okdek literojn oni povas indiki ne pli ol 3480 nombrojn. Ĉi tio signifas, ke estas neeble indiki certan nombron ne pli ol 3480 tiamaniere.
Ĉi tio signifas, ke ĉi tiu nombro respondas al la nomo "la plej malgranda nombro por kiu okdek literoj ne sufiĉas", kiu havas nur 78 literojn! Unuflanke, ĉi tiu nombro devas ekzisti; aliflanke, se ĉi tiu nombro ekzistas, tiam ĝia nomo ne respondas al ĝi. Paradokso!
La plej facila maniero malakcepti tiun paradokson estas rilati al la neformaleco de vortaj notacioj. Kiel, se nur specife difinita aro de esprimoj estus permesita en la notacio, tiam "la plej malgranda nombro por kiu okdek literoj ne sufiĉas" ne estus valida notacio, dum praktike utilaj notacioj kiel "faktoro de ok" restus akceptebla.
Ĉu ekzistas formalaj manieroj priskribi la sinsekvon (algoritmon) de agoj pri nombroj? Estas, kaj abunde - ili nomiĝas programlingvoj. Anstataŭ vortaj notacioj, ni uzos programojn (ekzemple en Python) kiuj montras la postulatajn nombrojn. Ekzemple, por kvin naŭoj la programo taŭgas print("9"*5). Ni daŭre interesiĝos pri la plej mallonga programo por difinita nombro. La longeco de tia programo estas nomita nombroj; ĝi estas la teoria limo al kiu donita nombro povas esti kunpremita.
Anstataŭ la paradokso de Berry, ni nun povas konsideri similan: Kio estas la plej malgranda nombro, kiun kilobajta programo ne sufiĉas por eligi?
Ni rezonos same kiel antaŭe: ekzistas 2561024 kilobajtaj tekstoj, kio signifas, ke ne pli ol 2561024 nombroj povas esti eligitaj per kilobajtaj programoj. Ĉi tio signifas, ke certa nombro ne pli granda ol 2561024 ne povas esti derivita tiamaniere.
Sed ni skribu programon en Python, kiu generas ĉiujn eblajn kilobajtajn tekstojn, rulas ilin por ekzekuto, kaj se ili eligas nombron, tiam aldonas ĉi tiun numeron al la vortaro de atingeblaj. Kontrolinte ĉiujn 2561024 XNUMX XNUMX eblecojn, kiom ajn longe ĝi daŭras, la programo serĉas la plej malgrandan nombron mankantan en la vortaro kaj presas tiun nombron. Ŝajnas evidente, ke tia programo konvenos al kilobajto da kodo - kaj eligos la numeron mem, kiu ne povas esti eligita per kilobajta programo!
Kio estas la kapto nun? Ĝi ne plu povas esti atribuita al la neformaleco de la notacio!
Se vi estas konfuzita de la fakto, ke nia programo postulos astronomian kvanton da memoro por funkcii - vortaro (aŭ bita tabelo) de 2561024 elementoj - tiam vi povas fari la samon sen ĝi: por ĉiu el la 2561024 nombroj, laŭvice. , trairu ĉiujn 2561024 eblajn programojn, ĝis ne estas taŭga. Ne gravas, ke tia serĉado daŭros tre longe: post kontrolo de malpli ol (2561024)2 paroj el la nombro kaj la programo, ĝi finiĝos kaj trovos tiun tre ŝatatan nombron.
Aŭ ĉu ĝi ne finiĝos? Efektive, inter ĉiuj programoj, kiuj estos provitaj, estos while True: pass (kaj ĝiaj funkciaj analogoj) - kaj la afero ne iros pli ol provi tian programon!
Male al la paradokso de Berry, kie la kapto estis en la neformaleco de la notacio, en la dua kazo ni havas bone kaŝvestitan reformulon . La fakto estas, ke estas neeble determini ĝian eliron de programo en finia tempo. Aparte, Kolmogorov komplekseco : ne ekzistas algoritmo kiu permesus, por donita nombro, trovi la longon de la plej mallonga programo kiu presas ĉi tiun nombron; kio signifas, ke ne ekzistas solvo al la problemo de Berry - trovi la longon de la plej mallonga vorta nomo por donita nombro.
fonto: www.habr.com