`find` और `mkdir` की Turing पूर्णता

• केवल GNU के find और mkdir से भी directory creation और traversal order का उपयोग करके loop और state transition बनाए जा सकते हैं, इसलिए साधारण file utility का यह संयोजन एक computation model बन जाता है
• प्रमाण tag system के implementation के जरिए दिया गया है, और पहले version का Rule 110-आधारित प्रमाण infinite repetition को handle न कर पाने की समस्या के कारण संशोधित किया गया
• बेसिक loop find x -execdir mkdir x/x \\; इस तरह काम करता है कि वह लगातार नई directories खोजता रहता है, और -regex जोड़ने पर FizzBuzz जैसी conditional branching भी संभव हो जाती है
• tag system implementation state को file path के रूप में व्यक्त करता है और back-reference की मदद से शुरुआती m characters हटाने के बाद बचे हिस्से की copy बनाता है
• POSIX, search के दौरान directory में file जुड़ने पर होने वाले व्यवहार को unspecified मानता है, इसलिए निष्कर्ष GNU tools के देखे गए व्यवहार और दिए गए environment पर निर्भर है

---

GNU find और mkdir से computation model बनाना

• उद्देश्य यह दिखाना है कि केवल GNU के find और mkdir commands वाले system की Turing पूर्णता सिद्ध की जा सकती है
• प्रमाण tag system को implement करने के तरीके से आगे बढ़ता है
• पूरा flow loop निर्माण, FizzBuzz, और फिर tag system implementation के क्रम में चलता है
• 2 अगस्त 2024 के पहले version में Rule 110-आधारित प्रमाण की त्रुटि सुधारी गई, और मौजूदा version को tag system implementation में बदला गया
  • पहले version में infinite संख्या के repetitions को handle न कर पाने की समस्या थी
• संबंधित शोधपत्र Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation को FUN with Algorithms 2026 में स्वीकार किया गया है

directory creation से बनने वाला loop

• नीचे दिया गया code recursively directories बनाता है और infinite loop में चला जाता है

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

• find x x के नीचे की files को सूचीबद्ध करता है, और इसमें x स्वयं भी शामिल होता है
• जब x सूचीबद्ध होता है, तो mkdir x/x बनाता है, और find की अगली iteration में नया बना x/x भी शामिल हो जाता है
• यह प्रक्रिया दोहरती रहती है और x/x/x, x/x/x/x जैसे path लगातार बनते जाते हैं
• -maxdepth option का उपयोग करके creation depth सीमित की जा सकती है

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

• यह उदाहरण x/x/x/x/x बनाने के बाद समाप्त हो जाता है

find -regex से implement किया गया FizzBuzz

• find का -regex option आगे की action के target बनने वाले filenames को filter कर सकता है
• इस filter को loop के साथ जोड़कर x/ की संख्या 3, 5, 15 के multiples में है या नहीं, यह जाँचते हुए FizzBuzz implement किया गया है
• उदाहरण readability के लिए -regextype posix-extended का उपयोग करता है, लेकिन इसी तरीके को दूसरी regex syntax के साथ भी इस्तेमाल किया जा सकता है

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"

• दूसरी पंक्ति d के नीचे ऐसा path बनाती है जिसमें x 30 बार जुड़ा होता है
• तीसरी पंक्ति में x की संख्या 15 के multiple होने पर FizzBuzz, 5 के multiple होने पर Buzz, 3 के multiple होने पर Fizz, और अन्यथा d से depth प्रिंट होती है
• इसका execution result OneCompiler उदाहरण में देखा जा सकता है

tag system के जरिए Turing पूर्णता दिखाना

• tag system (m, A, P) से मिलकर बना होता है
  • m एक positive integer है
  • A एक finite alphabet है जिसमें halt symbol H शामिल है
  • P हर alphabet के लिए production rule है
• जब initial string दी जाती है, तो system यह प्रक्रिया दोहराता है
  • यदि string की length m से कम हो या पहला character H हो, तो system रुक जाता है
  • अन्यथा पहले character x के लिए P(x) को string के अंत में जोड़ा जाता है
  • और शुरुआती m characters हटा दिए जाते हैं
