Gall problem cywasgu data, yn ei ffurf symlaf, ymwneud â rhifau a'u nodiant. Gellir dynodi rhifau gyda rhifolion ("un ar ddeg" ar gyfer y rhif 11), mynegiadau mathemategol ("dau yn yr ugeinfed" ar gyfer 1048576), mynegiadau llinynnol ("pump naw" ar gyfer 99999), enwau priod ("rhif y bwystfil" am 666, "blwyddyn marwolaeth Turing" ar gyfer 1954), neu gyfuniadau mympwyol ohonynt. Mae unrhyw ddynodiad yn addas er mwyn i'r cydlynydd benderfynu'n glir pa rif yr ydym yn sôn amdano. Yn amlwg, dywedwch wrth eich interlocutor "ffatri o wyth" yn fwy effeithlon na nodiant cyfatebol "deugain mil tri chant dau ddeg". Mae cwestiwn rhesymegol yn codi yma: beth yw'r nodiant byrraf ar gyfer rhif penodol?
Cyhoeddodd yr athronydd Bertrand Russell ym 1908 , sy’n cyffwrdd â mater nodiant rhif o’r ochr arall: Beth yw'r nifer lleiaf nad oes angen pedwar ugain o lythyrau arno?
Mae'n rhaid i rif o'r fath fodoli: o wyth deg o lythrennau a bylchau Rwsiaidd gallwch chi wneud dim ond 3480 o ddynodiadau, sy'n golygu na allwch chi ddynodi mwy na 3480 o rifau gan ddefnyddio wyth deg o lythyrau. Mae hyn yn golygu ei bod yn amhosibl dynodi nifer penodol heb fod yn fwy na 3480 yn y modd hwn.
Mae hyn yn golygu y bydd y rhif hwn yn cyfateb i'r dynodiad "y nifer lleiaf lle nad yw wyth deg o lythyrau yn ddigon", sydd heb ond 78 o lythyrau ! Ar y naill law, rhaid fod y rhif hwn ; ar y llaw arall, os yw'r rhif hwn yn bodoli, yna nid yw ei ddynodiad yn cyfateb iddo. Paradocs!
Y ffordd hawsaf o ddiystyru’r paradocs hwn yw cyfeirio at anffurfioldeb nodiannau geiriol. Fel, pe bai dim ond set o ymadroddion wedi'u diffinio'n benodol yn cael eu caniatáu yn y nodiant, yna "y nifer lleiaf lle nad yw wyth deg o lythyrau yn ddigon" Ni fyddai'n nodiant dilys, tra bod nodiannau ymarferol ddefnyddiol fel "ffatri o wyth" yn parhau i fod yn dderbyniol.
A oes ffyrdd ffurfiol o ddisgrifio dilyniant (algorithm) gweithredoedd ar rifau? Mae yna, ac mewn digonedd - fe'u gelwir yn ieithoedd rhaglennu. Yn lle nodiant geiriol, byddwn yn defnyddio rhaglenni (er enghraifft, yn Python) sy'n dangos y niferoedd gofynnol. Er enghraifft, am bump naw mae'r rhaglen yn addas print("9"*5). Byddwn yn parhau i fod â diddordeb yn y rhaglen fyrraf ar gyfer nifer penodol. Gelwir hyd rhaglen o'r fath niferoedd; dyma'r terfyn damcaniaethol y gellir cywasgu rhif penodol iddo.
Yn lle paradocs Berry, gallwn nawr ystyried un tebyg: Beth yw'r nifer lleiaf nad yw rhaglen kilobyte yn ddigon i'w allbynnu?
Byddwn yn rhesymu yn yr un modd ag o'r blaen: mae 2561024 o destunau kilobyte, sy'n golygu na ellir allbwn mwy na 2561024 o rifau gan raglenni kilobyte. Mae hyn yn golygu na ellir dod o hyd i nifer penodol heb fod yn fwy na 2561024 yn y modd hwn.
Ond gadewch i ni ysgrifennu rhaglen yn Python sy'n cynhyrchu'r holl destunau kilobyte posibl, yn eu rhedeg i'w gweithredu, ac os ydyn nhw'n allbynnu rhif, yna'n ychwanegu'r rhif hwn at y geiriadur o rai cyraeddadwy. Ar ôl gwirio pob un o'r 2561024 o bosibiliadau, ni waeth pa mor hir y mae'n ei gymryd, mae'r rhaglen yn edrych am y nifer lleiaf sydd ar goll o'r geiriadur ac yn argraffu'r rhif hwnnw. Mae'n amlwg y bydd rhaglen o'r fath yn ffitio i mewn i kilobyte o god - ac yn allbynnu'r union nifer na all rhaglen kilobyte ei allbynnu!
Beth yw'r dalfa nawr? Ni ellir bellach ei briodoli i anffurfioldeb y nodiant!
Os ydych chi'n cael eich drysu gan y ffaith y bydd ein rhaglen angen swm seryddol o gof i weithio - geiriadur (neu amrywiaeth didau) o 2561024 o elfennau - yna gallwch chi wneud yr un peth hebddo: ar gyfer pob un o'r rhifau 2561024, yn eu tro , ewch trwy bob 2561024 o raglenni posibl, nes nad oes un addas. Nid oes ots y bydd chwiliad o'r fath yn para am amser hir iawn: ar ôl gwirio llai na (2561024) 2 barau o'r rhif a'r rhaglen, bydd yn dod i ben ac yn dod o hyd i'r rhif annwyl iawn hwnnw.
Neu oni fydd yn gorffen? Yn wir, ymhlith yr holl raglenni y rhoddir cynnig arnynt, bydd while True: pass (a'i analogau swyddogaethol) - ac ni fydd y mater yn mynd ymhellach na phrofi rhaglen o'r fath!
Yn wahanol i baradocs Berry, lle’r oedd y dalfa yn anffurfioldeb y nodiant, yn yr ail achos mae gennym ailfformiwleiddiad sydd wedi’i guddio’n dda. . Y ffaith yw ei bod yn amhosibl pennu ei allbwn o raglen mewn amser cyfyngedig. Yn benodol, Kolmogorov cymhlethdod : nid oes algorithm a fyddai'n caniatáu, ar gyfer rhif penodol, ganfod hyd y rhaglen fyrraf sy'n argraffu'r rhif hwn; sy’n golygu nad oes ateb i broblem Berry – dod o hyd i hyd y dynodiad geiriol byrraf ar gyfer rhif penodol.
Ffynhonnell: hab.com