දත්ත සම්පීඩනය පිළිබඳ ගැටළුව, එහි සරලම ආකාරයෙන්, සංඛ්යා සහ ඒවායේ අංකනයට සම්බන්ධ විය හැක. සංඛ්යා ඉලක්කම් වලින් දැක්විය හැක ("එකොළොස්" අංක 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