क्या कोई नियम 110 को सबसे सरल तरीके से समझा सकता है?

Question

मैं चारों ओर the Wikipedia article या the answer here क्या कहते हैं मेरे सिर लपेटो नहीं कर सकते। क्या कोई साधारण नियमों में नियम 110 की व्याख्या कर सकता है? यह ट्यूरिंग पूर्णता की गारंटी कैसे देता है?

Answer 1

मुझे विस्तार से जाना होगा: मुझे नहीं लगता कि आप इस सबूत के बारे में अधिक जानकारी चाहते हैं जो लेख में पहले से ही जटिल है, हालांकि यह स्पष्ट रूप से कई विवरणों को छोड़ देता है।

से article you cite के शब्दों में:। "एक प्राथमिक सेलुलर automaton में, नियमों का एक सरल सेट के अनुसार 0 और 1 के विकसित की एक आयामी पैटर्न पैटर्न में एक बिंदु हो जाएगा चाहे 0 या 1 में निर्भर करता है नई पीढ़ी इसके वर्तमान पड़ोसियों के साथ-साथ इसके दो पड़ोसियों के साथ भी है। नियम 110 automaton के नियमों का निम्नलिखित सेट है ... " (wikipedia table देखें)

प्रारंभिक बिंदु, जिसे आप देख सकते हैं डेटा के रूप में, लेकिन कोड के प्रतिनिधित्व के रूप में लिया जा सकता है (ट्यूरिंग-पूर्णता के किसी भी प्रमाण के लिए कोड के रूप में डेटा का प्रतिनिधित्व करना आवश्यक है; यह ट्यूरिंग के मूल परिणामों पर वापस जाता है), 0 और 1 का अनुक्रम होता है, लेकिन अक्सर नहीं जरूरी है, और ly, केवल 0 युक्त कोशिकाओं द्वारा दोनों तरफ घिरा हुआ है। नियम 110 दिखाता है कि यह अनुक्रम कैसे विकसित होता है। उदाहरण के लिए, यदि एक पंक्ति में 3 1 का पैटर्न है, तो मध्य 1 अगली पंक्ति में "मर जाएगा" (0 में बदल जाएगा)। इसके दो पड़ोसियों के साथ क्या होता है इस पर निर्भर करता है कि पैटर्न उनके आगे कैसे फैलता है। आपके द्वारा देखे जाने वाले त्रिभुज चित्र मूल राज्य से automaton के विकास का एक ग्राफिकल प्रतिनिधित्व है, 1 को काले और 0 सफेद के रूप में कोडित करते हैं और ऊपर से नीचे तक विकास का प्रतिनिधित्व करते हैं। शुरुआती राज्य अक्सर यह दिखाने के लिए बहुत छोटा होता है कि सरल प्रारंभिक राज्यों से कितने जटिल पैटर्न विकसित हो सकते हैं।

ट्यूरिंग पूर्णता के सबूत की दो असामान्य विशेषताएं ये हैं कि, सबसे पहले, यह बहुत ही असंभव लगता है कि आपका बहुत ही सरल नियम आपकी पसंदीदा प्रोग्रामिंग भाषा कर सकता है, और दूसरा, जो पहले तथ्य को कम अद्भुत बनाता है, यह है कि सबूत के लिए एक अनगिनत लंबी दोहराने वाली पृष्ठभूमि की आवश्यकता होती है जिस पर अपने जादू का काम करना है। मैं इसके बारे में मूल रूप से बेईमानी कुछ भी नहीं देख सकता; मूल रूप से ट्यूरिंग के रूप में संभावित रूप से अनंत या अर्ध-अनंत खाली टेप मानने से कहीं ज्यादा नहीं।

सबूत को सही ढंग से समझने के लिए आपको प्रारंभिक पैटर्न में डेटा (और बाद में, कोड) एन्कोड किए जाने के साथ पकड़ने की आवश्यकता होगी, और ऐसा लगता है कि चक्रीय टैग सिस्टम के साथ परिचितता बहुत मददगार होगी। मैं उनको समझाने वाला व्यक्ति नहीं हूं।

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

तुम भी मिल सकता है talk page जानकारीपूर्ण (आप बिंदु लोभी नहीं में अकेले नहीं हैं, प्रविष्टि शुरुआत "चित्र मेरे लिए कोई मतलब नहीं है .." देखें)।

Answer 2

एक संक्षिप्त, आम आदमी की दृष्टि स्पष्टीकरण पर मेरे प्रयास: 1 है और 0 है की एक और पैटर्न में से 1 है और 0 है एक परिमित पैटर्न बदलने के लिए एक नियम:

• नियम 110 एक प्राथमिक सेलुलर automaton है।
• जब नियम 110 कुछ इनपुट बिट अनुक्रमों पर लागू होता है, तो इनपुट बिट्स में पाए गए उप-अनुक्रमों के आधार पर पैटर्न उभरते हैं। पर्याप्त पुनरावृत्तियों को देखते हुए, निम्नलिखित हो सकता है:
  • मूल उप-अनुक्रम मूल इनपुट के समान स्थान पर दिखाई देता है।
  • मूल उप-अनुक्रम संरक्षित है लेकिन बिटफील्ड में एक अलग स्थान पर 'चाल' है।
  • एक दूसरे की ओर बढ़ते हुए दो उप-अनुक्रम एक-दूसरे से बातचीत करते हैं और 'एक दूसरे से गुज़रते हैं'।
  • दो उप-अनुक्रम एक नया उप-अनुक्रम बनाने के लिए गठबंधन करते हैं।
