Essential complexity
அத்தியாவசிய சிக்கலானது ஒரு எண் அளவீடு ஆகும், இது தாமஸ் ஜே. மெக்கேப், சீனியர், அவரது மிகவும் மேற்கோள் காட்டப்பட்ட, 1976 ஆய்வறிக்கையில் சைக்ளோமாட்டிக் சிக்கலை அறிமுகப்படுத்துவதில் நன்கு அறியப்பட்டவர். அனைத்து கட்டமைக்கப்பட்ட நிரலாக்க கட்டுப்பாட்டு கட்டமைப்புகளையும் மீண்டும் மீண்டும் மாற்றியமைத்த பிறகு (குறைத்த பிறகு) குறைக்கப்பட்ட சிஎஃப்ஜியின் (கட்டுப்பாட்டு-ஓட்ட வரைபடம்) சுழற்சி சிக்கலானது அத்தியாவசிய சிக்கலானது என்று மெக்கேப் வரையறுத்தார். ஒற்றை நுழைவு புள்ளி மற்றும் ஒற்றை வெளியேறும் புள்ளி (எடுத்துக்காட்டாக என்றால்-பின்னர்-மற்ற மற்றும் சுழற்சிகள் இருக்கும் போது) பிளேஸ்ஹோல்டர் ஒற்றை அறிக்கைகளுடன். மெக்கேப்பின் குறைப்பு செயல்முறை கட்டுப்பாட்டு கட்டமைப்புகளின் கருத்தியல் மாற்றீட்டை (மற்றும் அவை கொண்ட உண்மையான அறிக்கைகள்) சப்ரூட்டின் அழைப்புகளுடன் உருவகப்படுத்துவதை நோக்கமாகக் கொண்டுள்ளது, எனவே கட்டுப்பாட்டு கட்டமைப்புகளுக்கு ஒற்றை நுழைவு மற்றும் ஒற்றை வெளியேறும் புள்ளி இருக்க வேண்டும். (இப்போதெல்லாம் இது போன்ற ஒரு செயல்முறை மறுசீரமைப்பு என்ற குடையின் கீழ் வரும்.) அனைத்து கட்டமைக்கப்பட்ட நிரல்களும் மெக்கேப் வரையறுத்தபடி 1 இன் அத்தியாவசிய சிக்கலைக் கொண்டுள்ளன, ஏனெனில் அவை அனைத்தும் ஒரு உயர்மட்ட சப்ரூட்டினுக்கு ஒரே அழைப்பாக மீண்டும் மீண்டும் குறைக்கப்படலாம். மெக்கேப் தனது கட்டுரையில் விளக்கியது போல், அவரது அத்தியாவசிய சிக்கலான அளவீடு ஒரு கொடுக்கப்பட்ட திட்டம் இந்த இலட்சியத்திலிருந்து (முழுமையாக கட்டமைக்கப்படுவது) எவ்வளவு தொலைவில் உள்ளது என்பதை அளவிட வடிவமைக்கப்பட்டுள்ளது. எனவே 1 க்கும் மேற்பட்ட அத்தியாவசிய சிக்கலான எண்கள், அவை கட்டமைக்கப்படாத நிரல்களுக்கு மட்டுமே பெற முடியும், அவை கட்டமைக்கப்பட்ட நிரலாக்க இலட்சியத்திலிருந்து மேலும் தொலைவில் உள்ளன என்பதைக் குறிக்கின்றன. கட்டமைக்கப்பட்ட திட்டங்களுக்கு குறைப்புத்திறன் பற்றிய பல்வேறு கருத்துக்களுக்கு இடையிலான குழப்பத்தைத் தவிர்க்க, மெக்கேப்பின் கட்டுரை சுருக்கமாக விவாதித்து பின்னர் எஸ். ராவ் கோசராஜுவின் 1973 ஆம் ஆண்டு ஆய்வறிக்கையின் சூழலில் செயல்படுகிறது என்பதைக் குறிப்பிடுவது முக்கியம், இது கட்டமைக்கப்பட்ட நிரல் தேற்றத்தின் சுத்திகரிப்பை (அல்லது மாற்றுக் கண்ணோட்டத்தை) வழங்கியது. இருப்பினும், ஒரு சீரற்ற நிரலை ஒரு கட்டமைக்கப்பட்ட நிரலாக மாற்றுவதில் கூடுதல் மாறிகள் அறிமுகப்படுத்தப்பட வேண்டும் (மற்றும் சோதனைகளில் பயன்படுத்தப்படலாம்) மற்றும் சில குறியீடுகள் நகலெடுக்கப்படலாம், இருப்பினும், அனைத்து நிரல்களையும் கட்டமைக்கப்பட்ட நிரலாக்க கட்டமைப்புகளை மட்டுமே பயன்படுத்தி எழுத முடியும் என்பதை போம் மற்றும் ஜாகோபினியின் 1966 ஆம் ஆண்டின் ஆரம்ப ஆய்வுக் கட்டுரை காட்டுகிறது. தங்கள் கட்டுரையில், போம் மற்றும் ஜாகோபினி யூகித்தனர், ஆனால் சில வகையான கட்டமைக்கப்படாத நிரல்களுக்கு கட்டமைக்கப்பட்ட நிரல்களாக மாற்றுவதற்காக இதுபோன்ற கூடுதல் மாறிகளை அறிமுகப்படுத்துவது அவசியம் என்பதை நிரூபிக்கவில்லை. நிரலின் ஒரு எடுத்துக்காட்டு (இப்போது நமக்குத் தெரியும்) அத்தகைய கூடுதல் மாறிகள் தேவைப்படுகிறது, அதற்குள் இரண்டு நிபந்தனை வெளியேறும் வளையமாகும். போம் மற்றும் ஜாகோபினியின் அனுமானத்தை நிவர்த்தி செய்வதற்காக, கோசராஜு போம் மற்றும் ஜாகோபினி பயன்படுத்திய டூரிங் சமநிலையை விட நிரல் குறைப்பு பற்றிய மிகவும் கட்டுப்படுத்தப்பட்ட கருத்தை வரையறுத்தார். அடிப்படையில், குறைப்பு பற்றிய கோசராஜுவின் கருத்து, இரண்டு நிரல்களும் ஒரே உள்ளீடுகளைக் கொடுத்தால் ஒரே மதிப்பைக் கணக்கிட வேண்டும் (அல்லது முடிக்கக்கூடாது) என்ற வெளிப்படையான தேவையைத் தவிர, இரண்டு நிரல்களும் ஒரே பழமையான செயல்களையும் கணிப்புகளையும் பயன்படுத்த வேண்டும், பிந்தையது நிபந்தனைகளில் பயன்படுத்தப்படும் வெளிப்பாடுகளாகப் புரிந்து கொள்ளப்படுகிறது. இந்த கட்டுப்பாடுகள் காரணமாக, கோசராஜுவின் குறைப்பு கூடுதல் மாறிகளை அறிமுகப்படுத்த அனுமதிக்காது; இந்த மாறிகளுக்கு ஒதுக்குவது புதிய பழமையான செயல்களை உருவாக்கும் மற்றும் அவற்றின் மதிப்புகளைச் சோதிப்பது நிபந்தனைகளில் பயன்படுத்தப்படும் கணிப்புகளை மாற்றும். குறைப்பு பற்றிய இந்த மிகவும் கட்டுப்படுத்தப்பட்ட கருத்தைப் பயன்படுத்தி, கோசராஜு பாம் மற்றும் ஜாகோபினியின் அனுமானத்தை நிரூபித்தார், அதாவது இரண்டு வெளியேறும் ஒரு வளையத்தை கூடுதல் மாறிகளை அறிமுகப்படுத்தாமல் ஒரு கட்டமைக்கப்பட்ட நிரலாக மாற்ற முடியாது, ஆனால் மேலும் சென்று பல நிலை இடைவெளிகளைக் கொண்ட நிரல்கள் (சுழல்களிலிருந்து) ஒரு படிநிலையை உருவாக்குகின்றன என்பதை நிரூபித்தது, அதாவது ஒருவர் எப்போதும் பல நிலை இடைவெளிகள் கொண்ட ஒரு நிரலைக் காணலாம். கொசாராஜுவின் முடிவுகளைக் கருத்தில் கொண்டு, கட்டமைக்கப்படாத நிரல்களின் கட்டுப்பாட்டு-ஓட்ட வரைபடங்களின் அடிப்படையில் அவற்றின் அத்தியாவசிய பண்புகளைப் பிடிக்க ஒரு வழியைக் கண்டுபிடிக்க அவர் விரும்பினார் என்று மெக்கேப் தனது கட்டுரையில் குறிப்பிடுகிறார். குரடோவ்ஸ்கியின் தேற்றத்திற்கு ஒத்த ஒரு தேற்றத்தை உருவாக்க அவர் பயன்படுத்தும் மிகச்சிறிய கட்டமைக்கப்படாத நிரல்களுடன் தொடர்புடைய கட்டுப்பாட்டு-ஓட்ட வரைபடங்களை (இவற்றில் ஒரு சுழற்சியில் கிளைப்பது, ஒரு சுழற்சியில் இருந்து கிளைப்பது மற்றும் அவற்றின் இல்லையென்றால்-மற்ற சகாக்கள் அடங்கும்) முதலில் அடையாளம் காண்பதன் மூலம் அவர் தொடர்கிறார், அதன்பிறகு அவர் ஒரு நிரலின் கட்டுப்பாட்டு-ஓட்ட வரைபடம் கட்டமைக்கப்பட்டுள்ளதா இல்லையா என்ற கேள்விக்கு ஆம்/இல்லை என்ற பதிலைக் காட்டிலும் ஒரு அளவிலான பதிலை (அவரது வார்த்தைகளில் ஒரு நிரலின் கட்டமைப்பின் அளவீடு) வழங்குவதற்காக அத்தியாவசிய சிக்கல் பற்றிய தனது கருத்தை அறிமுகப்படுத்துகிறார். இறுதியாக, சி. எஃப். ஜி. யைக் குறைக்க மெக்கேப் பயன்படுத்திய குறைப்பு என்ற கருத்து ஃப்ளோசார்ட்களைக் குறைப்பதற்கான கோசராஜுவின் கருத்தைப் போன்றது அல்ல. சிஎஃப்ஜியில் வரையறுக்கப்பட்ட குறைப்பு நிரலின் உள்ளீடுகளைப் பற்றி தெரியாது அல்லது கவலைப்படவில்லை, இது வெறுமனே ஒரு வரைபட மாற்றமாகும். எடுத்துக்காட்டாக, பின்வரும் சி நிரல் துண்டு 1 இன் அத்தியாவசிய சிக்கலைக் கொண்டுள்ளது, ஏனெனில் உள் இஃப் ஸ்டேட்மென்ட் மற்றும் ஃபார் ஆகியவற்றைக் குறைக்கலாம், அதாவது. இது ஒரு கட்டமைக்கப்பட்ட திட்டமாகும். (i = 0; i <3; i + +) {என்றால் (a [i] = = 0) b [i] + = 2;} பின்வரும் C நிரல் துண்டு நான்கு அத்தியாவசிய சிக்கலைக் கொண்டுள்ளது; அதன் CFG பகுக்கமுடியாதது. நிரல் பூஜ்ஜியமாக இருக்கும் z இன் முதல் வரிசையைக் கண்டுபிடித்து, அந்த குறியீட்டை i இல் வைக்கிறது; எதுவும் இல்லையென்றால், அது-1 ஐ i இல் வைக்கிறது. இருப்பினும், ஒற்றை-நுழைவு மற்றும் ஒற்றை-வெளியேறும் கட்டுப்பாட்டு கட்டமைப்பின் கட்டமைக்கப்பட்ட நிரலாக்கத்தின் கருத்து இயற்கையான வளையத்துடன் மாற்றப்படுகிறது, இது "ஒற்றை-நுழைவு, பல-வெளியேறும் வளையம், அதன் உள்ளே இருந்து நுழைவதற்கு ஒரு கிளை மட்டுமே உள்ளது" என்று வரையறுக்கப்படுகிறது. இயற்கையான சுழல்களாக குறைக்க முடியாத சிஎஃப்ஜியின் பகுதிகள் முறையற்ற பகுதிகள் என்று அழைக்கப்படுகின்றன; இந்த பகுதிகள் மிகவும் எளிமையான வரையறையைக் கொண்டுள்ளனஃ சிஎஃப்ஜியின் பல-நுழைவு, வலுவாக இணைக்கப்பட்ட கூறுகள். எளிமையான முறையற்ற பகுதி இரண்டு நுழைவு புள்ளிகளைக் கொண்ட ஒரு வளையமாகும். பல வெளியேற்றம் நவீன தொகுப்பாளர்களில் பகுப்பாய்வு சிக்கல்களை ஏற்படுத்தாது. முறையற்ற பகுதிகள் (சுழல்களில் பல-உள்ளீடுகள்) குறியீட்டை மேம்படுத்துவதில் கூடுதல் சிரமங்களை ஏற்படுத்துகின்றன. மேலும் காண்க மென்பொருள் பொறியியல் முடிவு-க்கு-முடிவு பாதை சுழற்சி சிக்கல் குறிப்புகள் மென்பொருள் திட்ட மேலாண்மை மென்பொருள் அளவீடுகள் வரலாறு