• यह ज्ञात है कि m=2, |A|=576 वाला tag system universal Turing machine के बराबर है, इसलिए ऐसे आकार के tag system को चला सकने वाला system Turing पूर्ण है
  • इसका आधार De Mol, L., 2008 है
• वास्तविक implementation उदाहरण Wikipedia के m=2, |A|=4 वाले simple 2-tag system का उपयोग करता है

file path को state के रूप में इस्तेमाल करने का तरीका

• मुख्य विचार यह है कि state दर्शाने वाले file path के पीछे लगातार अगला state जोड़ा जाता रहे
• states के बीच separator के रूप में _ का उपयोग किया गया है
  • उदाहरण: _/b/a/a/_
  • यदि अगला state a/c/c/a हो, तो path _/b/a/a/_/a/c/c/a/_ बन जाता है
• execution के दौरान एक directory के अंदर एक से अधिक file न हों, ऐसा विन्यास रखा गया है
• implementation halt symbol मिलने या string length m से कम या बराबर होने तक अगली states जोड़ता रहता है
• find conditional expression मोटे तौर पर तीन हिस्सों में काम करता है
  • halt condition की जाँच
  • back-reference का उपयोग करके पिछली state में शुरुआती M characters हटाने के बाद बचे हिस्से की copy बनाना
  • a, b, c के लिए production rules लागू करना
• उदाहरण production rules इस प्रकार हैं

M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"

• execution result में अपेक्षित _/H/c/c/c/c/c/c/a/_ प्रिंट होता है
• संबंधित execution result OneCompiler उदाहरण में भी दिया गया है

back-reference और विस्तार की संभावना

• FizzBuzz implementation सामान्य regex का उपयोग करता है, लेकिन tag system implementation back-reference \\2 का उपयोग करता है
• back-reference की वजह से पिछली state में शुरुआती m characters को छोड़कर बाकी हिस्से की copy बनाई जा सकती है
• इस संरचना को बड़े constant-size alphabet तक बढ़ाया जा सकता है
• यदि उपलब्ध characters कम पड़ें, तो हर filename में एक से अधिक characters इस्तेमाल करके इसका समाधान किया जा सकता है
• इसलिए निष्कर्ष यह निकलता है कि find + mkdir का संयोजन Turing पूर्ण है

POSIX सीमाएँ और execution environment

• file path length limit के कारण arbitrary size के automata चलाना संभव न भी हो, लेकिन दिया गया code इस तरह बनाया गया है कि arbitrary length वाले file path सीधे mkdir को न देने पड़ें
• परीक्षण में find ने 30000 characters से लंबे path पर भी काम किया, और कोई अलग सीमा नहीं मिली
• POSIX specification इसकी गारंटी नहीं देती
  • POSIX find दस्तावेज़ स्पष्ट रूप से कहता है कि search के दौरान directory में file जुड़ने पर व्यवहार unspecified है
  • GNU के अलावा दूसरे tools के व्यवहार की पुष्टि नहीं की गई
• इस्तेमाल किया गया environment यह था

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⁺]

Hacker News की राय

• पेज के सबसे ऊपर पहले से ही यह लिखा है: find + mkdir की Turing completeness वाला दावा वापस ले लिया गया है
  कहा गया है कि proof में खामी है, इसलिए find + mkdir के Turing complete होने को साबित करने का दावा वापस लिया जा रहा है, और https://news.ycombinator.com/item?id=41117141 देखने को कहा गया है
  अगर proof ठीक किया जा सके तो लेख अपडेट किया जाएगा

  • यह पहले ही ठीक किया जा चुका है

