क्या एक हाइपरग्राफ एक नोडेटर्मिनिस्टिक ट्यूरिंग मशीन का प्रतिनिधित्व कर सकता है?

Question

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

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

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

आंशिक उत्तर:

• ओपनकॉग लोगों के पास विभिन्न कंप्यूटिंग मॉडल में हाइपरग्राफ कैसे फिट होते हैं, इस बारे में एक tantalyzing चर्चा थी; इस जाहिरा तौर पर HypergraphDB पैकेज के विकास से संबंधित था: http://markmail.org/message/5oiv3qmoexvo4v5j
• से अधिक MathOverflow पर, वहाँ एक सवाल पर चर्चा क्या hypergraphs है कर सकते हैं करते हैं - ट्यूरिंग का कोई जिक्र नहीं अभी तक है, लेकिन मैं के बारे में जोड़ने के लिए कर रहा हूँ: https://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs
• यदि कोई हाइपरग्राफ नोडेटर्मेनिस्टिक ट्यूरिंग मशीन का प्रतिनिधित्व कर सकता है, तो मुझे लगता है कि भारित किनारों वाला एक हाइपरग्राफ संभाव्य ट्यूरिंग मशीन के बराबर होगा। http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

Answer 1

एक hypergraph केवल ग्राफ़ G=(V,E) जहां V कोने का सेट (नोड) और EV की Powerset के एक सबसेट है है। यह एक डेटा संरचना है।

तो एक सामान्य ग्राफ केवल रैंक 2 के साथ एक हाइपरग्राफ है। (यानी ई में प्रत्येक सेट में दो दो अक्षर होते हैं)। एक निर्देशित हाइपरग्राफ जोड़े (X,Y) किनारों के रूप में उपयोग करता है जहां X और Y सेट हैं।

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

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

states = {1,2,3} 
symbols = {a,b,c} 
moves = L, R 
delta = { (1,a) -> (1,b,R) 
      (1,b) -> (2,c,L) 
      ... 
} 

इसलिए यदि आप एक ग्राफ चाहते थे तो आपको पहले वी = राज्य यू प्रतीक यू चाल की आवश्यकता होगी। स्पष्ट रूप से उन्हें अलग-अलग सेट होने की आवश्यकता है। के रूप में {1, एक} -> {1, बी, आर} परिभाषा से {एक, 1} के बराबर है -> {ख, आर, 1} आदि

states = {1,2,3} 
symbols = {a,b,c} 
moves = L, R 
V = {1,2,3,a,b,c,L,R} 
E = { ({1,a},{1,b,R}) 
     ({b,1},{L,2,c}) 
     ... 
} 
turing-hypergraph = (V,E) 

कि मैंने पहले उल्लेख किया है, देखने के लिए ग्राफ फिर से लिखना या शब्द फिर से लिखना।