Turing jump
ಗಣನೀಯತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಅಥವಾ ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಆಪರೇಟರ್, ಅಲನ್ ಟ್ಯೂರಿಂಗ್ ಹೆಸರಿನಿಂದ ಕರೆಯಲ್ಪಡುತ್ತದೆ, ಇದು ಪ್ರತಿ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಗೆ ಒರಾಕಲ್ನೊಂದಿಗೆ ಒರಾಕಲ್ ಯಂತ್ರದಿಂದ ನಿರ್ಧರಿಸಲಾಗದ ಗುಣಲಕ್ಷಣದೊಂದಿಗೆ ಅನುಕ್ರಮವಾಗಿ ಕಠಿಣ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ನಿಯೋಜಿಸುವ ಒಂದು ಕಾರ್ಯಾಚರಣೆಯಾಗಿದೆ. ಆಪರೇಟರ್ ಅನ್ನು ಜಂಪ್ ಆಪರೇಟರ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಇದು ಸಮಸ್ಯೆಯ ಟ್ಯೂರಿಂಗ್ ಮಟ್ಟವನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ. ಅಂದರೆ, ಈ ಸಮಸ್ಯೆಯು ಟ್ಯೂರಿಂಗ್ಗೆ ಕಡಿಮೆಯಾಗುವುದಿಲ್ಲ. ಪೋಸ್ಟ್ನ ಪ್ರಮೇಯವು ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಆಪರೇಟರ್ ಮತ್ತು ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಸೆಟ್ಗಳ ಅಂಕಗಣಿತದ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯ ನಡುವಿನ ಸಂಬಂಧವನ್ನು ಸ್ಥಾಪಿಸುತ್ತದೆ. ಅನೌಪಚಾರಿಕವಾಗಿ, ಒಂದು ಸಮಸ್ಯೆಯನ್ನು ನೀಡಿದರೆ, ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಆ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಒರಾಕಲ್ಗೆ ಪ್ರವೇಶವನ್ನು ನೀಡಿದಾಗ ನಿಲ್ಲುವ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರಗಳ ಗುಂಪನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನ X ನ ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಅನ್ನು X ಗಾಗಿ ಒರಾಕಲ್ನೊಂದಿಗೆ ಒರಾಕಲ್ ಯಂತ್ರಗಳಿಗೆ ನಿಲುಗಡೆ ಸಮಸ್ಯೆಯ ಒರಾಕಲ್ ಎಂದು ಭಾವಿಸಬಹುದು. ಔಪಚಾರಿಕವಾಗಿ, ಗಣಿಸಬಹುದಾದ ಕಾರ್ಯಗಳ ಒಂದು ಸೆಟ್ ಮತ್ತು ಗೊಡೆಲ್ ಸಂಖ್ಯೆಯನ್ನು ನೀಡಿದರೆ, ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಅನ್ನು ದಿ ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಖಾಲಿ ಗುಂಪಿನ ಟ್ಯೂರಿಂಗ್ ಜಿಗಿತಕ್ಕೆ ಸಂಕೇತ ಅಥವಾ ಇದನ್ನು ಹೆಚ್ಚಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಇದನ್ನು ಶೂನ್ಯ-ಜಿಗಿತ ಅಥವಾ ಕೆಲವೊಮ್ಮೆ ಶೂನ್ಯ-ಪ್ರಧಾನ ಎಂದು ಓದಲಾಗುತ್ತದೆ. ಅಂತೆಯೇ, ಇದು ಖಾಲಿ ಗುಂಪಿನ ಏಳನೇ ಜಿಗಿತವಾಗಿದೆ. ಸೀಮಿತವಾಗಿ, ಈ ಸೆಟ್ಗಳು ಅಂಕಗಣಿತದ ಕ್ರಮಾನುಗತಕ್ಕೆ ನಿಕಟವಾಗಿ ಸಂಬಂಧಿಸಿವೆ ಮತ್ತು ನಿರ್ದಿಷ್ಟವಾಗಿ ಪೋಸ್ಟ್ನ ಪ್ರಮೇಯಕ್ಕೆ ಸಂಬಂಧಿಸಿವೆ. ಜಿಗಿತವನ್ನು ಟ್ರಾನ್ಸ್ಫೈನೈಟ್ ಆರ್ಡಿನಲ್ಸ್ಗಳಾಗಿ ಪುನರಾವರ್ತಿಸಬಹುದುಃ ಕ್ಲೈನ್ಸ್ನಲ್ಲಿ ಕೋಡ್ ಹೊಂದಿರುವ ಆರ್ಡಿನಲ್ ಆಗಿರುವಾಗ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಸೆಟ್ಗಳಿಗೆ ಜಂಪ್ ಆಪರೇಟರ್ಗಳಿವೆ (ಕೋಡ್ ಅನ್ನು ಲೆಕ್ಕಿಸದೆ, ಪರಿಣಾಮವಾಗಿ ಜಿಗಿತಗಳು ಸ್ಪೆಕ್ಟರ್ ಪ್ರಮೇಯದಿಂದ ಒಂದೇ ಆಗಿರುತ್ತವೆ), ನಿರ್ದಿಷ್ಟವಾಗಿ ಸೆಟ್ಗಳು, ಚರ್ಚ್-ಕ್ಲೈನ್ ಆರ್ಡಿನಲ್ ಎಲ್ಲಿದೆ, ಹೈಪರರಿಥಮೆಟಿಕ್ ಕ್ರಮಾನುಗತಕ್ಕೆ ನಿಕಟ ಸಂಬಂಧ ಹೊಂದಿದೆ. ಇದಲ್ಲದೆ, ಗೊಡೆಲ್ನ ಎಲ್. ನ ಸೂಕ್ಷ್ಮ ರಚನೆಯ ಸಿದ್ಧಾಂತದ ಬಗ್ಗೆ ಜೆನ್ಸನ್ ಅವರ ಕೆಲಸವನ್ನು ಬಳಸಿಕೊಂಡು, ರಚನಾತ್ಮಕ ಬ್ರಹ್ಮಾಂಡದ ಎಣಿಸಬಹುದಾದ ಕ್ರಮಗಳ ಮೂಲಕ ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಮುಂದುವರಿಸಬಹುದು. ಈ ಪರಿಕಲ್ಪನೆಯನ್ನು ಲೆಕ್ಕವಿಲ್ಲದಷ್ಟು ನಿಯಮಿತ ಕಾರ್ಡಿನಲ್ಗಳಿಗೆ ವಿಸ್ತರಿಸಲು ಸಾಮಾನ್ಯೀಕರಿಸಲಾಗಿದೆ. ಉದಾಹರಣೆಗಳು ಖಾಲಿ ಗುಂಪಿನ ಟ್ಯೂರಿಂಗ್ ಜಿಗಿತವು ನಿಲ್ಲಿಸುವ ಸಮಸ್ಯೆಗೆ ಸಮಾನವಾಗಿದೆ. ಪ್ರತಿಯೊಂದಕ್ಕೂ, ಅಂಕಗಣಿತದ ಕ್ರಮಾನುಗತ ಮಟ್ಟದಲ್ಲಿ ಸೆಟ್ m-ಪೂರ್ಣವಾಗಿದೆ (ಪೋಸ್ಟ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ). ಪೀನೋ ಅಂಕಗಣಿತದ ಭಾಷೆಯಲ್ಲಿ ನಿಜವಾದ ಸೂತ್ರಗಳ ಗೊಡೆಲ್ ಸಂಖ್ಯೆಗಳ ಗುಂಪನ್ನು ಪೂರ್ವಸೂಚಿಯೊಂದಿಗೆ ಇಲ್ಲಿಂದ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಗುಣಲಕ್ಷಣಗಳನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದು ಆದರೆ ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳಲಾಗುವುದಿಲ್ಲ. ಟ್ಯೂರಿಂಗ್-ಸಮಾನವಾಗಿದ್ದರೆ, ಟ್ಯೂರಿಂಗ್-ಸಮಾನವಾಗಿರುತ್ತದೆ. ಈ ಅರ್ಥದ ವ್ಯತಿರಿಕ್ತತೆಯು ನಿಜವಲ್ಲ. (ಶೋರ್ ಮತ್ತು ಸ್ಲಾಮನ್, 1999) ಟು ಗೆ ಮ್ಯಾಪಿಂಗ್ ಕಾರ್ಯವನ್ನು ಟ್ಯೂರಿಂಗ್ ಡಿಗ್ರಿಗಳ ಭಾಗಶಃ ಕ್ರಮದಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಟ್ಯೂರಿಂಗ್ ಜಂಪ್ ಆಪರೇಟರ್ನ ಅನೇಕ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಟ್ಯೂರಿಂಗ್ ಡಿಗ್ರಿಗಳ ಲೇಖನದಲ್ಲಿ ಚರ್ಚಿಸಲಾಗಿದೆ. ಅಂಬೋಸ್-ಸ್ಪೈಸ್, ಕೆ. ಮತ್ತು ಫೆಜರ್, ಪಿ. ಡಿಗ್ರಿ ಆಫ್ ಅನ್ಸಾಲ್ವಬಿಲಿಟಿ. ಅಪ್ರಕಟಿತ. http://www.cs.umb.edu ~ ಫೆಜರ್/ಲೇಖನಗಳು/ಹಿಸ್ಟರಿ _ ಆಫ್ _ ಡಿಗ್ರೀಸ್. ಪಿಡಿಎಫ್ ಪರಿಚಯದ ವರ್ಷ ಗಣಕಯಂತ್ರ ಸಿದ್ಧಾಂತವನ್ನು ಕಾಣೆಯಾಗಿದೆ ಅಲನ್ ಟ್ಯೂರಿಂಗ್