• क्या इससे Folders implement किया जा सकता है?
  https://www.danieltemkin.com/Esolangs/Folders/

  • Windows में folders के disk space बिल्कुल न लेने वाली व्याख्या, सख्ती से कहें तो सही नहीं है
    Directory entries MFT के अंदर जगह लेती हैं, लेकिन Explorer सिर्फ कहीं और allocated blocks को गिनता है, इसलिए वे दिखती नहीं हैं
    अगर खाली directories लगातार बनाते रहें, तो MFT बढ़ेगा और आखिरकार space की समस्या आएगी
    छोटी files के साथ भी ऐसा ही है: खाली text file size 0 bytes और disk size 0 bytes दिखती है, और करीब 400 bytes डालने पर भी data पहले से allocated MFT की directory entry के अंदर चला जाता है, इसलिए Explorer में disk size 0 दिखता है
    Data को दोगुना कर दें तो disk block allocate हो जाता है और length 800 bytes, disk size 4,096 bytes दिखता है; फिर वापस 400 bytes तक घटाने पर भी data MFT में वापस नहीं जाता, इसलिए 4,096 bytes लेता रहता है
    फिर भी, कुल मिलाकर इस शानदार नतीजे का आनंद लेने में इससे कोई बाधा नहीं आती

• समझ नहीं आता कि यह Turing completeness कैसे दिखाता है
  Rule 110 automaton implementation width limit में भी अटकता दिखता है, और iteration count limit में भी
  दिए गए width के लिए states की संख्या finite है, इसलिए यह Turing complete नहीं है; और चूंकि यह हमेशा terminate होता है, इसलिए भी Turing complete नहीं है
  क्या arbitrary, यानी अनंत रूप से expand हो सकने वाली width और depth वाला Rule 110 implementation लिखा जा सकता है?

  • अगर limitation concept में नहीं बल्कि सिर्फ implementation में है, तो ठीक है
    असली computers भी infinite tape नहीं, बल्कि finite memory इस्तेमाल करते हैं, इसलिए language या method कोई भी हो, वे उस condition को satisfy नहीं करते
  • C भी strict अर्थ में Turing complete नहीं हो सकता: https://cs.stackexchange.com/questions/60965/is-c-actually-t...
  • लेख लेखक ने बाद में article update किया: कहा कि proof में खामी है, इसलिए find + mkdir के Turing complete होने को साबित करने का दावा वापस लिया जा रहा है, और https://news.ycombinator.com/item?id=41117141 देखने को कहा गया
    अगर proof ठीक किया जा सके तो article update किया जाएगा

• वापस लिया गया
  लिखा है कि “proof में खामी है, इसलिए find + mkdir के Turing complete होने को साबित करने का दावा वापस लेता हूं”

• लगा था कि कोई दिलचस्प किस्म का lambda calculus इस्तेमाल होगा, लेकिन असल में यह computation के लिए बस find के regex parser पर निर्भर था

  • Regex को जबरन इस्तेमाल करके काफी complex computation करवाने का यह पहला मामला नहीं है
    याद रहने वाला एक example http://realgl.blogspot.com/2013/08/battlecode.html है; “Regular Expression Pathfinding” हिस्सा देखें

• यह proof cellular automaton के बजाय tag system(https://en.m.wikipedia.org/wiki/Tag_system) इस्तेमाल करे तो शायद काफी simpler हो जाएगा

• कोई भी implementation infinite नहीं हो सकता, लेकिन इस case में आम तौर पर 4096 होने वाला PATH_MAX खास तौर पर कम लगता है

  • “Expected questions and answers” section देखें
    GNU में 4096 से ज्यादा लंबे path lengths पर भी काम करता लगता है
  • लेख में इस समस्या को relative paths इस्तेमाल करके handle किया गया है
    apparently path length 30k तक test किया गया बताया गया है

• Regex (RE, RegExp) को implement या consume करने वाला software/service, या software/service chain के अंदर का कोई component, संभावित रूप से Turing complete हो सकता है
  उस context में security महत्वपूर्ण हो तो Turing completeness है या नहीं, इसका audit करना चाहिए

  • Strictly कहें तो मूल अर्थ वाली regex को केवल stack-रहित finite state machine चाहिए
    Turing completeness पाने के लिए 2 stacks चाहिए
    हालांकि कई regex libraries साधारण “regex” से कहीं ज्यादा features support करती हैं

• मेरा find साबित तौर पर Turing complete ही नहीं, Turing tarpit भी नहीं है और native code में compile होता है