Tính Turing-complete của find và mkdir

 (ogiekako.vercel.app)
1 điểm bởi GN⁺ 2024-08-01 | 1 bình luận | Chia sẻ qua WhatsApp
  • Chỉ với find và mkdir của GNU, có thể tạo vòng lặp và chuyển đổi trạng thái bằng cách tận dụng việc tạo thư mục và thứ tự duyệt, biến tổ hợp các tiện ích tệp đơn giản thành một mô hình tính toán
  • Chứng minh được thực hiện thông qua việc triển khai tag system, còn chứng minh dựa trên Rule 110 ở phiên bản đầu đã được sửa do vấn đề xử lý lặp vô hạn
  • Vòng lặp cơ bản có cấu trúc trong đó find x -execdir mkdir x/x \; liên tục phát hiện các thư mục mới; nếu thêm -regex thì cũng có thể rẽ nhánh điều kiện kiểu FizzBuzz
  • Triển khai tag system biểu diễn trạng thái bằng đường dẫn tệp và dùng back-reference để sao chép phần còn lại sau khi loại bỏ m ký tự đầu
  • POSIX để hành vi khi tệp được thêm vào thư mục đang được tìm kiếm là unspecified, nên kết luận phụ thuộc vào hành vi quan sát được của các công cụ GNU và môi trường được nêu

Xây dựng mô hình tính toán bằng GNU find và mkdir

  • Mục tiêu là chứng minh rằng một hệ thống chỉ có các lệnh find và mkdir của GNU là Turing-complete
  • Chứng minh được tiến hành bằng cách triển khai tag system
  • Luồng tổng thể đi theo thứ tự: xây dựng vòng lặp, FizzBuzz, rồi triển khai tag system
  • Lỗi trong chứng minh dựa trên Rule 110 ở phiên bản đầu ngày 2/8/2024 đã được sửa, và phiên bản hiện tại chuyển sang triển khai tag system
    • Phiên bản đầu có vấn đề là không xử lý được số lần lặp vô hạn
  • Bài báo liên quan Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation đã được chấp nhận tại FUN with Algorithms 2026

Vòng lặp được tạo ra bởi việc tạo thư mục

  • Đoạn mã sau tạo thư mục đệ quy và đi vào 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, bao gồm cả chính x
  • Khi x được liệt kê, mkdir tạo x/x, và ở vòng lặp tiếp theo của find, x/x mới được tạo sẽ được đưa vào
  • Quá trình này lặp lại, liên tục tạo ra các đường dẫn như x/x/x, x/x/x/x
  • Có thể dùng tùy chọn -maxdepth để giới hạn độ sâu tạo ra
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
  • Ví dụ này tạo x/x/x/x/x rồi kết thúc

FizzBuzz triển khai bằng find -regex

  • Tùy chọn -regex của find có thể lọc tên tệp sẽ trở thành đối tượng của các hành động tiếp theo
  • Kết hợp bộ lọc này với vòng lặp để triển khai FizzBuzz, xác định số lượng x/ có phải là bội số của 3, 5, hoặc 15 hay không
  • Ví dụ dùng -regextype posix-extended để dễ đọc, nhưng có thể xem là cùng cách này cũng làm được với các cú pháp biểu thức chính quy khác
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òng thứ hai tạo một đường dẫn bên dưới d với 30 x liên tiếp
  • Dòng thứ ba in FizzBuzz nếu số lượng x là bội số của 15, Buzz nếu là bội số của 5, Fizz nếu là bội số của 3, còn lại thì in độ sâu tính từ d
  • Có thể xem kết quả chạy trong ví dụ OneCompiler

Chứng minh Turing-complete bằng tag system

  • Tag system gồm (m, A, P)
    • m là một số nguyên dương
    • A là bảng chữ cái hữu hạn chứa ký hiệu dừng H
    • P là quy tắc sinh cho từng ký tự trong bảng chữ cái
  • Khi có chuỗi ban đầu, hệ thống lặp lại quá trình sau
    • Dừng nếu độ dài chuỗi nhỏ hơn m hoặc ký tự đầu tiên là H
    • Nếu không, thêm P(x) ứng với ký tự đầu tiên x vào cuối chuỗi
    • Xóa m ký tự đầu
  • Người ta đã biết rằng tag system với m=2, |A|=576 là máy Turing phổ dụng; hệ thống có thể chạy tag system cỡ này là Turing-complete
  • Ví dụ triển khai thực tế dùng 2-tag system đơn giản trên Wikipedia với m=2, |A|=4

