algorithm ब्रेनफैक प्रोग्राम में अनन्त लूप का पता लगा रहा है




interpreter infinite-loop (8)

मैंने MATLAB स्क्रिप्ट भाषा में एक साधारण ब्रेनफुक इंटरप्रेटर लिखा है इसे निष्पादित करने के लिए यादृच्छिक बीएफ कार्यक्रमों को खिलाया जाता है (आनुवंशिक एल्गोरिथम प्रोजेक्ट के भाग के रूप में)। मैं जो समस्या का सामना कर रहा हूं वह है, इस कार्यक्रम में बहुत अधिक मामलों में अनंत लूप होने का पता चलता है, और इसलिए जीए बिंदु पर फंस जाता है।
इसलिए, मुझे अनन्त लूप का पता लगाने के लिए एक तंत्र की आवश्यकता है और बीएफ में उस कोड को निष्पादित करने से बचने की आवश्यकता है।
एक स्पष्ट (तुच्छ) मामला है जब मेरे पास है

[]

मैं इसका पता लगा सकता हूं और उस प्रोग्राम को चलाने के लिए इंकार कर सकता हूं।
गैर-मामूली मामलों के लिए, मुझे पता चला कि मूल विचार यह है कि यह निर्धारित करने के लिए कि कैसे लूप का एक चलना वर्तमान सेल को बदलता है। यदि परिवर्तन नकारात्मक है, हम अंततः 0 तक पहुंचने जा रहे हैं, इसलिए यह एक सीमित लूप है। अन्यथा, यदि परिवर्तन गैर-नकारात्मक है, तो यह एक अनंत लूप है।
इसे लागू करना एक लूप के मामले में आसान है, लेकिन नेस्टेड लूप के साथ यह बहुत जटिल हो जाता है। उदाहरण के लिए, (निम्न में से (1) सेल 1, आदि की सामग्री को संदर्भित करता है)

++++ Put 4 in 1st cell (1)
>+++ Put 3 in (2)
<[   While( (1) is non zero)
    --   Decrease (1) by 2
    >[   While( (2) is non zero)
        -    Decrement (2)
        <+   Increment (1) 
    >]   
    (2) would be 0 at this point
    +++  Increase (2) by 3 making (2) = 3
<]   (1) was decreased by 2 and then increased by 3, so net effect is increment

और इसलिए कोड चालू रहता है + की संख्या के एक भोले-भरी जांच और 'सेल 1 पर किए गए', हालांकि, यह कहेंगे कि- की संख्या अधिक है, इसलिए अनंत लूप का पता नहीं लगाएगा
क्या कोई भी असीमित छोरों का पता लगाने के लिए एक अच्छा एल्गोरिथ्म के बारे में सोच सकता है, जिसे बीएफ में मनमाना संख्याओं की लूपों की मनमानी आंतों को दिया गया है?

संपादित करें: मुझे पता है कि थकावट समस्या सामान्य रूप से असमर्थ है, लेकिन मुझे यकीन नहीं था कि क्या विशेष केस अपवाद मौजूद नहीं था। जैसे, शायद Matlab एक सुपर ट्यूरिंग मशीन के रूप में काम कर सकता है जो बीएफ प्रोग्राम को रोकने का निर्धारण कर सकता है। मैं बहुत गलत हो सकता है, लेकिन यदि हां, तो मैं यह जानना चाहूंगा कि कैसे और क्यों

दूसरे संपादन: मैंने लिखा है कि अनंत लूप डिटेक्टर होने के लिए मैं क्या कह रहा हूं। यह शायद कुछ बढ़त के मामलों को याद करता है (या कम शायद, किसी तरह मिस्टर ट्यूरिंग के चंगुल से बच निकलते हैं), लेकिन मेरे लिए अभी के लिए काम करना लगता है। स्यूडोकोड रूप में, यह यहां जाता है:

subroutine bfexec(bfprogram)
begin
    Looping through the bfprogram,
        If(current character is '[')
            Find the corresponding ']'
            Store the code between the two brackets in, say, 'subprog'
            Save the value of the current cell in oldval
            Call bfexec recursively with subprog
            Save the value of the current cell in newval
            If(newval >= oldval)
                Raise an 'infinite loop' error and exit
            EndIf
        /* Do other character's processings */
        EndIf
    EndLoop
