Computation in the limit
ಗಣನೀಯತೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಒಂದು ಕಾರ್ಯವು ಏಕರೂಪವಾಗಿ ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯಗಳ ಅನುಕ್ರಮದ ಮಿತಿಯಾಗಿದ್ದರೆ ಅದನ್ನು ಮಿತಿ ಗಣನೀಯ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮಿತಿಯಲ್ಲಿ ಗಣಿಸಬಹುದಾದ ಪದಗಳು, ಮಿತಿ ಪುನರಾವರ್ತಿತ ಮತ್ತು ಪುನರಾವರ್ತಿತವಾಗಿ ಅಂದಾಜು ಮಾಡಬಹುದಾದ ಪದಗಳನ್ನು ಸಹ ಬಳಸಲಾಗುತ್ತದೆ. ಮಿತಿ ಗಣನೆಗೆ ಯೋಗ್ಯವಾದ ಕಾರ್ಯಗಳನ್ನು ತಮ್ಮ ನಿಜವಾದ ಮೌಲ್ಯದಲ್ಲಿ ಅಂತಿಮವಾಗಿ ಸರಿಯಾದ ಗಣನೆಗೆ ಯೋಗ್ಯವಾದ ಊಹೆಯ ಕಾರ್ಯವಿಧಾನವನ್ನು ಒಪ್ಪಿಕೊಳ್ಳುವಂತೆ ಪರಿಗಣಿಸಬಹುದು. ಒಂದು ಸೆಟ್ ಅದರ ವಿಶಿಷ್ಟ ಕಾರ್ಯವು ಮಿತಿ ಗಣನೀಯವಾಗಿದ್ದಾಗ ಸೀಮಿತ ಗಣನೀಯವಾಗಿರುತ್ತದೆ. ಅನುಕ್ರಮವು ಡಿ ಗೆ ಹೋಲಿಸಿದರೆ ಏಕರೂಪವಾಗಿ ಗಣಿಸಬಹುದಾದಂತಿದ್ದರೆ, ಡಿ ಯಲ್ಲಿ ಕಾರ್ಯವು ಮಿತಿಯನ್ನು ಗಣಿಸಬಹುದಾದಂತಾಗುತ್ತದೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಒಟ್ಟು ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯವಿದ್ದರೆ ಒಟ್ಟು ಕಾರ್ಯವು ಮಿತಿಯನ್ನು ಗಣಿಸಬಹುದಾದಂತಾಗುತ್ತದೆ. ಡಿ ಯಲ್ಲಿ ಗಣಿಸಬಹುದಾದ ಒಟ್ಟು ಕಾರ್ಯವಿದ್ದರೆ ಒಟ್ಟು ಕಾರ್ಯವು ಮಿತಿಯನ್ನು ಗಣಿಸಬಹುದಾದಂತಾಗುತ್ತದೆ. ಡಿ ಯಲ್ಲಿ ಸಹ ಗಣಿಸಬಹುದಾದ ಒಟ್ಟು ಕಾರ್ಯವು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಒಂದು ಗುಂಪನ್ನು ಮಿತಿಯಲ್ಲಿ ಅದರ ವಿಶಿಷ್ಟ ಕಾರ್ಯವು ಮಿತಿಯಲ್ಲಿ ಗಣಿಸಬಹುದಾದಂತಿದ್ದರೆ ಮಾತ್ರ ಮಿತಿಯಲ್ಲಿ ಗಣಿಸಬಹುದಾದಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗುತ್ತದೆ. ಇದಕ್ಕೆ ತದ್ವಿರುದ್ಧವಾಗಿ, ಒಂದು ಕಾರ್ಯದಿಂದ ಮಿತಿಯಲ್ಲಿ ಗಣಿಸಬಹುದಾದರೆ ಮತ್ತು ಇನ್ಪುಟ್ i ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮತ್ತು ಸ್ಥಿರಗೊಳಿಸಿದಷ್ಟು ದೊಡ್ಡ t ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸುವ ಎರಡನೇ ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯವಿದ್ದರೆ ಮಾತ್ರ ಸೆಟ್ ಅನ್ನು ಗಣಿಸಬಹುದಾಗಿದೆ. (ಖಾಲಿ ಗುಂಪಿನ ಟ್ಯೂರಿಂಗ್ ಜಂಪ್) ಸೆಟ್ ಅನ್ನು ಗಣಿಸಬಹುದಾದರೆ ಮಾತ್ರ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಗುಂಪನ್ನು ಮಿತಿ ಗಣನೆಗೆ ಒಳಪಡಿಸಬಹುದು ಎಂದು ಮಿತಿ ಲೆಮ್ಮಾ ಹೇಳುತ್ತದೆ. ಸಂಬಂಧಿತ ಮಿತಿ ಲೆಮ್ಮಾವು ಒಂದು ಸೆಟ್ ಅನ್ನು ಗಣಿಸಬಹುದಾದರೆ ಮತ್ತು ಅದರಿಂದ ಮಾತ್ರ ಗಣಿಸಬಹುದೆಂದು ಹೇಳುತ್ತದೆ. ಇದಲ್ಲದೆ, ಮಿತಿ ಲೆಮ್ಮಾವು (ಮತ್ತು ಅದರ ಸಾಪೇಕ್ಷತೆ) ಏಕರೂಪವಾಗಿ ಇರುತ್ತದೆ. ಹೀಗಾಗಿ ಕಾರ್ಯಕ್ಕಾಗಿ ಸೂಚ್ಯಂಕದಿಂದ ಇದಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಸೂಚ್ಯಂಕಕ್ಕೆ ಹೋಗಬಹುದು. ಮಿತಿಯನ್ನು ಹೊಂದಿರುವ ಕೆಲವರಿಗೆ ಸೂಚ್ಯಂಕಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಸೂಚ್ಯಂಕದಿಂದ ಸಹ ಹೋಗಬಹುದು. ಪ್ರೂಫ್ ಒಂದು [ಗಣನೀಯವಾಗಿ ಎಣಿಸಬಹುದಾದ] ಸೆಟ್ ಆಗಿರುವುದರಿಂದ, ಇದು ಮಿತಿಯಲ್ಲಿಯೇ ಗಣನೀಯವಾಗಿರಬೇಕು, ಏಕೆಂದರೆ ಗಣನೀಯ ಕಾರ್ಯವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಅದರ ಮಿತಿಯು ಅನಂತಕ್ಕೆ ಹೋಗುವಾಗ ಅದರ ವಿಶಿಷ್ಟ ಕಾರ್ಯವಾಗಿದೆ. ಆದ್ದರಿಂದ ಟ್ಯೂರಿಂಗ್ ಕಡಿತದಿಂದ ಮಿತಿ ಗಣನೆಯನ್ನು ಸಂರಕ್ಷಿಸಿದರೆ ಸಾಕು, ಏಕೆಂದರೆ ಇದು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದಾದ ಎಲ್ಲಾ ಸೆಟ್ಗಳು ಮಿತಿ ಗಣನಾರ್ಹವೆಂದು ತೋರಿಸುತ್ತದೆ. ಅವುಗಳ ವಿಶಿಷ್ಟ ಕಾರ್ಯಗಳು ಮತ್ತು ಮಿತಿಯೊಂದಿಗೆ ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯದೊಂದಿಗೆ ಗುರುತಿಸಲಾದ ಸೆಟ್ಗಳನ್ನು ಸರಿಪಡಿಸಿ. ಕೆಲವು ಟ್ಯೂರಿಂಗ್ ಕಡಿತಕ್ಕಾಗಿ ಮತ್ತು ಗಣನೆಯ ಕಾರ್ಯವನ್ನು ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಿ ಎಂದು ಭಾವಿಸೋಣ ಈಗ ಗಣನೆಯು ಹಂತಗಳಲ್ಲಿ ಒಮ್ಮುಖಗೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಅದರ ಮೊದಲ ಬಿಟ್ಗಳನ್ನು ಮಾತ್ರ ನೋಡುತ್ತದೆ ಎಂದು ಭಾವಿಸೋಣ. ಈಗ ಎಲ್ಲರಿಗೂ ಅಂತಹದನ್ನು ಆಯ್ಕೆ ಮಾಡಿ. ಹಾಗಿದ್ದಲ್ಲಿ, ಗಣನೆಯು ಹೆಚ್ಚಿನ ಹಂತಗಳಲ್ಲಿ ಒಮ್ಮುಖವಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ಒಂದು ಮಿತಿಯನ್ನು ಹೊಂದಿದೆ, ಆದ್ದರಿಂದ ಮಿತಿಯನ್ನು ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಸೆಟ್ಗಳು ಕೇವಲ ಪೋಸ್ಟ್ನ ಪ್ರಮೇಯದಿಂದ ಗಣಿಸಬಹುದಾದ ಸೆಟ್ಗಳಾಗಿರುವುದರಿಂದ, ಮಿತಿ ಲೆಮ್ಮಾವು ಮಿತಿ ಗಣಿಸಬಹುದಾದ ಸೆಟ್ಗಳು ಸೆಟ್ಗಳಾಗಿವೆ ಎಂದು ಸಹ ಸೂಚಿಸುತ್ತದೆ. ಗಣಿಸಬಹುದಾದ ನೈಜ ಸಂಖ್ಯೆಗಳನ್ನು ಮಿತಿಗೊಳಿಸಿ x ಗೆ ಒಮ್ಮುಖವಾಗುವ ತರ್ಕಬದ್ಧ ಸಂಖ್ಯೆಗಳ (ಅಥವಾ, ಸಮಾನವಾದ, ಗಣಿಸಬಹುದಾದ ನೈಜ ಸಂಖ್ಯೆಗಳ) ಗಣಿಸಬಹುದಾದ ಅನುಕ್ರಮವಿದ್ದರೆ ವಾಸ್ತವಿಕ ಸಂಖ್ಯೆ x ಅನ್ನು ಮಿತಿಯಲ್ಲಿ ಗಣಿಸಬಹುದಾಗಿದೆ. ಇದಕ್ಕೆ ತದ್ವಿರುದ್ಧವಾಗಿ, ಒಂದು ನೈಜ ಸಂಖ್ಯೆಯು ಅದರೊಂದಿಗೆ ಒಮ್ಮುಖವಾಗುವ ತರ್ಕಬದ್ಧ ಸಂಖ್ಯೆಗಳ ಅನುಕ್ರಮವಿದ್ದರೆ ಮತ್ತು ಅದು ಒಮ್ಮುಖದ ಗಣನೀಯ ಮಾಡ್ಯುಲಸ್ ಅನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಅದನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಒಂದು ನೈಜ ಸಂಖ್ಯೆಯನ್ನು ಬಿಟ್ಗಳ ಅನುಕ್ರಮವಾಗಿ ನೋಡಿದಾಗ, ಈ ಕೆಳಗಿನ ಸಮಾನ ವ್ಯಾಖ್ಯಾನವು ಹೊಂದಿರುತ್ತದೆ. ಗುಂಪಿನಲ್ಲಿ ಮೌಲ್ಯಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಒಟ್ಟು ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯವಿದ್ದರೆ ಮತ್ತು ಪ್ರತಿ i ಗೆ ಮಿತಿಯು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಮತ್ತು ಸಮಾನವಾಗಿದ್ದರೆ ಮಾತ್ರ ಬೈನರಿ ಅಂಕೆಗಳ ಅನಂತ ಅನುಕ್ರಮವನ್ನು ಮಿತಿಯಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಹೀಗಾಗಿ ಪ್ರತಿ i ಗೆ, t ಹೆಚ್ಚಾದಂತೆ ಅದರ ಮೌಲ್ಯವು ಅಂತಿಮವಾಗಿ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ ಮತ್ತು ಸಮನಾಗಿರುತ್ತದೆ. ಗಣಿಸಬಹುದಾದ ನೈಜ ಸಂಖ್ಯೆಗಳಂತೆ, ಮಿತಿ ಗಣಿಸಬಹುದಾದ ನೈಜಗಳ ಎರಡು ಪ್ರಾತಿನಿಧ್ಯಗಳ ನಡುವೆ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಚಲಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ಉದಾಹರಣೆಗಳು ಬೈನರಿ ವಿಸ್ತರಣೆಯು ನಿಲುಗಡೆ ಸಮಸ್ಯೆಯನ್ನು ಎನ್ಕೋಡ್ ಮಾಡುವ ರಿಯಲ್ ಅನ್ನು ಮಿತಿಯಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು ಆದರೆ ಲೆಕ್ಕ ಹಾಕಲಾಗುವುದಿಲ್ಲ. ಬೈನರಿ ವಿಸ್ತರಣೆಯು ಮೊದಲ-ಕ್ರಮಾಂಕದ ಅಂಕಗಣಿತದ ಸತ್ಯ ಗುಂಪನ್ನು ಎನ್ಕೋಡ್ ಮಾಡುವ ನೈಜವು ಮಿತಿಯಲ್ಲಿ ಗಣನೆಗೆ ಯೋಗ್ಯವಾಗಿಲ್ಲ. ಚೈತೀನ್ ನಿರಂತರ. ಸೆಟ್-ಥಿಯರಿಟಿಕ್ ಎಕ್ಸ್ಟೆನ್ಶನ್-ಅಂಕಗಣಿತದ ಕ್ರಮಾನುಗತ ಕಾರ್ಯಗಳ ಮೂಲಕ α-ಪುನರಾವರ್ತನೆಯ ಸಿದ್ಧಾಂತಕ್ಕೆ ಮಿತಿ ಲೆಮ್ಮಾದ ಮಾರ್ಪಡಿಸಿದ ಆವೃತ್ತಿಯಿದೆ, ಇದು ಕೆಲವು ಸ್ವೀಕಾರಾರ್ಹ ಆರ್ಡಿನಲ್ಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಕ್ರಮಾನುಗತವಾಗಿದೆ. ನೀಡಲಾದ ಸ್ವೀಕಾರಾರ್ಹ ಆರ್ಡಿನಲ್ಗೆ,-ಅಂಕಗಣಿತದ ಕ್ರಮಾನುಗತವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿಃ ಒಂದು ಸಂಬಂಧವು-ಪುನರಾವರ್ತಿತವಾಗಿದ್ದರೆ. ಅದು ಸಂಬಂಧದ ಪ್ರಕ್ಷೇಪಣವಾಗಿದ್ದರೆ. ಅದರ ಪೂರಕವಾಗಿದ್ದರೆ. ನಿಂದ ಭಾಗಶಃ ಕಾರ್ಯವಾಗಿರಲಿ. ಈ ಕೆಳಗಿನವುಗಳು ಸಮಾನವಾಗಿವೆಃ (ನ ನಕ್ಷೆ). ಇದು-ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯಗಳ ಸೂಚ್ಯಂಕಗಳನ್ನು ಬಳಸುವ-ಜಿಗಿತದಲ್ಲಿ ದುರ್ಬಲವಾಗಿ-ಪುನರಾವರ್ತಿತವಾಗಿದೆ. ಅಂತಹ ಅಂದಾಜು ಮಾಡುವ-ಪುನರಾವರ್ತಿತ ಕಾರ್ಯವಿದೆ. ಎರಡೂ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿಲ್ಲ, ಅಥವಾ ಅವೆರಡೂ ವ್ಯಾಖ್ಯಾನಿಸಲ್ಪಟ್ಟಿವೆ ಮತ್ತು ಸಮಾನವಾಗಿವೆ ಎಂಬುದನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಸ್ಪೆಕರ್ ಅನುಕ್ರಮ ಉಲ್ಲೇಖಗಳು ಜೆ. ಷ್ಮಿಧುಬರ್, "ಸಾಮಾನ್ಯೀಕೃತ ಕೊಲ್ಮೊಗೊರೊವ್ ಸಂಕೀರ್ಣತೆಗಳ ಶ್ರೇಣಿ ವ್ಯವಸ್ಥೆಗಳು ಮತ್ತು ಮಿತಿಯಲ್ಲಿ ಗಣಿಸಬಹುದಾದ ಅಸಂಖ್ಯಾತ ಸಾರ್ವತ್ರಿಕ ಕ್ರಮಗಳು", ಇಂಟರ್ನ್ಯಾಷನಲ್ ಜರ್ನಲ್ ಆಫ್ ಫೌಂಡೇಶನ್ಸ್ ಆಫ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್, 2002 ಅನ್ನು ಸಹ ನೋಡಿ. ಆರ್. ಸೋರೆ. ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದ ಸೆಟ್ಗಳು ಮತ್ತು ಡಿಗ್ರಿಗಳು. ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್ 1987. ವಿ. ಬ್ರಾಟ್ಕಾ. ಟ್ಯೂರಿಂಗ್ ಜಿಗಿತಗಳು ಮತ್ತು ಮಿತಿಗಳ ನಡುವಿನ ಗಾಲೋಯಿಸ್ ಸಂಪರ್ಕ. ಲಾಗ್ ಮಾಡಿ. ಮೆಥಡ್ಸ್ ಕಂಪ್ಯೂಟ್. ವಿಜ್ಞಾನ., 2018,. ಗಣನೀಯತೆ ಸಿದ್ಧಾಂತ ಗಣನೆಯ ಸಿದ್ಧಾಂತ