Cách dùng đường dẫn tệp làm trạng thái

  • Ý tưởng cốt lõi là liên tục nối trạng thái tiếp theo vào sau đường dẫn tệp biểu diễn trạng thái
  • Dùng _ làm dấu phân tách giữa các trạng thái
    • Ví dụ: _/b/a/a/_
    • Nếu trạng thái tiếp theo là a/c/c/a thì đường dẫn trở thành _/b/a/a/_/a/c/c/a/_
  • Trong khi chạy, cấu hình sao cho trong một thư mục không có nhiều hơn một tệp
  • Việc triển khai tiếp tục thêm trạng thái kế tiếp cho đến khi gặp ký hiệu dừng hoặc độ dài chuỗi trở thành không quá m
  • Biểu thức điều kiện của find hoạt động chủ yếu theo ba phần
    • Kiểm tra điều kiện dừng
    • Dùng back-reference để sao chép phần còn lại sau khi loại bỏ M ký tự đầu từ trạng thái trước đó
    • Áp dụng quy tắc sinh cho a, b, c
  • Các quy tắc sinh ví dụ như sau
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
  • Kết quả chạy kỳ vọng là _/H/c/c/c/c/c/c/a/_
  • Kết quả chạy đó cũng được cung cấp dưới dạng ví dụ OneCompiler

Back-reference và khả năng mở rộng

  • Triển khai FizzBuzz dùng biểu thức chính quy thông thường, nhưng triển khai tag system dùng back-reference \2
  • Nhờ back-reference, có thể sao chép phần của trạng thái trước sau khi bỏ qua m ký tự đầu tiên
  • Cấu trúc này có thể mở rộng sang bảng chữ cái có kích thước hằng số lớn hơn
  • Nếu thiếu ký tự có thể dùng nhiều hơn một ký tự cho mỗi tên tệp để xử lý
  • Vì vậy đi đến kết luận rằng tổ hợp find + mkdir là Turing-complete

