PR (complexity)
ಪಿಆರ್ ಎಲ್ಲಾ ಪ್ರಾಚೀನ ಪುನರಾವರ್ತಿತ ಕಾರ್ಯಗಳ ಸಂಕೀರ್ಣತೆಯ ವರ್ಗವಾಗಿದೆ-ಅಥವಾ, ಸಮಾನವಾಗಿ, ಅಂತಹ ಕಾರ್ಯದಿಂದ ಸೀಮಿತವಾದ ಸಮಯದಲ್ಲಿ ನಿರ್ಧರಿಸಬಹುದಾದ ಎಲ್ಲಾ ಔಪಚಾರಿಕ ಭಾಷೆಗಳ ಸಮೂಹವಾಗಿದೆ. ಇದು ಸೇರ್ಪಡೆ, ಗುಣಾಕಾರ, ಘಾತಾಂಕ, ಸಂಕೋಚನ ಇತ್ಯಾದಿಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಅಕರ್ಮನ್ ಕಾರ್ಯವು ಪ್ರಾಚೀನ ಪುನರಾವರ್ತಿತವಲ್ಲದ ಕಾರ್ಯಕ್ಕೆ ಒಂದು ಉದಾಹರಣೆಯಾಗಿದೆ, ಇದು ಆರ್ (ಕೂಪರ್ 2004:88) ನಲ್ಲಿ ಪಿಆರ್ ಅನ್ನು ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಒಳಗೊಂಡಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ನಾವು ಈ ಕೆಳಗಿನ ಅರ್ಥದಲ್ಲಿ ಪ್ರಾಚೀನ-ಪುನರಾವರ್ತಿತ ಕಾರ್ಯದಿಂದ ಯಾವುದೇ ಪುನರಾವರ್ತಿತವಾಗಿ ಎಣಿಸಬಹುದಾದ ಸೆಟ್ ಅನ್ನು (ಅದರ ಸಂಕೀರ್ಣತೆ ವರ್ಗ RE ಅನ್ನು ಸಹ ನೋಡಿ) "ಎಣಿಸಬಹುದು": ಇನ್ಪುಟ್ (M, k) ಅನ್ನು ನೀಡಿದರೆ, ಅಲ್ಲಿ M ಒಂದು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವಾಗಿದೆ ಮತ್ತು k ಒಂದು ಪೂರ್ಣಾಂಕವಾಗಿದೆ, M k ಹಂತಗಳಲ್ಲಿ ನಿಲ್ಲಿಸಿದರೆ M ಅನ್ನು ಔಟ್ಪುಟ್ ಮಾಡಿ; ಇಲ್ಲದಿದ್ದರೆ ಏನನ್ನೂ ಔಟ್ಪುಟ್ ಮಾಡುವುದಿಲ್ಲ. ನಂತರ ಎಲ್ಲಾ ಸಂಭವನೀಯ ಇನ್ಪುಟ್ಗಳ (ಎಂ, ಕೆ) ಮೇಲೆ ಔಟ್ಪುಟ್ಗಳ ಒಕ್ಕೂಟವು ನಿಖರವಾಗಿ ನಿಲ್ಲುವ ಎಂನ ಗುಂಪಾಗಿದೆ. ಪಿಆರ್ ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಅಂಶಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಪಿಆರ್ "ಪಿಆರ್-ಕಂಪ್ಲೀಟ್" ಸಮಸ್ಯೆಗಳನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ (ಉದಾಹರಣೆಗೆ, ಎಲಿಮೆಂಟರಿಗೆ ಸೇರಿದ ಕಡಿತಗಳು). ಆಚರಣೆಯಲ್ಲಿ, ಪಿ. ಆರ್. ನಲ್ಲಿಲ್ಲದ ಆದರೆ ಅದನ್ನೂ ಮೀರಿದ ಅನೇಕ ಸಮಸ್ಯೆಗಳು-ಪೂರ್ಣವಾಗಿವೆ (ಷ್ಮಿಟ್ಜ್ 2016). ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು. ಸಂಕೀರ್ಣತೆ ತರಗತಿಗಳು