ಡೇಟಾ ಸಂಕೋಚನದ ಸಮಸ್ಯೆ, ಅದರ ಸರಳ ರೂಪದಲ್ಲಿ, ಸಂಖ್ಯೆಗಳು ಮತ್ತು ಅವುಗಳ ಸಂಕೇತಗಳಿಗೆ ಸಂಬಂಧಿಸಿರಬಹುದು. ಸಂಖ್ಯೆಗಳನ್ನು ಅಂಕಿಗಳಿಂದ ಸೂಚಿಸಬಹುದು ("ಹನ್ನೊಂದು" ಸಂಖ್ಯೆ 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 (ಮತ್ತು ಅದರ ಕ್ರಿಯಾತ್ಮಕ ಸಾದೃಶ್ಯಗಳು) - ಮತ್ತು ಅಂತಹ ಪ್ರೋಗ್ರಾಂ ಅನ್ನು ಪರೀಕ್ಷಿಸುವುದಕ್ಕಿಂತ ವಿಷಯವು ಮುಂದೆ ಹೋಗುವುದಿಲ್ಲ!
ಬೆರ್ರಿ ವಿರೋಧಾಭಾಸದಂತೆ, ಕ್ಯಾಚ್ ಸಂಕೇತದ ಅನೌಪಚಾರಿಕತೆಯಲ್ಲಿತ್ತು, ಎರಡನೆಯ ಪ್ರಕರಣದಲ್ಲಿ ನಾವು ಉತ್ತಮ ವೇಷದ ಸುಧಾರಣೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ. . ಸತ್ಯವೆಂದರೆ ಪ್ರೋಗ್ರಾಂನಿಂದ ಅದರ ಔಟ್ಪುಟ್ ಅನ್ನು ಸೀಮಿತ ಸಮಯದಲ್ಲಿ ನಿರ್ಧರಿಸಲು ಅಸಾಧ್ಯವಾಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಕೊಲ್ಮೊಗೊರೊವ್ ಸಂಕೀರ್ಣತೆ : ನಿರ್ದಿಷ್ಟ ಸಂಖ್ಯೆಗೆ, ಈ ಸಂಖ್ಯೆಯನ್ನು ಮುದ್ರಿಸುವ ಚಿಕ್ಕದಾದ ಪ್ರೋಗ್ರಾಂನ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅನುಮತಿಸುವ ಯಾವುದೇ ಅಲ್ಗಾರಿದಮ್ ಇಲ್ಲ; ಇದರರ್ಥ ಬೆರ್ರಿಯ ಸಮಸ್ಯೆಗೆ ಯಾವುದೇ ಪರಿಹಾರವಿಲ್ಲ - ನಿರ್ದಿಷ್ಟ ಸಂಖ್ಯೆಗೆ ಕಡಿಮೆ ಮೌಖಿಕ ಪದನಾಮದ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು.
ಮೂಲ: www.habr.com