டூரிங் இயந்திரங்களின் அனைத்து வெவ்வேறு மாறுபாடுகளும் கம்ப்யூட்டிங் திறனில் சமமானவையா என்பது பற்றிய விசாரணை கோட்பாட்டு கணினி அறிவியல் துறையில், குறிப்பாக கணக்கீட்டு சிக்கலான கோட்பாடு மற்றும் தீர்மானம் பற்றிய ஆய்வில் ஒரு அடிப்படை கேள்வியாகும். இதை நிவர்த்தி செய்ய, டூரிங் இயந்திரங்களின் தன்மை மற்றும் கணக்கீட்டு சமநிலையின் கருத்தை கருத்தில் கொள்வது அவசியம்.
ஒரு ட்யூரிங் இயந்திரம் என்பது 1936 ஆம் ஆண்டில் ஆலன் டூரிங் அறிமுகப்படுத்திய ஒரு சுருக்கமான கணித மாதிரியாகும். இது ஒரு எல்லையற்ற டேப், டேப்பில் குறியீடுகளைப் படிக்கவும் எழுதவும் கூடிய டேப் ஹெட், வரையறுக்கப்பட்ட நிலைகளின் தொகுப்பு மற்றும் மாறுதல் செயல்பாடு ஆகியவற்றைக் கொண்டுள்ளது. தற்போதைய நிலை மற்றும் படிக்கப்படும் சின்னத்தின் அடிப்படையில் இயந்திரத்தின் செயல்களை ஆணையிடுகிறது. நிலையான டூரிங் இயந்திரம், பெரும்பாலும் "கிளாசிக்கல்" அல்லது "ஒற்றை-நாடா" டூரிங் இயந்திரம் என்று குறிப்பிடப்படுகிறது, இது கணக்கீட்டு செயல்முறைகளை வரையறுப்பதற்கான அடிப்படை மாதிரியாக செயல்படுகிறது.
டூரிங் இயந்திரங்களில் பல வேறுபாடுகள் உள்ளன, ஒவ்வொன்றும் வெவ்வேறு கட்டமைப்புகள் அல்லது மேம்பாடுகளுடன். சில குறிப்பிடத்தக்க மாறுபாடுகள் பின்வருமாறு:
1. பல டேப் ட்யூரிங் இயந்திரங்கள்: இந்த இயந்திரங்களில் பல டேப்கள் மற்றும் தொடர்புடைய டேப் ஹெட்கள் உள்ளன. ஒவ்வொரு டேப்பும் சுயாதீனமாக இயங்குகிறது, மேலும் மாற்றம் செயல்பாடு அனைத்து நாடாக்களிலிருந்தும் வாசிக்கப்படும் சின்னங்களைப் பொறுத்தது. அதிகரித்த சிக்கலான போதிலும், மல்டி-டேப் ட்யூரிங் இயந்திரங்கள் ஒற்றை-டேப் டூரிங் இயந்திரங்களுக்கு கணக்கீட்டு ரீதியாக சமமானவை. மல்டி-டேப் ட்யூரிங் இயந்திரத்தால் செய்யப்படும் எந்தவொரு கணக்கீடும் ஒற்றை-டேப் டூரிங் இயந்திரத்தால் உருவகப்படுத்தப்படலாம், இருப்பினும் தேவையான படிகளின் எண்ணிக்கையில் பல்லுறுப்புக்கோவை அதிகரிப்பு இருக்கலாம்.
2. நிர்ணயம் செய்யாத டூரிங் இயந்திரங்கள் (NTMs): இந்த இயந்திரங்கள் கொடுக்கப்பட்ட நிலை மற்றும் உள்ளீட்டு சின்னத்திற்கு பல மாற்றங்களைச் செய்யலாம், பல கணக்கீட்டுப் பாதைகளில் திறம்படக் கிளைக்கும். NTMகள் ஒரே நேரத்தில் பல கணக்கீட்டு பாதைகளை ஆராய முடியும் என்றாலும், அவை கணக்கீட்டு ரீதியாக நிர்ணயிக்கும் டூரிங் இயந்திரங்களுக்கு (டிடிஎம்கள்) சமமானவை. NTM ஆல் அங்கீகரிக்கப்பட்ட எந்த மொழியும் DTM ஆல் அங்கீகரிக்கப்படலாம், இருப்பினும் உருவகப்படுத்துதலுக்கு மோசமான நிலையில் அதிவேக நேரம் தேவைப்படலாம்.
3. யுனிவர்சல் டூரிங் மெஷின்கள் (UTMகள்): ஒரு UTM என்பது ஒரு ட்யூரிங் இயந்திரம் ஆகும், இது வேறு எந்த டூரிங் இயந்திரத்தையும் உருவகப்படுத்த முடியும். இது மற்றொரு ட்யூரிங் இயந்திரத்தின் விளக்கத்தையும் அந்த இயந்திரத்திற்கான உள்ளீட்டு சரத்தையும் உள்ளீடாக எடுத்துக்கொள்கிறது. UTM பின்னர் உள்ளீட்டு சரத்தில் விவரிக்கப்பட்ட இயந்திரத்தின் நடத்தையை உருவகப்படுத்துகிறது. யுடிஎம்களின் இருப்பு, டூரிங் இயந்திர மாதிரியின் உலகளாவிய தன்மையை உயர்த்தி, வேறு எந்த டூரிங் இயந்திரமும் செய்யக்கூடிய எந்தவொரு கணக்கீட்டையும் ஒரு இயந்திரம் செய்ய முடியும் என்பதை நிரூபிக்கிறது.
4. அரை முடிவிலி நாடாக்கள் கொண்ட டூரிங் இயந்திரங்கள்: இந்த இயந்திரங்கள் ஒரே ஒரு திசையில் எல்லையற்ற டேப்களைக் கொண்டுள்ளன. அவை கணக்கீட்டு ரீதியாக நிலையான டூரிங் இயந்திரங்களுக்குச் சமமானவை, ஏனெனில் அரை-எல்லையற்ற டேப் டூரிங் இயந்திரத்தால் செய்யப்படும் எந்தவொரு கணக்கீடும் டேப் உள்ளடக்கங்களின் பொருத்தமான குறியாக்கத்துடன் ஒரு நிலையான டூரிங் இயந்திரத்தால் உருவகப்படுத்தப்படலாம்.
5. பல தலைகள் கொண்ட டூரிங் இயந்திரங்கள்: இந்த இயந்திரங்களில் பல டேப் ஹெட்கள் உள்ளன, அவை ஒரே டேப்பில் படிக்கவும் எழுதவும் முடியும். மல்டி-டேப் டூரிங் இயந்திரங்களைப் போலவே, மல்டி-ஹெட் டூரிங் இயந்திரங்களும் கணக்கீட்டு ரீதியாக ஒற்றை-டேப் டூரிங் இயந்திரங்களுக்குச் சமமானவை, உருவகப்படுத்துதலுக்கு கூடுதல் படிகள் தேவைப்படும்.
6. மாற்று டூரிங் இயந்திரங்கள் (ஏடிஎம்கள்): இந்த இயந்திரங்கள் மாநிலங்களை இருத்தலியல் அல்லது உலகளாவியதாகக் குறிப்பிட அனுமதிப்பதன் மூலம் NTM களைப் பொதுமைப்படுத்துகின்றன. இருத்தலியல் மற்றும் உலகளாவிய நிலைமைகளைப் பூர்த்தி செய்யும் ஆரம்ப நிலையிலிருந்து ஏற்றுக்கொள்ளும் நிலைக்கு நகர்வுகளின் வரிசை இருந்தால் ஏடிஎம் உள்ளீட்டை ஏற்றுக்கொள்கிறது. ஏடிஎம்கள் அவர்கள் அங்கீகரிக்கும் மொழிகளின் அடிப்படையில் டிடிஎம்களுக்கு கணக்கீட்டு ரீதியாக சமமானவை, இருப்பினும் அவை வகைப்படுத்தும் சிக்கலான வகுப்புகள், அதாவது பல்லுறுப்புக்கோவை படிநிலை போன்றவை வேறுபடுகின்றன.
7. குவாண்டம் டூரிங் இயந்திரங்கள் (QTMs): இந்த இயந்திரங்கள் குவாண்டம் இயக்கவியலின் கொள்கைகளை உள்ளடக்கி, நிலைகளின் மேல்நிலை மற்றும் சிக்கலை அனுமதிக்கிறது. கிளாசிக்கல் டூரிங் இயந்திரங்களை விட QTMகள் சில சிக்கல்களை மிகவும் திறமையாக தீர்க்க முடியும் (எ.கா., ஷோரின் அல்காரிதத்தைப் பயன்படுத்தி பெரிய முழு எண்களை காரணியாக்குவது), கணக்கிடக்கூடிய செயல்பாடுகளின் வகுப்பின் அடிப்படையில் அவை அதிக சக்தி வாய்ந்தவை அல்ல. க்யூடிஎம் மூலம் கணக்கிடக்கூடிய எந்தவொரு செயல்பாடும் கிளாசிக்கல் டூரிங் இயந்திரத்தால் கணக்கிடப்படுகிறது.
கணினித் திறனில் வெவ்வேறு டூரிங் இயந்திர மாறுபாடுகளின் சமநிலை சர்ச்-டூரிங் ஆய்வறிக்கையில் உள்ளது. எந்தவொரு நியாயமான கணக்கீட்டு மாதிரியினாலும் திறம்பட கணக்கிடக்கூடிய எந்தவொரு செயல்பாட்டையும் ஒரு டூரிங் இயந்திரத்தால் கணக்கிட முடியும் என்று இந்த ஆய்வறிக்கை கூறுகிறது. இதன் விளைவாக, டூரிங் இயந்திரங்களின் மேற்கூறிய அனைத்து மாறுபாடுகளும், செயல்திறனில் அல்லது உருவகப்படுத்துதலின் சிக்கலான தன்மையில் வேறுபட்டாலும், செயல்பாடுகளைக் கணக்கிடுவதற்கும் மொழிகளை அங்கீகரிக்கும் திறனுக்கும் சமமானதாகும்.
இந்த சமநிலையை விளக்குவதற்கு, ஒற்றை-டேப் டூரிங் இயந்திரத்தைப் பயன்படுத்தி பல-டேப் ட்யூரிங் இயந்திரத்தை உருவகப்படுத்தும் பணியைக் கவனியுங்கள். எங்களிடம் (k) டேப்கள் கொண்ட பல-டேப் ட்யூரிங் இயந்திரம் உள்ளது என்று வைத்துக்கொள்வோம். அனைத்து (k) டேப்களின் உள்ளடக்கங்களையும் ஒரே டேப்பில் குறியாக்கம் செய்வதன் மூலம் இந்த இயந்திரத்தை ஒற்றை-டேப் டூரிங் இயந்திரத்துடன் உருவகப்படுத்தலாம். ஒற்றை-நாடா இயந்திரத்தின் டேப்பை (k) பிரிவுகளாகப் பிரிக்கலாம், ஒவ்வொன்றும் அசல் நாடாக்களில் ஒன்றைக் குறிக்கும். இயந்திரத்தின் நிலை ஒவ்வொரு (k) டேப்களிலும் உள்ள டேப் ஹெட்களின் நிலைகள் பற்றிய தகவலைச் சேர்க்கலாம். ஒற்றை-நாடா இயந்திரத்தின் மாறுதல் செயல்பாடு, குறியிடப்பட்ட டேப் உள்ளடக்கங்கள் மற்றும் தலை நிலைகளை அதற்கேற்ப புதுப்பிப்பதன் மூலம் மல்டி-டேப் இயந்திரத்தின் நடத்தையைப் பிரதிபலிக்கும் வகையில் வடிவமைக்கப்படலாம். இந்த உருவகப்படுத்துதலுக்கு அசல் மல்டி-டேப் இயந்திரத்தை விட அதிகமான படிகள் தேவைப்படலாம் என்றாலும், ஒற்றை-நாடா இயந்திரம் அதே கணக்கீட்டைச் செய்ய முடியும் என்பதை இது நிரூபிக்கிறது.
இதேபோல், ஒரு தீர்மானமற்ற டூரிங் இயந்திரத்தை ஒரு உறுதியான டூரிங் இயந்திரத்துடன் உருவகப்படுத்துவது, NTM இன் சாத்தியமான அனைத்து கணக்கீட்டு பாதைகளையும் முறையாக ஆராய்வதை உள்ளடக்கியது. அகலம்-முதல் தேடல் அல்லது ஆழம்-முதல் தேடல் போன்ற நுட்பங்களைப் பயன்படுத்தி இதை அடையலாம், அனைத்து பாதைகளும் இறுதியில் ஆய்வு செய்யப்படுவதை உறுதி செய்கிறது. உருவகப்படுத்துதல் அதிவேகமாக மெதுவாக இருந்தாலும், DTM ஆனது NTM போன்ற அதே மொழிகளை அங்கீகரிக்க முடியும் என்பதை உறுதிப்படுத்துகிறது.
டூரிங் இயந்திரங்களின் உலகளாவிய தன்மை உலகளாவிய டூரிங் இயந்திரங்களின் இருப்பு மூலம் எடுத்துக்காட்டுகிறது. இலக்கு இயந்திரம் மற்றும் அதன் உள்ளீட்டின் விளக்கத்தை விளக்குவதன் மூலம் ஒரு UTM வேறு எந்த டூரிங் இயந்திரத்தையும் உருவகப்படுத்த முடியும். ஒரு கணக்கீட்டு மாதிரியானது மற்ற எல்லா மாதிரிகளின் நடத்தையையும் இணைக்க முடியும் என்ற அடிப்படைக் கொள்கையை இந்த திறன் அடிக்கோடிட்டுக் காட்டுகிறது, இது கணக்கீட்டு சமநிலையின் கருத்தை வலுப்படுத்துகிறது.
டூரிங் இயந்திரங்களின் வெவ்வேறு மாறுபாடுகள் செயல்திறன், நிரலாக்கத்தின் எளிமை அல்லது கருத்தியல் தெளிவு ஆகியவற்றின் அடிப்படையில் தனித்துவமான நன்மைகளை வழங்கக்கூடும் என்றாலும், அவை அனைத்தும் கணினித் திறனில் சமமானவை. இந்த சமன்பாடு கோட்பாட்டு கணினி அறிவியலின் ஒரு மூலக்கல்லாகும், இது கணக்கீட்டின் வரம்புகள் மற்றும் தீர்மானத்தின் தன்மையைப் புரிந்துகொள்வதற்கான ஒரு ஒருங்கிணைந்த கட்டமைப்பை வழங்குகிறது.
தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் கணக்கிடக்கூடிய செயல்பாடுகள்:
- கணக்கிடக்கூடிய செயல்பாட்டிற்கும் அதைக் கணக்கிடக்கூடிய ட்யூரிங் இயந்திரத்தின் இருப்புக்கும் உள்ள தொடர்பை விளக்குக.
- கணக்கிடக்கூடிய செயல்பாட்டைக் கணக்கிடும்போது டூரிங் இயந்திரம் எப்போதும் நிறுத்தப்படுவதன் முக்கியத்துவம் என்ன?
- ஒரு ட்யூரிங் இயந்திரத்தை எப்போதும் ஒரு செயல்பாட்டை ஏற்றுக்கொள்ளும் வகையில் மாற்றியமைக்க முடியுமா? ஏன் அல்லது ஏன் இல்லை என்பதை விளக்குங்கள்.
- டூரிங் இயந்திரம் ஒரு செயல்பாட்டை எவ்வாறு கணக்கிடுகிறது மற்றும் உள்ளீடு மற்றும் வெளியீட்டு நாடாக்களின் பங்கு என்ன?
- கணக்கீட்டு சிக்கலான கோட்பாட்டின் சூழலில் கணக்கிடக்கூடிய செயல்பாடு என்றால் என்ன, அது எவ்வாறு வரையறுக்கப்படுகிறது?