end

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

अब मान लें कि आप एक नया प्रोग्राम बनाने के लिए चेकर प्रोग्राम का विस्तार करते हैं। यह नया प्रोग्राम तत्काल बाहर निकल जाता है जब इसकी इनपुट अनिश्चित रूप से छोरती है, और हमेशा के लिए छोरता है जब इसकी इनपुट किसी बिंदु पर निकलती है।

यदि आप अपने आप में इस नए प्रोग्राम को इनपुट करते हैं, तो परिणाम क्या होंगे?

अगर इस कार्यक्रम को हमेशा चलाए जाने के लिए छोर जाता है, तो अपनी स्वयं की परिभाषा के अनुसार इसे तत्काल बाहर निकल जाना चाहिए, जब वह स्वयं इनपुट के रूप में चलाया जाता है। और इसके विपरीत। चेकर कार्यक्रम संभवत: मौजूद नहीं हो सकता, क्योंकि इसके अस्तित्व में एक विरोधाभास है।

जैसा कि पहले उल्लेख किया गया है, आप अनिवार्य रूप से प्रसिद्ध थकावट समस्या को पुन: विश्राम कर रहे हैं: http://en.wikipedia.org/wiki/Halting_problem

ईडी। मैं यह स्पष्ट करना चाहता हूं कि उपरोक्त विरूपण मेरा अपना नहीं है, लेकिन अनिवार्य रूप से 1 9 36 में एल्न ट्यूरिंग ने प्रसिद्ध विरूपण किया।



राज्य में बीएफ अक्षर का एक सरणी है

अगर मैं आप थे, तो मैं हर एक "" "(या एक बार रैंड (1, 100)"] "* पर बीएफ इंटरप्रीटर राज्य का एक हेश लेता हूं और यह दावा करता हूं कि हैश का सेट अद्वितीय है

दूसरा (या अधिक) समय मैं एक निश्चित हैश को देखता हूं, मैं पूरे राज्य को अलग कर देता हूं

तीसरा (या अधिक) समय मैं एक निश्चित हैश को देखता हूं, मैं पूरे राज्य को सहेजे गए किसी के साथ तुलना करता हूं और अगर कोई मैच होता है, तो मैंने छोड़ दिया

प्रत्येक इनपुट कमांड ('।', IIRC) पर मैं अपने सहेजे हुए राज्यों और हैशों की सूची को रीसेट करता हूं।

ऑप्टिमाइज़ेशन केवल उस राज्य का हिस्सा है जो छू गया था।

मैंने इस समस्या को हल नहीं किया है - मैं प्रोग्राम चलाते समय अनंत लूप का पता लगा रहा हूं।

* रैंड को चेक को लूप अवधि से अलग करना है


यह स्थगित समस्या नहीं है, हालांकि, यह अभी भी एक सीमित सेल मशीन में 1000 सेल बीएफ मशीन के रूप में भी नहीं रोक पाया है।

इस कार्यक्रम पर विचार करें:

+[->[>]+<[-<]+]

यह कार्यक्रम तब तक दोहराना नहीं होगा जब तक कि यह पूरी स्मृति भर न हो जाए जिसके लिए सिर्फ 1000 कोशिकाओं में लगभग 10 ^ 300 वर्ष लगेगा।


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

Fermat के अंतिम प्रमेय पर विचार करें यह एक ऐसा प्रोग्राम बनाने में आसान है जो प्रत्येक नंबर (या इस मामले में 3 नंबर) के माध्यम से दोहराता है, और पता लगाता है कि क्या यह प्रमेय के लिए एक काउंटरएक्साउंड है यदि ऐसा है तो यह रोकता है, अन्यथा यह जारी है।

इसलिए यदि आपके पास एक अनंत लूप डिटेक्टर है, तो यह इस प्रमेय को साबित करने में सक्षम होना चाहिए, और कई अन्य (शायद अन्य सभी, यदि वे counterexamples के लिए खोज करने के लिए कम हो सकते हैं।)

