`find` और `mkdir` की Turing completeness

अवलोकन

• केवल GNU के find और mkdir कमांड से यह साबित करने की कोशिश कि सिस्टम Turing complete है
• sed और awk कमांड के Turing complete होने के बारे में अच्छी तरह जाना जाता है, लेकिन find और mkdir की Turing completeness पर संदर्भ सामग्री नहीं मिलती
• यह प्रमाण उस सामान्य तकनीक का उपयोग करता है जिसमें Rule 110 चलाया जा सकने को दिखाया जाता है
• व्याख्या लूप, FizzBuzz, और Rule 110 के implementation के क्रम में की गई है

implementation

लूप बनाना

• नीचे दिया गया कोड recursive तरीके से directories बनाता है और infinite loop तैयार करता है

  mkdir x
  find x -execdir mkdir x/x \;
  

• find x x के नीचे की files को सूचीबद्ध करता है, और जब x सूचीबद्ध होता है तो x/x बनाया जाता है
• directory creation की depth सीमित करने के लिए -maxdepth option का उपयोग किया जा सकता है

  mkdir x
  find x -maxdepth 3 -execdir mkdir x/x \;
  

FizzBuzz

• find के -regex option से file names को filter करके, और इसे loop के साथ जोड़कर, FizzBuzz implement किया जाता है

  mkdir -p d/x
  find d/x -regextype posix-extended -regex 'd(/x){0,29}' -execdir mkdir x/x \;
  find d -regextype posix-extended \
  -regex 'd((/x){15})+' -printf "FizzBuzz\n" -o \
  -regex 'd((/x){5})+' -printf "Buzz\n" -o \
  -regex 'd((/x){3})+' -printf "Fizz\n" -o \
  -regex 'd(/x)+' -printf "%d\n"
  

Rule 110 implementation

• जब loop और conditional branching उपलब्ध हो जाएँ, तो arbitrary programs लिखना संभव हो जाता है
• इसे साबित करने के लिए Rule 110 implement किया गया है

  WIDTH=16
  ITER=15
  mkdir -p p/0/0/0/0/0/0/0/0/0/0/0/0/0/0/0/1
  O='(/?1)'
  Z='(/?[0p])'
  X='(/?[01p])'
  W0="($X{$WIDTH})"
  W1="($X$W0)"
  W2="($X$W1)"
  ZERO="($Z$Z$Z|$O$Z$Z|$O$O$O)"
  ONE="($O$O$Z|$O$Z$O|$Z$O$O|$Z$O$Z|$Z$Z$O)"
  find p -regextype posix-extended \
  -regex "$W1$W2{$ITER}" -fprint /dev/null \
  -o -regex "$W1$W2{0,$ITER}" \( -execdir mkdir 0/p 1/p \; -o -execdir mkdir 0/p/p 1/p/p \; \) \
  -o -regex "$W2*" -fprint /dev/null \
  -o -regex "$X*$ZERO$W0" -execdir mkdir 0/0 1/0 p/0 \; \
  -o -regex "$X*$ONE$W0" -execdir mkdir 0/1 1/1 p/1 \; \
  2> /dev/null
  find p -regextype posix-extended \
  -regex "p$W2{0,$ITER}" -execdir find p -mindepth $WIDTH -maxdepth $WIDTH \;
  

संभावित सवाल और जवाब

• क्या file path length limit की वजह से arbitrary size का automaton चलाना असंभव है?

  • mkdir एक निश्चित लंबाई से बड़े file path दिए जाने पर fail हो जाता है, लेकिन ऊपर का कोड इससे बचता है
  • find 30000 से अधिक लंबाई वाले paths पर भी काम करता है

• क्या ऊपर दिया गया कोड POSIX specification के अनुसार काम करने की गारंटी रखता है?

  • नहीं, क्योंकि directory search के दौरान files जुड़ने पर behavior निर्दिष्ट नहीं है
  • इस्तेमाल किए गए tool versions:

    find (GNU findutils) 4.8.0
    mkdir (GNU coreutils) 8.32
    Linux DESKTOP-5JU1LI7 5.15.153.1-microsoft-standard-WSL2 #1 SMP Fri Mar 29 23:14:13 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
    

GN⁺ की टिप्पणी

• केवल find और mkdir कमांड से Turing completeness साबित करने की कोशिश दिलचस्प है
• Rule 110 के implementation के जरिए इसे साबित करने का तरीका रचनात्मक है
• POSIX specification के अनुसार behavior की गारंटी नहीं है, लेकिन GNU tools में यह सफलतापूर्वक काम करता है
• समान प्रकृति वाले projects में sed और awk शामिल हैं