Tính hoàn chỉnh Turing của `find` và `mkdir`

Tổng quan

• Một nỗ lực chứng minh rằng chỉ với các lệnh find và mkdir của GNU, hệ thống đã là Turing-complete
• Tính hoàn chỉnh Turing của các lệnh sed và awk đã được biết đến rộng rãi, nhưng không có tài liệu tham khảo về tính hoàn chỉnh Turing của find và mkdir
• Bài chứng minh sử dụng kỹ thuật phổ biến là cho thấy có thể chạy Rule 110
• Nội dung được trình bày theo thứ tự: vòng lặp, FizzBuzz, rồi triển khai Rule 110

Triển khai

Cấu thành vòng lặp

• Đoạn mã sau tạo thư mục theo cách đệ quy và tạo ra vòng lặp vô hạn

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

• find x liệt kê các tệp bên dưới x, và khi x được liệt kê thì x/x sẽ được tạo
• Để giới hạn độ sâu tạo thư mục, dùng tùy chọn -maxdepth

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

FizzBuzz

• Dùng tùy chọn -regex của find để lọc tên tệp, rồi kết hợp với vòng lặp để triển khai 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"
  

Triển khai Rule 110

• Khi đã có thể dùng vòng lặp và rẽ nhánh điều kiện, có thể viết chương trình tùy ý
• Điều này được chứng minh bằng cách triển khai 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 \;
  

Câu hỏi dự kiến và trả lời

• Có phải do giới hạn độ dài đường dẫn tệp nên không thể chạy automaton có kích thước tùy ý?

  • mkdir sẽ thất bại nếu nhận đường dẫn tệp vượt quá một độ dài nhất định, nhưng đoạn mã trên tránh được điều đó
  • find vẫn hoạt động với các đường dẫn dài hơn 30000

• Có bảo đảm rằng đoạn mã trên hoạt động theo đặc tả POSIX không?

  • Không, vì khi thêm tệp trong lúc đang duyệt thư mục thì hành vi không được đặc tả
  • Phiên bản công cụ được sử dụng:

    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
    

Tóm tắt của GN⁺

• Nỗ lực chứng minh tính hoàn chỉnh Turing chỉ với các lệnh find và mkdir là một ý tưởng thú vị
• Cách tiếp cận chứng minh điều này thông qua việc triển khai Rule 110 là sáng tạo
• Dù không có bảo đảm về hành vi theo đặc tả POSIX, nó vẫn chạy thành công trên các công cụ GNU
• Những dự án có chức năng tương tự gồm sed và awk