सामान्य तौर पर, किसी भी प्रोग्राम में संख्याओं के जरिए चलना शामिल होता है और केवल कुछ स्थिति में रोकना पड़ता है, एक सामान्य प्रमेय प्रवक्ता को यह साबित करने की आवश्यकता होती है कि उस स्थिति को कभी भी पूरा नहीं किया जा सकता है। और यह पाशन का सबसे सरल मामला है।


जैसा कि पहले ही बताया गया है कि यह हलचल समस्या है। लेकिन आपके मामले में कोई हल हो सकता है: हल करने की समस्या पर विचार हो रहा है ट्यूरिंग मशीन के बारे में, जिसमें असीमित स्मृति है

अगर आप जानते हैं कि आपके पास स्मृति की ऊपरी सीमा है (जैसे आप जानते हैं कि आप 10 मेमोरी सेल्स का उपयोग नहीं करते हैं), तो आप अपने प्रोग्राम को निष्पादित कर सकते हैं और उसे रोक सकते हैं। विचार यह है कि अभिकलन अंतरिक्ष में गणना समय सीमा (जैसा कि आप एक कदम से एक से अधिक कक्ष लिख सकते हैं)। जैसे ही आप अलग-अलग मेमोरी कॉन्फ़िगरेशन कर सकते हैं उतने कदम उठाए जाने के बाद, आप तोड़ सकते हैं अगर आपके पास 3 कोशिकाएं हैं, तो 256 स्थितियों के साथ, आपके पास अधिकतम 3 ^ 256 विभिन्न राज्य हो सकते हैं, और इसलिए आप कई चरणों का पालन करने के बाद रोक सकते हैं। लेकिन सावधान रहें, अनुदेश संकेतक और रजिस्टरों जैसे निहित कोशिकाएं हैं। यदि आप प्रत्येक राज्य कॉन्फ़िगरेशन को सहेजते हैं और जैसे ही आप पहले से ही पता लगाते हैं, तो आप इसे भी कम करते हैं, आपके पास एक बुद्धिमत्ता लूप है। यह दृष्टिकोण निश्चित रूप से चलाने के समय में बेहतर है, लेकिन इसके लिए अधिक जगह की आवश्यकता है (यहां यह कॉन्फ़िगरेशन हैश के लिए उपयुक्त हो सकता है)।


जब मैं रेखीय आनुवंशिक प्रोग्रामिंग का इस्तेमाल करता था, तो मैंने निर्देशों की संख्या के लिए सिर्फ एक ऊपरी बाधा का इस्तेमाल किया था, एक एकल कार्यक्रम को अपने जीवनकाल में करने की अनुमति दी गई थी। मुझे लगता है कि यह दो तरीकों से समझदार है: मैं वास्तव में किसी भी समस्या को हल नहीं कर सकता, और प्रोग्राम जो गणना करने में अधिक समय लेते हैं वैसे भी अधिक समय पाने के योग्य नहीं हैं।


मेरे सिर के ऊपर से (और मैं गलत हो सकता है), मुझे लगता होगा कि कार्यक्रम को वास्तव में निष्पादित किए बिना एक प्रोग्राम की असीमित लूप है या नहीं, यह पता लगाने में थोड़ा मुश्किल होगा।

के रूप में कार्यक्रम के भाग के सशर्त निष्पादन कार्यक्रम के निष्पादन राज्य पर निर्भर करता है, कार्यक्रम के वास्तव में वास्तव में निष्पादित किए बिना प्रोग्राम की विशेष स्थिति को जानना मुश्किल होगा।

यदि आप की आवश्यकता नहीं है कि एक प्रोग्राम को अनंत लूप के साथ निष्पादित किया जाए, तो आप "निर्देशों को निष्पादित" काउंटर की कोशिश कर सकते हैं, और केवल निर्देशों की एक सीमित संख्या को निष्पादित कर सकते हैं। इस तरह, यदि एक प्रोग्राम में अनंत लूप है, तो इंटरप्रिटर उस प्रोग्राम को समाप्त कर सकता है जो अनंत लूप में फंस गया है।





brainfuck