PR (complexity)
PR என்பது அனைத்து பழமையான மறுநிகழ்வு செயல்பாடுகளின் சிக்கலான வகுப்பாகும்-அல்லது, சமமாக, அத்தகைய செயல்பாட்டால் வரையறுக்கப்பட்ட நேரத்தில் தீர்மானிக்கக்கூடிய அனைத்து முறையான மொழிகளின் தொகுப்பாகும். இதில் கூட்டல், பெருக்கம், எக்ஸ்போனென்டியேஷன், டெட்ரேஷன் போன்றவை அடங்கும். ஆக்கர்மேன் செயல்பாடு பழமையான மறுநிகழ்வு இல்லாத ஒரு செயல்பாட்டிற்கு ஒரு எடுத்துக்காட்டு, இது R இல் PR கண்டிப்பாக உள்ளது என்பதைக் காட்டுகிறது (கூப்பர் 2004:88). மறுபுறம், எந்தவொரு தொடர்ச்சியான கணக்கிடக்கூடிய தொகுப்பையும் (அதன் சிக்கலான வகுப்பு RE ஐப் பார்க்கவும்) ஒரு பழமையான-தொடர்ச்சியான செயல்பாட்டின் மூலம் பின்வரும் அர்த்தத்தில் "கணக்கிடலாம்": ஒரு உள்ளீடு (M, k) கொடுக்கப்பட்டால், M என்பது ஒரு டூரிங் இயந்திரம் மற்றும் k ஒரு முழு எண், M என்பது k படிகளுக்குள் நிறுத்தினால் M ஐ வெளியிடுங்கள்; இல்லையெனில் எதுவும் வெளியீடு செய்யாது. பின்னர் வெளியீடுகளின் ஒன்றிணைப்பு, சாத்தியமான அனைத்து உள்ளீடுகளுக்கும் (M, k), சரியாக நிறுத்தப்படும் M இன் தொகுப்பாகும். PR கண்டிப்பாக ELEMENTARY ஐக் கொண்டுள்ளது. PR இல் "PR-முழுமையான" சிக்கல்கள் இல்லை (எ. கா., ELEMENTARY ஐச் சேர்ந்த குறைப்புகள்). நடைமுறையில், PR இல் இல்லாத ஆனால் அதற்கு அப்பால் உள்ள பல சிக்கல்கள்-முழுமையானவை (ஷ்மிட்ஸ் 2016). குறிப்புகள் வெளி இணைப்புகள். சிக்கலான வகுப்புகள்