• विभिन्न उप-अनुक्रमों को '1', '0', 'घड़ी पल्स' या 'उत्पादन नियम' जैसे प्रतीकात्मक अर्थ दिया जा सकता है जो चक्रीय टैग सिस्टम के तत्वों से मेल खाते हैं।
• एक सावधानी से निर्मित इनपुट बिटफील्ड पर नियम 110 के कई पुनरावृत्तियों के साथ, उप-अनुक्रमों की बातचीत एक चक्रीय टैग सिस्टम के व्यवहार को अनुकरण करती है।
• एक चक्रीय टैग सिस्टम का उपयोग सार्वभौमिक ट्यूरिंग मशीन को अनुकरण करने के लिए किया जा सकता है। इस प्रकार एक चक्रीय टैग सिस्टम ट्यूरिंग-पूर्ण है।
• चूंकि नियम 110 एक चक्रीय टैग सिस्टम अनुकरण कर सकता है, यह भी ट्यूरिंग-पूर्ण है।

Answer 3

1 9 70 में जॉन कॉन्वे ने Game of Life का आविष्कार किया है।

तब से, मुझे लगता है कि लगभग हर प्रोग्रामर ने इसके कार्यान्वयन को लिखने की कोशिश की - मैंने निश्चित रूप से बहुत समय पहले किया था, और यह बहुत मजेदार था।

यह गेम वास्तव में cellular automaton है, जो अनंत 2-आयामी विमान में कोशिकाओं की पीढ़ियों के बीच सरल नियम निर्धारित करता है। उदाहरण के लिए, यदि वर्तमान पीढ़ी के सेल में 2 से कम पड़ोसी जीवित हैं (बिट मान 1), तो यह अगली पीढ़ी अकेलेपन में मरना चाहिए। यदि इसमें 3 से अधिक पड़ोसी जीवित हैं, तो इसे अतिसंवेदनशीलता से मरना चाहिए। यदि खाली (बिट मान 0, या मृत) सेल में बिल्कुल 3 पड़ोसी हैं, तो यह पैदा होने का कारण बन जाएगा (1 बनें)।

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

अब 110 नियम क्या है। सीधे शब्दों में कहें, नियम 110 जीवन के खेल का एक आयामी भिन्नता है।

110 बाइनरी स्ट्रिंग 01101110 का सिर्फ एक दशमलव संख्या प्रतिनिधित्व जो कैसे कोशिकाओं की वर्तमान पीढ़ी (बिट) के शासन प्रणाली की संक्षिप्त रूप है translated into next one, अकेलापन या भीड़भाड़ से मर कोशिकाओं के खेल के जीवन के शासन प्रणाली के समान हो जाएगा और वास्तव में तीन पड़ोसी होने का जन्म हुआ।

जीवन के खेल की तरह, यह साबित हुआ है कि नियम 110 ट्यूरिंग-पूर्ण है। आप अपने प्रोग्राम के रूप में प्रारंभिक कक्ष (बिट्स) संयोजन का उपयोग करके मनमाने ढंग से जटिल एल्गोरिदम को एन्कोड कर सकते हैं, और परिणामस्वरूप अंतिम बिट संयोजन।

Answer 4

अजगर में एक कार्यान्वयन:

(सलाह दी: वास्तविक अजगर प्रोग्रामर इस के लिए आप को मार डालेंगे)

import time 

seed = raw_input("Feed me a string! (At least 3 characters long please)\n>") 

lastline = '>' 
iterator = 0 

while (iterator<len(seed)): 
    temp = (ord(seed[iterator]))%2 
    if (temp == 1): 
     lastline += '#' 
    else: 
     lastline += ' ' 
    iterator += 1 

stop = 0 
while (stop != 1): #Keep printing as long as CTRL-C isn't pressed 
    #dummy = raw_input(lastline) 
    print lastline 
    iterator = 0 
    nextline = '>' 


    while (iterator<len(seed)): #Convert entire string 

     if (len(seed) < 3): # if wrong 
      print "You had ONE JOB!" 
      stop = 1 

     elif (iterator == 0): # if at start 
      if (lastline[1] == ' '): 
       nextline += ' ' 
      else: 
       nextline += '#' 

     elif (iterator+1 == len(seed)): # if at end 
      if (lastline[iterator+1] == ' '): 
       nextline += ' ' 
      else: 
       nextline += '#' 

     else: #if in middle 
      if (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #111 
       nextline += ' ' 
      elif (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #110 
       nextline += '#' 
      elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #101 
       nextline += '#' 
      elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == ' '): #100 
       nextline += ' ' 
      elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #011 
       nextline += '#' 
      elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #010 
       nextline += '#' 
      elif (lastline[iterator] == ' ' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #001 
       nextline += '#' 
      else: # (lastline[iterator-1] == ' ' and lastline[iterator] == ' ' and lastline[iterator+1] == ' '): #000 
       nextline += ' ' 

     iterator += 1 

    lastline = nextline 
    time.sleep(0.02)