शुद्ध SQL ट्यूरिंग मशीन

कुछ महीने पहले मैंने एक पोस्ट पढ़ी जिसमें आदरणीय kususha ने MySQL और संग्रहीत प्रक्रियाओं का उपयोग करके ट्यूरिंग मशीन एमुलेटर लिखा था। संग्रहित प्रक्रियाओं का उपयोग किए बिना, लेख ने शुद्ध SQL में ट्यूरिंग मशीन बनाने के विचार को प्रोत्साहन दिया। कार्यान्वयन के लिए, परिचित और प्रिय फायरबर्ड संस्करण 2.1 का उपयोग किया गया था।



नंगे एसक्यूएल पर ट्यूरिंग मशीन बनाते समय दो मूलभूत समस्याएं हैं:

• 1) मशीन के टेप को संशोधित और जोड़ा जा सकता है, जिसके लिए एक ही डिजाइन में INSERT और UPDATE स्टेटमेंट की आवश्यकता होती है;
• 2) ट्यूरिंग मशीन के लिए कम से कम एक राज्य चर की आवश्यकता होती है। नियमित एसक्यूएल (डीएमएल) क्वेरीज़ कम से कम फायरबर्ड में इंटरमीडिएट चर को स्टोर नहीं कर सकती हैं।

हालाँकि, मैं इन सीमाओं को पाने में कामयाब रहा।



शुरू करने के लिए, मैंने एक नियमित संग्रहित प्रक्रिया पर ट्यूरिंग मशीन लिखी। मुझे नहीं पता कि क्यूशा ने पुनरावृत्ति का उपयोग क्यों किया, मैंने इसे एक नियमित लूप में और दोनों तरफ एक अंतहीन रिबन पर किया। उस कोड में कुछ भी उल्लेखनीय नहीं है, इसलिए मैंने तुरंत इसे नंगे SQL पर लागू करना शुरू कर दिया।



Firebird 2.1 में पहली समस्या को हल करने के लिए, पहले से ही दो निर्माण हैं: MERGE और UPDATE OR INSERT।

पहले तो मैंने दूसरे का उपयोग करने की योजना बनाई, लेकिन इसकी मदद से आप केवल 1 रिकॉर्ड को संशोधित या सम्मिलित कर सकते हैं। MERGE आपको एक मनमाना चयन के साथ "गोंद" करने की अनुमति देता है।



प्रयोगों की एक श्रृंखला के बाद राज्यों को संग्रहीत करने के लिए, पुनरावर्ती प्रश्नों का उपयोग करने का निर्णय लिया गया, जो संस्करण 2.1 में भी दिखाई दिया।



कार्यक्रम और टेप को संग्रहीत करने के लिए, मूल पोस्ट के समान एक टेबल संरचना का उपयोग किया गया था।



यहाँ मैं के साथ समाप्त हो गया है:

MERGE INTO ribbon r USING ( WITH RECURSIVE data AS ( SELECT 0 AS state, 1 AS pos, (SELECT sinput FROM ribbon WHERE id = 1) AS val FROM RDB$DATABASE UNION ALL SELECT p.out_state AS STATE, CASE WHEN p.actions = '<' THEN data.pos - 1 WHEN p.actions = '>' THEN data.pos + 1 ELSE data.pos END AS pos, CASE WHEN p.actions = '<' THEN COALESCE((SELECT sinput FROM ribbon WHERE id = (data.pos - 1)), ' ') WHEN p.actions = '>' THEN COALESCE((SELECT sinput FROM ribbon WHERE id = (data.pos + 1)), ' ') ELSE p.actions END AS val FROM program p JOIN data ON data.state = p.in_state WHERE p.sread = COALESCE((SELECT sinput FROM ribbon WHERE id = data.pos), ' ') AND p.actions != '#' ) SELECT * FROM data ) data ON data.pos = r.id WHEN MATCHED THEN UPDATE SET sinput = data.val WHEN NOT MATCHED THEN INSERT (id, sinput) VALUES (data.pos, data.val)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

गणना की गई राज्य फ़ील्ड में हम राज्य को स्टोर करते हैं, पॉस टेप पर स्थिति है।

"आरडीबी $ डटैबेस्ट" निर्माण फायरबर्ड की एक ऐसी "विशेषता" है जिसका उपयोग तब किया जाता है जब आपको किसी भी तालिका के बिना एकल पंक्ति चयन बनाने की आवश्यकता होती है।

इस प्रकार, हम मान सकते हैं कि फायरबर्ड 2.1 कार्यान्वयन में डीएमएल एसक्यूएल को ट्यूरिंग-पूर्ण प्रोग्रामिंग भाषा माना जा सकता है। सैद्धांतिक रूप से, ऐसी क्वेरी किसी भी DBMS पर की जा सकती है जो पुनरावर्ती प्रश्नों का समर्थन करता है और MERGE जैसे निर्माण करता है, सिंटैक्स में अंतर को ध्यान में रखते हुए।

एक आफ्टरवर्ड के बजाय

प्रारंभ में, यह जनरेटर उर्फ ​​SEQUENCE में राज्य को संग्रहीत करने की योजना बनाई गई थी। हालांकि, मैं इस तरह के अनुरोध को लिखने में सक्षम नहीं था - टेप के लिए नए डेटा का एक स्रोत ताकि यह कार्यक्रम और टेप के चारों ओर आगे और पीछे चला सके। फिर भी, इस प्रयोग ने जनरेटर के साथ काम करते समय कई दिलचस्प समाधान खोजना संभव बना दिया:

• 1) WHERE सेक्शन में जनरेटर को स्थानांतरित करने के लिए, आप डिज़ाइन का उपयोग कर सकते हैं
  
  

   GEN_ID(POS, <increment>)=GEN_ID(POS, 0)
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  किसी भी वृद्धि मूल्य के लिए, यह सच है;
• 2) जनरेटर को शून्य पर रीसेट किया जा सकता है
  
  

   GEN_ID(POS, -GEN_ID(POS, 0))
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  1 के साथ एक साथ उपयोग करना) WHERE क्लॉज में जनरेटर को रीसेट करना संभव है।

मुझे कहना होगा कि पुनरावर्ती फायरबर्ड प्रश्नों का नेस्टिंग 1024 स्तरों तक सीमित है, इसलिए यदि मैं अभी भी जनरेटर पर ऐसा करने का प्रबंधन करता हूं, तो प्रतिबंध हटा दिया जाएगा।

तालिका संरचना

 CREATE TABLE PROGRAM ( IN_STATE INTEGER NOT NULL, SREAD CHAR(1) NOT NULL, ACTIONS CHAR(1) NOT NULL, OUT_STATE INTEGER NOT NULL ); CREATE TABLE RIBBON ( SINPUT CHAR(1) NOT NULL, ID INTEGER NOT NULL );
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

सूत्रों का कहना है

फायरबर्ड 2.1 रिलीज नोट्स