ओरेकल मौजूद है

या शटडाउन समस्या के लिए एक सामान्य एल्गोरिथ्म मौजूद हो सकता है।
लेकिन, हमेशा की तरह, बारीकियां हैं।
अगर दिलचस्पी है, तो मैं बिल्ली के लिए पूछना।

परिचय

1936 में, एलन ट्यूरिंग ने साबित किया कि कोई भी सामान्य एल्गोरिदम नहीं है जो अन्य एल्गोरिदम का विश्लेषण करता है और इंगित करता है कि कार्यक्रम लटका होगा या नहीं।

मैं तुरंत सभी ई को डॉट करना चाहूंगा और मेरे द्वारा उपयोग की जाने वाली शर्तों का वर्णन करूंगा ताकि कोई समझ न आए।

कार्यक्रम जमा देता है - एल्गोरिदम समय की एक प्रभावी मात्रा में काम करेगा, भले ही आदेशों के निष्पादन की गति और समानांतर कंप्यूटिंग की परवाह किए बिना। कोई फर्क नहीं पड़ता कि हम कितने बड़े सुपर कंप्यूटर हैं, एल्गोरिथ्म हमेशा अनंत समय तक चलेगा।

एक कार्यक्रम को एक सीमित समय में निष्पादित करना - किसी भी मशीन पर एल्गोरिथ्म इसकी गणना को समाप्त कर देगा चाहे वे कितना भी बड़ा हो। उदाहरण के लिए, यदि कोई एल्गोरिथम 300 मिलियन वर्ष चलता है, तो इसका मतलब यह नहीं है कि यह लटका हुआ है, इसे वर्तमान संसाधनों पर 300 मिलियन वर्ष चलाने की आवश्यकता है और यह हमेशा समाप्त होता है।

अब आप जारी रख सकते हैं।

ट्यूरिंग के प्रमाण को निम्नानुसार वर्णित किया जा सकता है: इनपुट पर एक निश्चित ओरेकल एस (एल्गोरिथ्म) है जिसमें एल्गोरिदम एन और इनपुट डेटा एक्स का विवरण प्रदान किया गया है। प्रोग्राम बंद हो जाता है और 1 रिटर्न होता है यदि एल्गोरिदम एन बंद नहीं करता है, तो इनपुट पर एक्स प्राप्त करना।

प्रोग्राम अन्यथा बंद नहीं होता है, अगर एल्गोरिथ्म एन इनपुट एक्स प्राप्त करके बंद हो जाता है। यदि हम अपने विवरण को अपने ओरेकल को खिलाते हैं, तो एक विरोधाभास होगा और एल्गोरिथ्म खुद ही विरोधाभास करेगा। विवरण विकी पर पाया जा सकता है।

ओरेकल मौजूद है लेकिन उसे एक भाई की जरूरत है

आप इस तथ्य से भ्रमित नहीं हैं कि ओरेकल को फ्रीज करना चाहिए यदि एल्गोरिथ्म जो विश्लेषण करता है वह बंद हो जाता है, मैं इस तथ्य से सीधे भ्रमित हूं, इसलिए प्रमाण के लिए हम ओरेकल के निष्कर्ष को थोड़ा सही करेंगे। दैवज्ञ को 1 या 0. वापस आने दें, इसलिए, आप पूछते हैं, अगर हम छद्म कोड पर लिखते हैं तो कुछ भी नहीं बदला है:

If ((N)==0){
While (true){
}
} 

, , :
, , :

S1 0 1 0 1 , .

S2 0 1 , . 1 1 , 0 . 0 , 1 .

, . .

, , . , , .

, . , .

:

If ((N)==0){
While(true){
}
}

If ((N)==0){
While(true){
}
}

.

.
, . , . - , .

, , . , .