డేటా కంప్రెషన్ సమస్య, దాని సరళమైన రూపంలో, సంఖ్యలు మరియు వాటి సంజ్ఞామానాలకు సంబంధించినది. సంఖ్యలను సంఖ్యల ద్వారా సూచించవచ్చు ("పదకొండు" సంఖ్య 11 కోసం), గణిత వ్యక్తీకరణలు ("ఇరవైలో రెండు" 1048576 కోసం), స్ట్రింగ్ వ్యక్తీకరణలు ("ఐదు తొమ్మిది" 99999 కోసం), సరైన పేర్లు ("మృగం యొక్క సంఖ్య" 666 కోసం, "ట్యూరింగ్ మరణించిన సంవత్సరం" 1954 కోసం), లేదా వాటి ఏకపక్ష కలయికలు. ఏదైనా హోదా అనుకూలంగా ఉంటుంది, దీని ద్వారా సంభాషణకర్త మనం ఏ సంఖ్య గురించి మాట్లాడుతున్నామో స్పష్టంగా నిర్ణయించవచ్చు. సహజంగానే, మీ సంభాషణకర్తకు చెప్పండి "ఎనిమిది కారకం" సమానమైన సంజ్ఞామానం కంటే మరింత సమర్థవంతమైనది "నలభై వేల మూడు వందల ఇరవై". ఇక్కడ ఒక తార్కిక ప్రశ్న తలెత్తుతుంది: ఇచ్చిన సంఖ్యకు అతి చిన్న సంజ్ఞామానం ఏమిటి?
తత్వవేత్త బెర్ట్రాండ్ రస్సెల్ 1908లో ప్రచురించారు , ఇది వ్యతిరేక వైపు నుండి సంఖ్య సంజ్ఞామానం సమస్యను తాకుతుంది: ఎనభై అక్షరాలు అవసరం లేని అతి చిన్న సంఖ్య ఏది?
అటువంటి సంఖ్య తప్పనిసరిగా ఉండాలి: ఎనభై రష్యన్ అక్షరాలు మరియు ఖాళీల నుండి మీరు 3480 హోదాలను మాత్రమే తయారు చేయవచ్చు, అంటే ఎనభై అక్షరాలను ఉపయోగించి మీరు 3480 కంటే ఎక్కువ సంఖ్యలను నియమించలేరు. ఈ విధంగా నిర్దిష్ట సంఖ్యను 3480 కంటే ఎక్కువ పేర్కొనడం అసాధ్యం అని దీని అర్థం.
ఈ సంఖ్య హోదాకు అనుగుణంగా ఉంటుందని దీని అర్థం "ఎనభై అక్షరాలు సరిపోని అతి చిన్న సంఖ్య", ఇందులో 78 అక్షరాలు మాత్రమే ఉన్నాయి! ఒక వైపు, ఈ సంఖ్య తప్పనిసరిగా ఉండాలి; మరోవైపు, ఈ సంఖ్య ఉన్నట్లయితే, దాని హోదా దానికి అనుగుణంగా ఉండదు. పారడాక్స్!
ఈ వైరుధ్యాన్ని తోసిపుచ్చడానికి సులభమైన మార్గం మౌఖిక సంకేతాల యొక్క అనధికారికతను సూచించడం. ఇలా, సంజ్ఞామానంలో ప్రత్యేకంగా నిర్వచించబడిన వ్యక్తీకరణల సమితిని మాత్రమే అనుమతించినట్లయితే, అప్పుడు "ఎనభై అక్షరాలు సరిపోని అతి చిన్న సంఖ్య" చెల్లుబాటు అయ్యే సంజ్ఞామానం కాదు, అయితే ఆచరణాత్మకంగా ఉపయోగకరమైన సంజ్ఞామానాలు వంటివి "ఎనిమిది కారకం" ఆమోదయోగ్యంగా ఉంటుంది.
సంఖ్యలపై చర్యల క్రమాన్ని (అల్గోరిథం) వివరించడానికి అధికారిక మార్గాలు ఉన్నాయా? ఉన్నాయి, మరియు సమృద్ధిగా - వాటిని ప్రోగ్రామింగ్ భాషలు అంటారు. శబ్ద సంజ్ఞామానాలకు బదులుగా, అవసరమైన సంఖ్యలను ప్రదర్శించే ప్రోగ్రామ్‌లను (ఉదాహరణకు, పైథాన్‌లో) ఉపయోగిస్తాము. ఉదాహరణకు, ఐదు తొమ్మిది కోసం ప్రోగ్రామ్ అనుకూలంగా ఉంటుంది print("9"*5). మేము ఇచ్చిన సంఖ్య కోసం చిన్నదైన ప్రోగ్రామ్‌పై ఆసక్తిని కొనసాగిస్తాము. అటువంటి ప్రోగ్రామ్ యొక్క పొడవు అంటారు సంఖ్యలు; ఇది ఇచ్చిన సంఖ్యను కుదించగల సైద్ధాంతిక పరిమితి.
బెర్రీ యొక్క పారడాక్స్‌కు బదులుగా, మనం ఇప్పుడు ఇలాంటిదే పరిగణించవచ్చు: అవుట్‌పుట్ చేయడానికి కిలోబైట్ ప్రోగ్రామ్ సరిపోని అతి చిన్న సంఖ్య ఏది?
మేము మునుపటి విధంగానే తర్కించాము: 2561024 కిలోబైట్ టెక్స్ట్‌లు ఉన్నాయి, అంటే కిలోబైట్ ప్రోగ్రామ్‌ల ద్వారా 2561024 కంటే ఎక్కువ సంఖ్యలు అవుట్‌పుట్ చేయబడవు. దీనర్థం 2561024 కంటే ఎక్కువ లేని నిర్దిష్ట సంఖ్యను ఈ విధంగా పొందలేము.
అయితే సాధ్యమయ్యే అన్ని కిలోబైట్ టెక్స్ట్‌లను రూపొందించే ప్రోగ్రామ్‌ను పైథాన్‌లో వ్రాద్దాం, వాటిని అమలు చేయడానికి అమలు చేయండి మరియు అవి ఒక సంఖ్యను అవుట్‌పుట్ చేస్తే, ఈ నంబర్‌ను రీచ్ అయ్యే వాటి నిఘంటువుకి జోడిస్తుంది. మొత్తం 2561024 సాధ్యాసాధ్యాలను తనిఖీ చేసిన తర్వాత, ఎంత సమయం పట్టినా, డిక్షనరీలో లేని చిన్న సంఖ్య కోసం ప్రోగ్రామ్ వెతుకుతుంది మరియు ఆ సంఖ్యను ప్రింట్ చేస్తుంది. అటువంటి ప్రోగ్రామ్ కిలోబైట్ కోడ్‌కి సరిపోతుందని స్పష్టంగా కనిపిస్తోంది - మరియు కిలోబైట్ ప్రోగ్రామ్ ద్వారా అవుట్‌పుట్ చేయలేని సంఖ్యను అవుట్‌పుట్ చేస్తుంది!
ఇప్పుడు క్యాచ్ ఏమిటి? ఇది ఇకపై సంజ్ఞామానం యొక్క అనధికారికతకు ఆపాదించబడదు!
2561024 మూలకాల యొక్క నిఘంటువు (లేదా బిట్ శ్రేణి) - మా ప్రోగ్రామ్ పని చేయడానికి ఖగోళ సంబంధమైన మెమరీ అవసరమని మీరు గందరగోళానికి గురైతే, అది లేకుండా మీరు అదే పనిని చేయవచ్చు: ప్రతి 2561024 సంఖ్యలకు. , అన్ని 2561024 సాధ్యమయ్యే ప్రోగ్రామ్‌ల ద్వారా వెళ్లండి, తగినది ఏదీ ఉండదు. అటువంటి శోధన చాలా కాలం పాటు కొనసాగుతుందని పట్టింపు లేదు: సంఖ్య మరియు ప్రోగ్రామ్ నుండి (2561024) 2 జతల కంటే తక్కువ తనిఖీ చేసిన తర్వాత, అది ముగుస్తుంది మరియు చాలా ప్రతిష్టాత్మకమైన సంఖ్యను కనుగొంటుంది.
లేక పూర్తి కాదా? నిజమే, ప్రయత్నించబడే అన్ని ప్రోగ్రామ్‌లలో, ఉంటుంది while True: pass (మరియు దాని ఫంక్షనల్ అనలాగ్‌లు) - మరియు అటువంటి ప్రోగ్రామ్‌ను పరీక్షించడం కంటే విషయం ముందుకు సాగదు!
బెర్రీ యొక్క పారడాక్స్ వలె కాకుండా, క్యాచ్ సంజ్ఞామానం యొక్క అనధికారికతలో ఉంది, రెండవ సందర్భంలో మనకు బాగా మారువేషంలో ఉన్న సంస్కరణ ఉంది. . వాస్తవం ఏమిటంటే, ప్రోగ్రామ్ నుండి దాని అవుట్‌పుట్‌ను పరిమిత సమయంలో గుర్తించడం అసాధ్యం. ముఖ్యంగా, Kolmogorov సంక్లిష్టత : ఇచ్చిన సంఖ్య కోసం, ఈ సంఖ్యను ప్రింట్ చేసే అతి చిన్న ప్రోగ్రామ్ యొక్క పొడవును కనుగొనడానికి అనుమతించే అల్గోరిథం లేదు; దీనర్థం బెర్రీ సమస్యకు పరిష్కారం లేదు - ఇచ్చిన సంఖ్య కోసం అతి తక్కువ శబ్ద హోదాని కనుగొనడం.
మూలం: www.habr.com