Low basis theorem
ಕಡಿಮೆ ಆಧಾರ ಪ್ರಮೇಯವು ಗಣನೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಹಲವಾರು ಆಧಾರ ಪ್ರಮೇಯಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ, ಬೈನರಿ ಮರದ ಅನಂತ ಉಪವೃಕ್ಷವನ್ನು ನೀಡಿದರೆ, ನಿರ್ದಿಷ್ಟ ಗಣನೆಯ ಗುಣಲಕ್ಷಣಗಳೊಂದಿಗೆ ಮರದ ಮೂಲಕ ಅನಂತ ಮಾರ್ಗವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಕಡಿಮೆ ಆಧಾರದ ಪ್ರಮೇಯವು, ನಿರ್ದಿಷ್ಟವಾಗಿ, ಕಡಿಮೆ ಇರುವ ಮಾರ್ಗವಿರಬೇಕು ಎಂದು ತೋರಿಸುತ್ತದೆ; ಅಂದರೆ, ಮಾರ್ಗದ ಟ್ಯೂರಿಂಗ್ ಜಿಗಿತವು ಟ್ಯೂರಿಂಗ್ ಅನ್ನು ನಿಲ್ಲಿಸುವ ಸಮಸ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಹೇಳಿಕೆ ಮತ್ತು ಪುರಾವೆ ಕಡಿಮೆ ಆಧಾರ ಪ್ರಮೇಯವು (ಅಂಕಗಣಿತದ ಶ್ರೇಣಿವ್ಯವಸ್ಥೆಯನ್ನು ನೋಡಿ) ಪ್ರತಿಯೊಂದು ಖಾಲಿ ಇಲ್ಲದ ವರ್ಗವು ಕಡಿಮೆ ಮಟ್ಟದ (ಸೋರೆ 1987:109) ಗುಂಪನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ, ದ್ವಿಮಾನ ವೃಕ್ಷದ ಪ್ರತಿಯೊಂದು ಅನಂತ ಗಣನೀಯ ಉಪವೃಕ್ಷವು ಕಡಿಮೆ ಮಟ್ಟದ ಅನಂತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿದೆ ಎಂಬ ಹೇಳಿಕೆಗೆ ಇದು ಸಮನಾಗಿರುತ್ತದೆ. ಪುರಾವೆಯು ತರಗತಿಗಳೊಂದಿಗೆ ಒತ್ತಾಯಿಸುವ ವಿಧಾನವನ್ನು ಬಳಸುತ್ತದೆ (ಕೂಪರ್ 2004:330). ಹ್ಯಾಜೆಕ್ ಮತ್ತು ಕುಸೆರಾ (1989) ಎಂದು ಕರೆಯಲ್ಪಡುವ ಅಂಕಗಣಿತದ ಔಪಚಾರಿಕ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ಕಡಿಮೆ ಆಧಾರವನ್ನು ಸಾಬೀತುಪಡಿಸಬಹುದು ಎಂದು ತೋರಿಸಿದರು. ಬಲವಂತದ ವಾದವನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಸ್ಪಷ್ಟವಾಗಿ ರೂಪಿಸಬಹುದು. X′ ω ಗುಂಪಿಗೆ, f (X) = σ {i} (X) ′2 − i ಆಗಿರಲಿ, ಅಲ್ಲಿ {i} (X) ′ ಎಂದರೆ ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು i, X ಮೇಲೆ ನಿಲ್ಲುತ್ತದೆ (ಅಂತಹ ಎಲ್ಲಾ i ಗಳ ಮೊತ್ತದೊಂದಿಗೆ). ನಂತರ, ಪ್ರತಿ ಖಾಲಿ ಇಲ್ಲದ (ಲೈಟ್ಫೇಸ್) S2ω ಗೆ, f (X) ಅನ್ನು ಕಡಿಮೆ ಮಾಡುವ (ಅನನ್ಯ) X ωS ಕಡಿಮೆ ಟ್ಯೂರಿಂಗ್ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಇದನ್ನು ನೋಡಲು, i ಮೇಲೆ ಇಂಡಕ್ಷನ್ ಮೂಲಕ 0′ ನಿಂದ ಲೆಕ್ಕ ಹಾಕಬಹುದಾದ, {i} (X) ′ ′ ′ ′ ′ Y ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಯಂತ್ರವು X ಮೇಲೆ ನಿಲ್ಲುತ್ತದೆಯೇ ಎಂಬುದು X′ = 0′ ಗೆ ಅನುಮತಿಸುವ ಸೀಮಿತ ಸ್ಥಿತಿಯಿಂದ ಒತ್ತಾಯಿಸಲ್ಪಡುತ್ತದೆ. ಕಡಿಮೆ ಆಧಾರದ ಪ್ರಮೇಯದ ಒಂದು ಅನ್ವಯವೆಂದರೆ ಪರಿಣಾಮಕಾರಿ ಸಿದ್ಧಾಂತಗಳ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಗಳನ್ನು ನಿರ್ಮಿಸುವುದು, ಇದರಿಂದಾಗಿ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಗಳು ಕಡಿಮೆ ಟ್ಯೂರಿಂಗ್ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ಕಡಿಮೆ ಆಧಾರ ಪ್ರಮೇಯವು ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಕೆಳಗಿರುವ ಪಿಎ ಡಿಗ್ರಿಗಳ ಅಸ್ತಿತ್ವವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು. ಹೆಚ್ಚುವರಿ ಸ್ಪಷ್ಟೀಕರಣ ಗದ್ಯವನ್ನು ಒಳಗೊಂಡಂತೆ ಮೂಲ ಪ್ರಕಟಣೆ. ಪ್ರಮೇಯ 1.8.37. ಗಣನೆಯ ಸಿದ್ಧಾಂತ