RE (complexity)
கணக்கீட்டு கோட்பாடு மற்றும் கணக்கீட்டு சிக்கலான கோட்பாட்டில், RE (மீண்டும் மீண்டும் கணக்கிடக்கூடியது) என்பது முடிவு சிக்கல்களின் வகுப்பாகும், இதற்காக ஒரு 'ஆம்' பதிலை ஒரு வரையறுக்கப்பட்ட நேரத்தில் ஒரு டூரிங் இயந்திரத்தால் சரிபார்க்க முடியும். முறைசாரா முறையில், ஒரு சிக்கல் நிகழ்வுக்கான பதில் 'ஆம்' என்றால், இதைத் தீர்மானிக்க வரையறுக்கப்பட்ட நேரம் எடுக்கும் சில நடைமுறைகள் உள்ளன, மேலும் உண்மையான பதில் 'இல்லை' என்று இருக்கும்போது இந்த நடைமுறை ஒருபோதும் 'ஆம்' என்று பொய்யாகப் புகாரளிக்காது. இருப்பினும், உண்மையான பதில் 'இல்லை' என்றால், செயல்முறை நிறுத்தப்பட வேண்டிய அவசியமில்லை; சில 'இல்லை' நிகழ்வுகளுக்கு இது ஒரு "எல்லையற்ற சுழற்சிக்கு" செல்லக்கூடும். அத்தகைய செயல்முறை சில நேரங்களில் அரை-வழிமுறை என்று அழைக்கப்படுகிறது, இது ஒரு வழிமுறையிலிருந்து வேறுபடுகிறது, இது ஒரு முடிவு சிக்கலுக்கான முழுமையான தீர்வாக வரையறுக்கப்படுகிறது. இதேபோல், கோ-ஆர். இ என்பது ஆர். இ. யில் உள்ள ஒரு மொழியின் முழுமைகளாக இருக்கும் அனைத்து மொழிகளின் தொகுப்பாகும். ஒரு வகையில், கோ-ஆர்இ என்பது ஒரு வரையறுக்கப்பட்ட காலத்திற்குள் அங்கத்துவத்தை நிரூபிக்க முடியாத மொழிகளைக் கொண்டுள்ளது, ஆனால் அங்கத்துவத்தை நிரூபிக்க எப்போதும் ஆகலாம். சமமான வரையறை சமமாக, RE என்பது ஒரு டூரிங் இயந்திரம் அனைத்து 'ஆம்' நிகழ்வுகளையும் ஒவ்வொன்றாக பட்டியலிடக்கூடிய முடிவு சிக்கல்களின் வகுப்பாகும் (இதுதான் 'கணக்கிடக்கூடிய' பொருள்). RE இன் ஒவ்வொரு உறுப்பினரும் ஒரு தொடர்ச்சியான கணக்கிடக்கூடிய தொகுப்பாகும், எனவே ஒரு டயோஃபாண்டைன் தொகுப்பாகும். இது சமமானது என்பதைக் காட்ட, ஏற்றுக்கொள்ளப்பட்ட அனைத்து உள்ளீடுகளையும் கணக்கிடும் ஒரு இயந்திரம் இருந்தால், ஒரு சரத்தில் எடுக்கும் மற்றொரு இயந்திரம் சரம் கணக்கிடப்பட்டால் இயக்கலாம் மற்றும் ஏற்றுக்கொள்ளலாம் என்பதை நினைவில் கொள்க. மாறாக, ஒரு உள்ளீடு ஒரு மொழியில் இருக்கும்போது ஒரு இயந்திரம் ஏற்றுக்கொண்டால், மற்றொரு இயந்திரம் ஒவ்வொரு உள்ளீட்டின் உருவகப்படுத்துதல்களையும் இணைப்பதன் மூலமும் ஏற்றுக்கொள்ளப்பட்ட சரங்களை வெளியிடுவதன் மூலமும் மொழியில் உள்ள அனைத்து சரங்களையும் கணக்கிட முடியும் (செயல்படுத்தும் வரிசை உள்ளது, இது இறுதியில் ஒவ்வொரு செயல்படுத்தும் படியையும் பெறும், ஏனெனில் எண்ணற்ற பல வரிசைப்படுத்தப்பட்ட ஜோடி உள்ளீடுகள் மற்றும் படிகள் உள்ளன). பிற வகுப்புகளுடனான உறவுகள் மறுநிகழ்வு மொழிகளின் தொகுப்பு (ஆர்) என்பது ஆர்இ மற்றும் கோ-ஆர்இ ஆகிய இரண்டின் துணைக்குழுவாகும். உண்மையில், இது அந்த இரண்டு வகுப்புகளின் குறுக்குவெட்டு, ஏனென்றால் ஒரு அங்கீகரிப்பவர் மற்றும் ஒரு இணை அங்கீகரிப்பவர் இருக்கும் எந்தவொரு சிக்கலையும் ஒருவர் முடிவைப் பெறும் வரை அவற்றை வெறுமனே இணைப்பதன் மூலம் தீர்மானிக்க முடியும். எனவேஃ இதற்கு நேர்மாறாக, ஆர்இ அல்லது கோ-ஆர்இ அல்லாத மொழிகளின் தொகுப்பு என்ஆர்என்சி என்று அழைக்கப்படுகிறது. உறுப்பினர் அல்லது உறுப்பினர் அல்லாதவர்களை ஒரு வரையறுக்கப்பட்ட காலத்திற்குள் நிரூபிக்க முடியாத மொழிகளின் தொகுப்பாக இவை உள்ளன, மேலும் RE அல்லது Co-RE இல் இல்லாத மற்ற அனைத்து மொழிகளும் இதில் உள்ளன. அதாவதுஃ இந்த பிரச்சினைகள் தீர்க்கமுடியாதவை மட்டுமல்ல, அவை அல்லது அவற்றின் நிரப்பு ஆகியவை மீண்டும் மீண்டும் கணக்கிடப்படுவதில்லை. 2020 ஜனவரியில், ஒரு முன் அச்சு ஆர்இ வகுப்பு எம்ஐபி * க்கு சமமானது என்பதற்கான ஆதாரத்தை அறிவித்தது (ஒரு கிளாசிக்கல் சரிபார்ப்பவர் சிக்கலைப் பகிர்ந்து கொள்ளும் பல அனைத்து சக்திவாய்ந்த குவாண்டம் புரோவர்களுடன் தொடர்பு கொள்ளும் வகுப்பு); ஒரு திருத்தப்பட்ட, ஆனால் இன்னும் முழுமையாக மதிப்பாய்வு செய்யப்படவில்லை, ஆதாரம் நவம்பர் 2021 இல் ஏசிஎம் தகவல்தொடர்புகளில் வெளியிடப்பட்டது. கான்ஸ் உட்பொதிக்கும் சிக்கல் மற்றும் சிரெல்ஸனின் சிக்கல் பொய்யானது என்பதை ஆதாரம் குறிக்கிறது. ரீ-கம்ப்லீட் ரீ-கம்ப்லீட் என்பது ரீக்கான முழுமையான முடிவு சிக்கல்களின் தொகுப்பாகும். ஒரு வகையில், இவை "கடினமான" தொடர்ச்சியான கணக்கிடக்கூடிய பிரச்சினைகள். பொதுவாக, பயன்படுத்தப்படும் குறைப்புகளில் எந்த தடையும் வைக்கப்படுவதில்லை, அவை பல-ஒரு குறைப்புகளாக இருக்க வேண்டும் என்பதைத் தவிர. ரீ-கம்ப்லீட் சிக்கல்களின் எடுத்துக்காட்டுகள்ஃ சிக்கலை நிறுத்துதல்ஃ ஒரு வரையறுக்கப்பட்ட உள்ளீடு வழங்கப்பட்ட நிரல் இயங்குகிறதா அல்லது என்றென்றும் இயங்குகிறதா. ரைஸின் தேற்றத்தின் படி, தொடர்ச்சியான செயல்பாடுகளின் தொகுப்பின் எந்தவொரு அற்பமான துணைக்குழுவிலும் உறுப்பினர் பதவியை தீர்மானிப்பது RE-கடினமானது. தொகுப்பு மீண்டும் மீண்டும் கணக்கிடப்படும் போதெல்லாம் இது முழுமையடையும். அனைத்து படைப்பு தொகுப்புகளும் மீண்டும் முழுமையடைந்துள்ளன என்பதை நிரூபித்தது. குழுக்கள் அல்லது அரை குழுக்களுக்கான சீரான சொல் சிக்கல். (உண்மையில், சில தனிப்பட்ட குழுக்களுக்கான சொல் சிக்கல் RE-முழுமையானது.) ஒரு பொதுவான கட்டுப்பாடற்ற முறையான இலக்கணத்தில் உறுப்பினர் என்பதை தீர்மானித்தல். (மீண்டும், சில தனிப்பட்ட இலக்கணங்களில் RE-முழுமையான உறுப்பினர் சிக்கல்கள் உள்ளன.) முதல் வரிசை தர்க்கத்திற்கான செல்லுபடியாகும் சிக்கல். பிந்தைய கடிதப் பிரச்சினைஃ ஜோடி சரங்களின் பட்டியலைக் கொடுத்தால், இந்த ஜோடிகளிலிருந்து (மீண்டும் மீண்டும் அனுமதிக்கும்) ஒரு தேர்வு இருக்கிறதா என்பதைத் தீர்மானிக்கவும், அதாவது முதல் உருப்படிகளின் (ஜோடிகளின்) ஒருங்கிணைப்பு இரண்டாவது உருப்படிகளின் இணைப்புக்கு சமமாக இருக்கும். ஒரு டயோஃபாண்டைன் சமன்பாட்டிற்கு ஏதேனும் முழு எண் தீர்வுகள் உள்ளதா என்பதை தீர்மானித்தல். கோ-ஆர்இ-கம்ப்லீட் கோ-ஆர்இ-கம்ப்லீட் என்பது கோ-ஆர்இக்கு முழுமையான முடிவு சிக்கல்களின் தொகுப்பாகும். ஒரு வகையில், இவை கடினமான தொடர்ச்சியான கணக்கிடக்கூடிய சிக்கல்களின் நிரப்பு. இணை-RE-முழுமையான சிக்கல்களின் எடுத்துக்காட்டுகள்ஃ வாங் ஓடுகளுக்கான டோமினோ சிக்கல். முதல் வரிசை தர்க்கத்திற்கான திருப்திகரமான சிக்கல். மேலும் காண்க க்னுத்-பெண்டிக்ஸ் நிறைவு வழிமுறை தீர்மானிக்க முடியாத சிக்கல்களின் பட்டியல் பாலிமார்பிக் மறுசுழற்சி ரிஷ் வழிமுறை அரை நிலைப்படுத்துதல் குறிப்புகள் சிக்கலான வகுப்புகள் தீர்மானிக்க முடியாத சிக்கல்கள்