ความสมบูรณ์ทัวริงของ `find` และ `mkdir`

ภาพรวม

• ความพยายามในการพิสูจน์ว่าระบบมีความสมบูรณ์ทัวริงโดยใช้เพียงคำสั่ง find และ mkdir ของ GNU
• เป็นที่ทราบกันดีว่าคำสั่ง sed และ awk มีความสมบูรณ์ทัวริง แต่ไม่มีเอกสารอ้างอิงเกี่ยวกับความสมบูรณ์ทัวริงของ find และ mkdir
• การพิสูจน์ใช้เทคนิคทั่วไปที่แสดงว่าสามารถรัน Rule 110 ได้
• อธิบายตามลำดับของการติดตั้งใช้งานลูป, FizzBuzz และ Rule 110

การติดตั้งใช้งาน

การสร้างลูป

• โค้ดต่อไปนี้จะสร้างไดเรกทอรีแบบเรียกซ้ำและทำให้เกิดลูปไม่สิ้นสุด

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

• find x จะแสดงรายการไฟล์ใต้ x และเมื่อ x ถูกแสดงรายการ ก็จะสร้าง x/x
• หากต้องการจำกัดความลึกของการสร้างไดเรกทอรี ให้ใช้ตัวเลือก -maxdepth

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

FizzBuzz

• ใช้ตัวเลือก -regex ของ find เพื่อกรองชื่อไฟล์ และนำมารวมกับลูปเพื่อทำ FizzBuzz

  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

• เมื่อสามารถใช้ลูปและการแตกแขนงแบบมีเงื่อนไขได้ ก็สามารถเขียนโปรแกรมใด ๆ ก็ได้
• พิสูจน์สิ่งนี้ด้วยการติดตั้งใช้งาน Rule 110

  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 \;
  

คำถามและคำตอบที่คาดไว้

• เนื่องจากข้อจำกัดความยาวของพาธไฟล์ จึงไม่สามารถรันออโตมาตาขนาดตามอำเภอใจได้หรือไม่?

  • mkdir จะล้มเหลวหากส่งพาธไฟล์ที่ยาวเกินค่าหนึ่ง แต่โค้ดข้างต้นหลีกเลี่ยงปัญหานี้ได้
  • find ทำงานได้แม้กับพาธที่ยาวเกิน 30000

• โค้ดข้างต้นรับประกันได้หรือไม่ว่าจะทำงานตามข้อกำหนดของ POSIX?

  • ไม่รับประกัน และหากมีการเพิ่มไฟล์ระหว่างการค้นหาไดเรกทอรี พฤติกรรมจะไม่ถูกระบุไว้
  • เวอร์ชันเครื่องมือที่ใช้:

    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 นั้นน่าสนใจ
• แนวทางการพิสูจน์ด้วยการติดตั้งใช้งาน Rule 110 มีความสร้างสรรค์
• แม้จะไม่มีการรับประกันพฤติกรรมตามข้อกำหนด POSIX แต่ก็ทำงานได้สำเร็จบนเครื่องมือ GNU
• โปรเจ็กต์ที่มีความสามารถคล้ายกันได้แก่ sed และ awk