இருக்க முடியாத ஒரு சிறிய கணினி நிரலில் குறைந்தது ஒரு சான்று

மிக அழகான கணித சான்றுகள், தொகுதி. 2, மேக்சிம் க out ட்.

கடந்த வார கட்டுரை “சில முடிவிலிகள் மற்றவர்களை விட பெரியதா?” மற்றும் கேன்டர் மூலைவிட்ட வாதம். இந்த வாரம் எனக்கு பிடித்த தத்துவார்த்த கணினி அறிவியல் சிக்கலில் ஒன்றைப் பகிர விரும்புகிறேன்.

நான் கம்ப்யூட்டர் சயின்ஸ் செய்யத் தொடங்கியபோது நடுநிலைப் பள்ளியில் மீண்டும் நினைவில் வைத்திருக்கிறேன், சரியான கணிதக் கருவிகள் மற்றும் புரோகிராமிங் மூலம் எந்தவொரு கணக்கீட்டு சிக்கலையும் கோட்பாட்டளவில் தீர்க்க முடியும் என்று நினைத்தேன். நான் கருதியது தவறு. எந்தவொரு கம்ப்யூட்டிங் மெஷினுக்கும் தத்துவார்த்த வரம்பு உள்ளது, எந்தவொரு கணினி நிரலும் தீர்க்க முடியாத ஒரு தர்க்கப் பிரச்சினையாவது இருப்பதற்கான ஆதாரத்தை இங்கே பார்ப்போம்.

எச், தி இம்பாசிபிள் கம்ப்யூட்டர் புரோகிராம் வரையறுத்தல்

ஒரு கணினி நிரல் P (i) ஐ ஒரு அறிவுறுத்தல் பட்டியலாக வரையறுக்கிறோம் P என்பது ஒரு உள்ளீட்டு i உடன் செயல்படுத்தப்படும் போது, ​​ஒரு வெளியீட்டை கொடுங்கள்.

உதாரணமாக,

நீங்கள் கொடுக்கும் இரண்டு எண்களை உள்ளீடுகளாக தொகுக்கும் ஒரு நிரல், மற்றும்,

மற்றொரு நிரலை - P_add - உள்ளீடாகப் பயன்படுத்தும் ஒரு நிரலாகும், மேலும் இந்த நிரலை மற்ற இரண்டு உள்ளீடுகளையும் கடந்து செல்கிறது. இது P_add (a, b) செய்வதைச் செய்து அதை இரட்டிப்பாக்குகிறது.

ஒரு நிரல் செயல்படுத்தப்படும்போது, ​​அது சிக்கி, எப்போதும் இயங்கக்கூடும், எதையும் ஒருபோதும் வெளியிடுவதில்லை, உதாரணமாக, அனைத்து இயற்கை எண்களின் கூட்டுத்தொகையைத் தொடரும் ஒரு நிரல் P_sum எப்போதும் இயங்குவதை முடிக்காமல் இயற்கையான எண்களை எப்போதும் சேர்த்துக் கொண்டே இருக்கும் (அதாவது, நிறுத்த) மற்றும் முடிவை வெளியிடுகிறது.

இப்போது அது ஒரு நிரல் H (P, i) உள்ளது என்று வைத்துக்கொள்வோம், இது P (i) நிரலின் P இன் அறிவுறுத்தல்களின் பட்டியலையும், P (i) இன் உள்ளீட்டையும், P (i) என்றால் 1 ஐ வெளியீடு செய்கிறது. பி (i) சிக்கி எப்போதும் இயங்கினால் 0 ஒரு கட்டத்தில் நிறுத்தவும். எளிமையாகச் சொல்வதென்றால்,

தர்க்க வழிமுறைகளின் பட்டியல் ஏன் எச் இருக்க முடியாது

ஆலன் டூரிங்கின் சான்றின் அடிப்படையில் ”கணக்கிடக்கூடிய எண்களில், Entscheidungsproblem” -1937 க்கு ஒரு விண்ணப்பத்துடன், H இருக்க முடியாது என்பதை நாங்கள் நிரூபிப்போம்.

எச் இருக்கின்றது என்ற அனுமானத்தின் அடிப்படையில், எச் (பி, பி) = 1 என்றால் மட்டுமே என்றென்றும் இயங்கும் ஒரு நிரல் எக்ஸ் (பி) ஐ உருவாக்குகிறோம், எச் (பி, பி) = 0 என்றால் மட்டுமே நிறுத்தப்படும். வேறுவிதமாகக் கூறினால்,

எக்ஸ் (ஐ) அதன் சொந்த வழிமுறைகளின் பட்டியலை எக்ஸ் ஒரு உள்ளீடாக வழங்குவதை இப்போது நாம் பரிசீலிக்கலாம்: எக்ஸ் (எக்ஸ்).

ஆகையால், எச் (எக்ஸ், எக்ஸ்) = 1 மற்றும் எக்ஸ் (எக்ஸ்) நிறுத்தப்பட்டால் மட்டுமே எச் (எக்ஸ், எக்ஸ்) = 0 என்றால் மட்டுமே எக்ஸ் (எக்ஸ்) எப்போதும் இயங்கும். வேறுவிதமாகக் கூறினால்,

எங்களுக்கு ஒரு முரண்பாடு உள்ளது! எச் இருத்தல் அபத்தமான முடிவுகளுக்கு இட்டுச் செல்வதால் எச் இருக்க முடியாது என்பதை ரெடக்டியோ விளம்பர அபத்தத்தால் காட்டியுள்ளோம்.

எனவே எந்தவொரு கணினி நிரலும் எந்தவொரு உள்ளீடும் கொடுக்கப்பட்டு நிரந்தரமாக இயங்குமா அல்லது இயங்குவதை முடிக்க முடியுமா என்பதை தீர்மானிக்கக்கூடிய கணினி நிரல் சாத்தியமற்றது. இருக்க முடியாத ஒரு தர்க்க சிக்கலைத் தீர்க்க குறைந்தபட்சம் ஒரு கணினி நிரல் உள்ளது.

குறிப்புகள், ஆலன் டூரிங். “கணக்கிடக்கூடிய எண்களில், Entscheidungsproblem க்கான பயன்பாட்டுடன்”. 1937.

நான் மேக்ஸ் க out ட், ரிலேடிவி.காமின் இணை நிறுவனர், நான் புதிதாக வடிவமைத்த வி.ஆர் ஹெட்செட், அதில் நான் குறியீடு மற்றும் வன்பொருளைத் திறந்தேன். Twitter @maxcoutte இல் என்னைப் பின்தொடரவும்.