கணக்கீட்டு சிக்கலான கோட்பாட்டின் பின்னணியில் கணக்கிடக்கூடிய செயல்பாடு, ஒரு அல்காரிதம் மூலம் திறம்பட கணக்கிடக்கூடிய செயல்பாட்டைக் குறிக்கிறது. இது கணினி அறிவியல் துறையில் ஒரு அடிப்படைக் கருத்தாகும் மற்றும் கணக்கீட்டின் வரம்புகளைப் புரிந்துகொள்வதில் முக்கிய பங்கு வகிக்கிறது.
கணக்கிடக்கூடிய செயல்பாட்டை வரையறுக்க, கணக்கீட்டு மாதிரிகளின் திறன்கள் மற்றும் வரம்புகளைப் பற்றி நியாயப்படுத்த அனுமதிக்கும் முறையான கட்டமைப்பை நாம் நிறுவ வேண்டும். 1936 ஆம் ஆண்டில் ஆலன் டூரிங் அறிமுகப்படுத்திய டூரிங் இயந்திரம் அத்தகைய ஒரு கட்டமைப்பாகும். ட்யூரிங் இயந்திரம் என்பது ஒரு சுருக்கமான கணித மாதிரியாகும், இது செல்களாகப் பிரிக்கப்பட்ட டேப், படிக்க-எழுதும் தலை மற்றும் மாநிலங்களின் தொகுப்பைக் கொண்டுள்ளது. தற்போதைய கலத்தில் உள்ள குறியீட்டைப் படித்து, தற்போதைய நிலை மற்றும் குறியீட்டின் அடிப்படையில் ஒரு புதிய நிலைக்கு மாறுதல் மற்றும் தற்போதைய கலத்தில் உள்ள குறியீட்டை மாற்றுவதன் மூலம் இயந்திரம் செயல்படுகிறது. இது படிக்க-எழுதும் தலையை ஒரு கலத்தை இடது அல்லது வலது பக்கம் நகர்த்தலாம்.
டூரிங் இயந்திரங்களின் சூழலில், கணக்கிடக்கூடிய செயல்பாடு என்பது ஒரு டூரிங் இயந்திரம் இருக்கும் ஒரு செயல்பாடாக வரையறுக்கப்படுகிறது, அது எந்த உள்ளீட்டையும் கொடுத்தால், அந்த உள்ளீட்டிற்கான சரியான வெளியீட்டை நிறுத்துகிறது மற்றும் உற்பத்தி செய்கிறது. வேறு வார்த்தைகளில் கூறுவதானால், எந்தவொரு உள்ளீட்டிற்கும் அதன் மதிப்பைக் கணக்கிடக்கூடிய ஒரு அல்காரிதம் இருந்தால், ஒரு செயல்பாடு கணக்கிடப்படும். கொடுக்கப்பட்ட உள்ளீடு ஒரு குறிப்பிட்ட சொத்தை திருப்திப்படுத்துகிறதா என்பதை தீர்மானிக்கும் திறனைக் குறிக்கும் தீர்மானம் என்ற கருத்துடன் இந்த கருத்து நெருக்கமாக தொடர்புடையது.
கணக்கிடக்கூடிய செயல்பாடுகளின் கருத்தை நேர சிக்கலான கருத்தைப் பயன்படுத்தி மேலும் முறைப்படுத்தலாம். நேர சிக்கலானது, உள்ளீட்டின் அளவின் செயல்பாடாக சிக்கலைத் தீர்க்க ஒரு அல்காரிதம் தேவைப்படும் நேரத்தை அளவிடுகிறது. உள்ளீட்டின் அளவு பல்லுறுப்புக்கோவையாக இருக்கும் பல படிகளில் செயல்பாட்டைக் கணக்கிடக்கூடிய ஒரு ட்யூரிங் இயந்திரம் இருந்தால், பல்லுறுப்புக்கோவை நேரத்தில் ஒரு சார்பு கணக்கிடத்தக்கது என்று கூறப்படுகிறது. பல்லுறுப்புக்கோவை நேரத்தைக் கணக்கிடக்கூடிய செயல்பாடுகள் திறமையானதாகக் கருதப்படுகின்றன, ஏனெனில் அவற்றின் இயங்கும் நேரம் உள்ளீட்டு அளவுடன் பல்லுறுப்புக்கோவையாக வளர்கிறது.
கணக்கிடக்கூடிய செயல்பாடுகளின் கருத்தை விளக்க, கொடுக்கப்பட்ட எண் முதன்மையானதா என்பதை தீர்மானிக்கும் செயல்பாட்டைக் கருத்தில் கொள்வோம். இந்தச் சார்பு ஒரு உள்ளீட்டை n எடுத்து, n பிரைம் என்றால் சரி என்றும் இல்லையெனில் பொய் என்றும் வழங்கும். எரடோஸ்தீனஸின் சல்லடை போன்ற ஒரு அல்காரிதம் இருப்பதால், முதன்மை சோதனைச் செயல்பாடு கணக்கிடத்தக்கது, இது எந்த எண்ணின் முதன்மைத்தன்மையையும் தீர்மானிக்க முடியும்.
இதற்கு நேர்மாறாக, கொடுக்கப்பட்ட நிரல் ஒரு குறிப்பிட்ட உள்ளீட்டில் நிறுத்தப்படுகிறதா என்பதைத் தீர்மானிக்கும் செயல்பாட்டைக் கவனியுங்கள். நிறுத்துதல் பிரச்சனை எனப்படும் இந்த செயல்பாடு கணக்கிட முடியாதது. இதை 1936 ஆம் ஆண்டில் ஆலன் டூரிங் நிரூபித்தார், மூலைவிட்டமாக்கல் எனப்படும் நுட்பத்தைப் பயன்படுத்தி. டூரிங்கின் ஆதாரம், எந்த ஒரு நிரல் மற்றும் உள்ளீட்டிற்கும், நிரல் நிறுத்தப்படுமா அல்லது என்றென்றும் இயங்குமா என்பதை தீர்மானிக்கும் வழிமுறை எதுவும் இருக்க முடியாது என்பதைக் காட்டுகிறது.
கணக்கீட்டு சிக்கலான கோட்பாட்டின் சூழலில் ஒரு கணக்கிடக்கூடிய செயல்பாடு என்பது ஒரு அல்காரிதம் மூலம் திறம்பட கணக்கிடக்கூடிய ஒரு செயல்பாட்டைக் குறிக்கிறது. இது கணினி அறிவியலில் ஒரு அடிப்படைக் கருத்தாகும், மேலும் தீர்மானம் என்ற கருத்துடன் நெருங்கிய தொடர்புடையது. கணக்கிடக்கூடிய செயல்பாடுகளின் கருத்து டூரிங் இயந்திரங்கள் மற்றும் நேர சிக்கலைப் பயன்படுத்தி முறைப்படுத்தப்படுகிறது. பல செயல்பாடுகள் கணக்கிடக்கூடியவையாக இருந்தாலும், நிறுத்தும் சிக்கல் போன்ற செயல்பாடுகளும் உள்ளன, அவை கணக்கிட முடியாதவை.
தொடர்பான பிற சமீபத்திய கேள்விகள் மற்றும் பதில்கள் கணக்கிடக்கூடிய செயல்பாடுகள்:
- டூரிங் இயந்திரங்களின் வெவ்வேறு மாறுபாடுகள் கணினித் திறனில் சமமானதாக இருப்பதன் அர்த்தம் என்ன?
- கணக்கிடக்கூடிய செயல்பாட்டிற்கும் அதைக் கணக்கிடக்கூடிய ட்யூரிங் இயந்திரத்தின் இருப்புக்கும் உள்ள தொடர்பை விளக்குக.
- கணக்கிடக்கூடிய செயல்பாட்டைக் கணக்கிடும்போது டூரிங் இயந்திரம் எப்போதும் நிறுத்தப்படுவதன் முக்கியத்துவம் என்ன?
- ஒரு ட்யூரிங் இயந்திரத்தை எப்போதும் ஒரு செயல்பாட்டை ஏற்றுக்கொள்ளும் வகையில் மாற்றியமைக்க முடியுமா? ஏன் அல்லது ஏன் இல்லை என்பதை விளக்குங்கள்.
- டூரிங் இயந்திரம் ஒரு செயல்பாட்டை எவ்வாறு கணக்கிடுகிறது மற்றும் உள்ளீடு மற்றும் வெளியீட்டு நாடாக்களின் பங்கு என்ன?