Ràng buộc POSIX và môi trường chạy

  • Do giới hạn độ dài đường dẫn tệp, có khả năng không chạy được automata có kích thước tùy ý, nhưng mã được trình bày được cấu hình để không truyền trực tiếp đường dẫn tệp có độ dài tùy ý cho mkdir
  • Trong thử nghiệm, find vẫn hoạt động với đường dẫn dài hơn 30000 ký tự, và không tìm thấy giới hạn riêng nào
  • Không có đảm bảo theo đặc tả POSIX
    • Tài liệu POSIX find nêu rõ rằng khi tệp được thêm vào thư mục đang được tìm kiếm, hành vi là unspecified
    • Chưa kiểm chứng hành vi của các công cụ ngoài GNU
  • Môi trường được sử dụng như sau
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

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-08-01
Ý kiến trên Hacker News

  • Ngay đầu trang đã ghi rõ thế này: tuyên bố tính Turing hoàn chỉnh của find + mkdir đã bị rút lại
    Có ghi rằng do có lỗi trong chứng minh nên họ rút lại tuyên bố rằng đã chứng minh được find + mkdir là Turing hoàn chỉnh, và bảo xem https://news.ycombinator.com/item?id=41117141
    Họ nói sẽ cập nhật bài viết nếu có thể sửa được chứng minh

    • Đã được sửa rồi

  • Có thể dùng cái này để triển khai Folders không?
    https://www.danieltemkin.com/Esolangs/Folders/

    • Nói rằng thư mục trên Windows hoàn toàn không tốn dung lượng đĩa thì xét chặt chẽ là không đúng
      Các mục thư mục vẫn chiếm chỗ trong MFT, chỉ là Explorer chỉ tính các block được cấp phát ở nơi khác nên không hiện ra thôi
      Nếu cứ tiếp tục tạo thư mục rỗng thì MFT sẽ lớn dần lên và cuối cùng vẫn gặp vấn đề về dung lượng
      Các tệp nhỏ cũng tương tự: một tệp văn bản rỗng sẽ hiện kích thước 0 byte · dung lượng đĩa 0 byte, và kể cả khi thêm khoảng 400 byte thì dữ liệu vẫn nằm trong mục thư mục của MFT đã được cấp phát sẵn nên Explorer vẫn hiện dung lượng đĩa là 0
      Nếu tăng dữ liệu lên gấp đôi thì các block đĩa sẽ được cấp phát, khi đó sẽ hiện độ dài 800 byte, dung lượng đĩa 4.096 byte, và dù giảm lại còn 400 byte thì dữ liệu cũng không quay lại MFT nên vẫn tiếp tục chiếm 4.096 byte
      Dù vậy điều này cũng không làm giảm đi sự thích thú với thành quả rất tuyệt này

  • Tôi không hiểu điều này cho thấy tính Turing hoàn chỉnh như thế nào
    Việc cài đặt automaton quy tắc 110 có vẻ vừa bị giới hạn về bề rộng, vừa bị giới hạn về số lần lặp
    Số trạng thái cho một bề rộng nhất định là hữu hạn nên không Turing hoàn chỉnh, và vì luôn kết thúc nên cũng không Turing hoàn chỉnh
    Có thể viết một bản cài đặt quy tắc 110 với bề rộng và độ sâu tùy ý, tức là có thể mở rộng vô hạn, hay không?

    • Nếu giới hạn chỉ nằm ở phần triển khai chứ không phải ở khái niệm thì vẫn ổn
      Máy tính thực tế cũng dùng bộ nhớ hữu hạn chứ không phải băng vô hạn, nên dù là ngôn ngữ hay phương pháp nào thì cũng không thỏa điều kiện đó
    • Ngay cả C cũng có thể, xét theo nghĩa nghiêm ngặt, không Turing hoàn chỉnh: https://cs.stackexchange.com/questions/60965/is-c-actually-t...
    • Sau đó tác giả bài viết đã cập nhật: họ nói do có lỗi trong chứng minh nên rút lại tuyên bố rằng find + mkdir là Turing hoàn chỉnh, và bảo xem https://news.ycombinator.com/item?id=41117141
      Họ nói sẽ cập nhật bài viết nếu có thể sửa được chứng minh

  • Đã bị rút lại
    Có ghi rằng: “Do có lỗi trong chứng minh, tôi rút lại tuyên bố rằng đã chứng minh được find + mkdir là Turing hoàn chỉnh”

  • Tôi cứ nghĩ sẽ thấy một dạng lambda calculus thú vị, nhưng thực ra nó chỉ dựa vào bộ phân tích cú pháp regex của find để tính toán

  • Có vẻ chứng minh này sẽ đơn giản hơn nhiều nếu dùng tag system (https://en.m.wikipedia.org/wiki/Tag_system) thay vì cellular automata

  • Không có cách triển khai nào có thể là vô hạn, nhưng trong trường hợp này giá trị PATH_MAX thường là 4096 có vẻ đặc biệt thấp

    • Xem phần “Expected questions and answers”
      Trên GNU, có vẻ nó vẫn hoạt động với độ dài đường dẫn lớn hơn 4096
    • Bài viết xử lý vấn đề này bằng cách dùng đường dẫn tương đối
      apparently họ nói đã thử tới độ dài đường dẫn 30k

  • Phần mềm/dịch vụ triển khai hoặc tiêu thụ regex (RE, RegExp), hoặc các thành phần trong một chuỗi phần mềm/dịch vụ như vậy, về mặt tiềm năng có thể Turing hoàn chỉnh
    Trong bối cảnh đó, nếu bảo mật là điều quan trọng thì nên kiểm tra xem chúng có tính Turing hoàn chỉnh hay không

    • Nói một cách chặt chẽ thì regex theo nghĩa gốc chỉ cần một máy trạng thái hữu hạn không có stack
      Để có được tính Turing hoàn chỉnh thì cần 2 stack
      Tuy vậy, nhiều thư viện regex hỗ trợ nhiều tính năng hơn rất nhiều so với “regex” đơn thuần

  • find của tôi không chỉ có thể chứng minh là Turing hoàn chỉnh, mà còn không phải Turing tarpit và được biên dịch thành mã máy native