Faodaidh duilgheadas teannachadh dàta, anns an riochd as sìmplidh aige, ceangal a dhèanamh ri àireamhan agus na comharran aca. Faodar àireamhan a chomharrachadh le àireamhan ("aon-deug" airson an àireamh 11), abairtean matamataigeach ("dithis anns an fhicheadamh" airson 1048576), abairtean sreang ("còig naoi" airson 99999), ainmean ceart ("àireamh a' bhiast" airson 666, "bliadhna de bhàs Turing" airson 1954), no measgachadh neo-riaghailteach dheth. Tha sònrachadh sam bith freagarrach leis am faod an neach-conaltraidh dearbhadh gu soilleir dè an àireamh air a bheil sinn a 'bruidhinn. Gu follaiseach, innis don neach-conaltraidh agad "factaraidh ochd" nas èifeachdaiche na comharradh co-ionann "ceithir mìle tri cheud fichead". Tha ceist loidsigeach ag èirigh an seo: dè an comharradh as giorra airson àireamh sònraichte?
Chaidh am feallsanaiche Bertrand Russell fhoillseachadh ann an 1908 , a tha a’ suathadh air cùis comharrachadh àireamh bhon taobh eile: Dè an àireamh as lugha aig nach eil feum air ceithir fichead litir?
Feumaidh an àireamh seo a bhith ann: bho ochdad litrichean is beàrnan Ruiseanach chan urrainn dhut ach 3480 sònrachadh a dhèanamh, a tha a ’ciallachadh le bhith a’ cleachdadh ceithir fichead litir nach urrainn dhut barrachd air 3480 àireamh ainmeachadh. Tha seo a 'ciallachadh gu bheil e do-dhèanta àireamh sònraichte ainmeachadh gun a bhith nas fhaide na 3480 san dòigh seo.
Tha seo a’ ciallachadh gum bi an àireamh seo a rèir an t-sònrachadh "an àireamh as lugha airson nach eil ceithir fichead litir gu leòr", aig nach eil ach 78 litrichean! Air an aon làimh, feumaidh an àireamh seo a bhith ann; air an làimh eile, ma tha an àireamh seo ann, chan eil a shònrachadh a 'freagairt ris. Paradocs!
Is e an dòigh as fhasa air am paradocs seo a chuir às a bhith a’ toirt iomradh air neo-fhoirmealachd nan comharran beòil. Mar, mura biodh ach seata abairtean sònraichte ceadaichte anns a’ chomharra, mar sin "an àireamh as lugha airson nach eil ceithir fichead litir gu leòr" cha bhiodh e na chomharradh dligheach, ach tha comharran feumail mar sin "factaraidh ochd" bitheadh gabhail ris.
A bheil dòighean foirmeil ann cunntas a thoirt air an t-sreath (algorithm) de ghnìomhan air àireamhan? Tha, agus ann am pailteas - canar cànanan prògramadh riutha. An àite comharran beòil, cleachdaidh sinn prògraman (mar eisimpleir, ann am Python) a sheallas na h-àireamhan riatanach. Mar eisimpleir, airson còig nines tha am prògram freagarrach print("9"*5). Bidh ùidh againn fhathast anns a’ phrògram as giorra airson àireamh sònraichte. Canar fad a leithid de phrògram àireamhan; is e seo a’ chrìoch teòiridheach air am faodar àireamh ainmichte a dhlùthadh.
An àite paradox Berry, faodaidh sinn a-nis beachdachadh air fear coltach ris: Dè an àireamh as lugha nach eil prògram kilobyte gu leòr airson a thoirt a-mach?
Nì sinn reusanachadh san aon dòigh ris roimhe: tha teacsaichean 2561024 kilobyte ann, a tha a’ ciallachadh nach urrainn barrachd air àireamhan 2561024 a bhith air an toirt a-mach le prògraman kilobyte. Tha seo a’ ciallachadh nach urrainnear àireamh sònraichte nach eil nas motha na 2561024 a thoirt a-mach san dòigh seo.
Ach sgrìobhamaid prògram ann am Python a ghineas a h-uile teacsa kilobyte a dh’ fhaodadh a bhith ann, gan ruith airson a chuir gu bàs, agus ma chuireas iad a-mach àireamh, an uairsin cuiridh sinn an àireamh seo ri faclair an fheadhainn a tha ruigsinneach. Às deidh sgrùdadh a dhèanamh air a h-uile comas 2561024, ge bith dè cho fada ‘s a bheir e, bidh am prògram a’ coimhead airson an àireamh as lugha a tha a dhìth bhon fhaclair agus a ’clò-bhualadh an àireamh sin. Tha e follaiseach gum bi a leithid de phrògram a’ freagairt air kilobyte de chòd - agus gun toir e a-mach an dearbh àireamh nach gabh a chuir a-mach le prògram kilobyte!
Dè an glacadh a-nis? Chan urrainnear tuilleadh a thoirt air sgàth neo-fhoirmealachd a’ chomharra!
Ma tha thu troimh-a-chèile leis gu bheil feum aig a’ phrògram againn air ìre speurail de chuimhne airson a bhith ag obair - faclair (no sreath bheag) de eileamaidean 2561024 - faodaidh tu an aon rud a dhèanamh às aonais: airson gach aon de na h-àireamhan 2561024, an uair sin , rachaibh tro na 2561024 prògram a tha comasach, gus nach eil fear iomchaidh ann. Chan eil e gu diofar gum mair an leithid de sgrùdadh ùine mhòr: às deidh sgrùdadh nas lugha na (2561024) 2 paidhir bhon àireamh agus den phrògram, thig e gu crìch agus lorgaidh e an àireamh fìor ionmholta sin.
No an tig e gu crìch? Gu dearbh, am measg a h-uile prògram a thèid fheuchainn, bidh while True: pass (agus na analogues gnìomh aige) - agus cha tèid a’ chùis nas fhaide na bhith a ’dèanamh deuchainn air a leithid de phrògram!
Eu-coltach ri paradocs Berry, far an robh an glacadh ann an neo-fhoirmealachd a’ chomharra, anns an dàrna cùis tha ath-leasachadh againn air a dheagh chliù. . Is e an fhìrinn gu bheil e do-dhèanta an toradh aige a dhearbhadh bho phrògram ann an ùine chrìochnaichte. Gu sònraichte, iom-fhillteachd Kolmogorov : chan eil algairim ann a leigeadh, airson àireamh ainmichte, fad a' phrògram as giorra a chlò-bhualadh an àireamh seo a lorg; tha sin a’ ciallachadh nach eil fuasgladh sam bith ann do dhuilgheadas Berry - lorg fad an t-sònrachadh beòil as giorra airson àireamh ainmichte.
Source: www.habr.com