- เพียงใช้
find และ mkdir ของ GNU ก็สามารถอาศัยลำดับการสร้างและการไล่สำรวจไดเรกทอรีเพื่อสร้างลูปและการเปลี่ยนสถานะได้ ทำให้การผสมผสานยูทิลิตีไฟล์ง่าย ๆ กลายเป็นโมเดลการคำนวณ
- การพิสูจน์ทำผ่านการใช้งาน tag system และการพิสูจน์เวอร์ชันแรกที่อิง Rule 110 ได้รับการแก้ไขเนื่องจากมีปัญหาในการจัดการการทำซ้ำแบบไม่สิ้นสุด
- ลูปพื้นฐานมีโครงสร้างที่
find x -execdir mkdir x/x \; ค้นพบไดเรกทอรีใหม่ต่อไปเรื่อย ๆ และเมื่อเพิ่ม -regex ก็ทำเงื่อนไขแตกแขนงอย่าง FizzBuzz ได้
- การใช้งาน tag system แทนสถานะด้วยพาธไฟล์ และใช้ back-reference เพื่อคัดลอกส่วนที่เหลือหลังตัดอักขระ
m ตัวแรกออก
- POSIX ระบุพฤติกรรมเมื่อมีการเพิ่มไฟล์ในไดเรกทอรีที่กำลังค้นหาไว้เป็น unspecified ดังนั้นข้อสรุปจึงขึ้นอยู่กับพฤติกรรมที่สังเกตได้ของเครื่องมือ GNU และสภาพแวดล้อมที่นำเสนอ
สร้างโมเดลการคำนวณด้วย GNU find และ mkdir
ลูปที่เกิดจากการสร้างไดเรกทอรี
- โค้ดต่อไปนี้สร้างไดเรกทอรีแบบเรียกซ้ำและเข้าสู่ ลูปไม่สิ้นสุด
mkdir x
find x -execdir mkdir x/x \;
find x จะแสดงรายการไฟล์ภายใต้ x โดยรวมถึงตัว x เองด้วย- เมื่อมีการแสดงรายการ
x คำสั่ง mkdir จะสร้าง x/x และในการวนซ้ำถัดไปของ find ก็จะรวม x/x ที่เพิ่งสร้างขึ้นมาใหม่ด้วย
- กระบวนการนี้ทำซ้ำไปเรื่อย ๆ ทำให้เกิดพาธอย่าง
x/x/x, x/x/x/x ต่อไปไม่หยุด
- หากใช้ตัวเลือก
-maxdepth จะจำกัดความลึกที่สร้างได้
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- ตัวอย่างนี้จะสร้าง
x/x/x/x/x แล้วจบการทำงาน
FizzBuzz ที่ใช้งานด้วย find -regex
- ตัวเลือก
-regex ของ find สามารถกรองชื่อไฟล์ที่จะเป็นเป้าหมายของ action ถัดไปได้
- เมื่อนำฟิลเตอร์นี้มารวมกับลูป จะใช้งาน FizzBuzz ที่ตัดสินว่าจำนวน
x/ เป็นพหุคูณของ 3, 5 หรือ 15 ได้
- ตัวอย่างใช้
-regextype posix-extended เพื่อให้อ่านง่าย แต่คาดว่าวิธีเดียวกันทำได้ด้วยไวยากรณ์ regex แบบอื่นเช่นกัน
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 ที่มี x ต่อกัน 30 ตัว
- บรรทัดที่สาม หากจำนวน
x เป็นพหุคูณของ 15 จะพิมพ์ FizzBuzz, ถ้าเป็นพหุคูณของ 5 จะพิมพ์ Buzz, ถ้าเป็นพหุคูณของ 3 จะพิมพ์ Fizz และกรณีอื่นจะพิมพ์ความลึกจาก d
- ดูผลการรันได้ที่ ตัวอย่าง OneCompiler
แสดงความสมบูรณ์แบบทัวริงด้วย tag system
- tag system ประกอบด้วย
(m, A, P)
m คือจำนวนเต็มบวกA คืออัลฟาเบตจำกัดที่มีสัญลักษณ์หยุด HP คือกฎการสร้างของแต่ละอักขระในอัลฟาเบต
- เมื่อมีสตริงเริ่มต้น ระบบจะทำกระบวนการต่อไปนี้ซ้ำ
- หากความยาวสตริงน้อยกว่า
m หรืออักขระตัวแรกเป็น H ให้หยุด
- มิฉะนั้น ให้เพิ่ม
P(x) ของอักขระตัวแรก x ต่อท้ายสตริง
- ลบอักขระ
m ตัวแรกออก
- เป็นที่ทราบว่า tag system ที่
m=2, |A|=576 เป็น universal Turing machine และระบบที่รัน tag system ขนาดนี้ได้ถือว่า ทัวริงสมบูรณ์
- ตัวอย่างการใช้งานจริงใช้ 2-tag system แบบง่ายจาก Wikipedia ที่
m=2, |A|=4
วิธีใช้พาธไฟล์เป็นสถานะ
- ไอเดียหลักคือการต่อสถานะถัดไปไว้ท้ายพาธไฟล์ที่แทนสถานะ
- ใช้
_ เป็นตัวคั่นระหว่างสถานะ
- ตัวอย่าง:
_/b/a/a/_
- หากสถานะถัดไปคือ
a/c/c/a พาธจะกลายเป็น _/b/a/a/_/a/c/c/a/_
- ระหว่างการรัน จะจัดโครงสร้างไม่ให้มีไฟล์มากกว่าหนึ่งไฟล์ภายในไดเรกทอรีเดียวกัน
- การใช้งานจะเพิ่มสถานะถัดไปต่อไปเรื่อย ๆ จนกว่าจะเจอสัญลักษณ์หยุด หรือความยาวสตริงเหลือไม่เกิน
m
- เงื่อนไขของ
find ทำงานเป็นสามส่วนใหญ่ ๆ
- ตรวจสอบ เงื่อนไขหยุด
- ใช้ back-reference เพื่อคัดลอกส่วนที่เหลือหลังตัดอักขระ
M ตัวแรกจากสถานะก่อนหน้า
- ใช้กฎการสร้างสำหรับ
a, b, c
- ตัวอย่างกฎการสร้างมีดังนี้
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- ผลการรันที่คาดหวังคือการพิมพ์
_/H/c/c/c/c/c/c/a/_
- ผลการรันดังกล่าวมีให้ดูเป็น ตัวอย่าง OneCompiler เช่นกัน
Back-reference และความเป็นไปได้ในการขยาย
- การใช้งาน FizzBuzz ใช้ regex ทั่วไป แต่การใช้งาน tag system ใช้ back-reference
\2
- ด้วย back-reference จึงสามารถคัดลอกส่วนของสถานะก่อนหน้าที่ยกเว้นอักขระ
m ตัวแรกได้
- โครงสร้างนี้สามารถขยายไปยังอัลฟาเบตที่มีขนาดคงที่ใหญ่ขึ้นได้
- หากตัวอักขระที่ใช้ได้ไม่พอ สามารถรับมือได้โดยใช้ชื่อไฟล์แต่ละชื่อแทนอักขระมากกว่าหนึ่งตัว
- ดังนั้นจึงได้ข้อสรุปว่าการผสมผสาน
find + mkdir มีความสมบูรณ์แบบทัวริง
ข้อจำกัดของ POSIX และสภาพแวดล้อมการรัน
- เนื่องจากข้อจำกัดความยาวพาธไฟล์ อาจไม่สามารถรันออโตมาตาที่มีขนาดใด ๆ ได้ แต่โค้ดที่นำเสนอถูกจัดโครงสร้างไม่ให้ส่งพาธไฟล์ความยาวใดก็ได้ให้
mkdir โดยตรง
- ในการทดสอบ
find ทำงานได้แม้กับพาธที่ยาวเกิน 30000 อักขระ และไม่พบข้อจำกัดแยกต่างหาก
- ไม่มีการรับประกันตามสเปก POSIX
- เอกสาร POSIX
find ระบุไว้ว่าพฤติกรรมเมื่อมีการเพิ่มไฟล์ในไดเรกทอรีที่กำลังค้นหาอยู่เป็น unspecified
- ยังไม่ได้ตรวจสอบพฤติกรรมของเครื่องมือที่ไม่ใช่ GNU
- สภาพแวดล้อมที่ใช้มีดังนี้
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
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ด้านบนสุดของหน้ามีเขียนไว้แล้วว่า: ข้ออ้างเรื่อง ความเป็นทัวริงสมบูรณ์ของ find + mkdir ถูกถอนแล้ว
มีระบุว่าเนื่องจากมีข้อบกพร่องในบทพิสูจน์ จึงขอถอนคำกล่าวอ้างที่ว่าพิสูจน์ได้ว่า find + mkdir เป็นทัวริงสมบูรณ์ และให้ดู https://news.ycombinator.com/item?id=41117141
และบอกว่าจะอัปเดตบทความหากสามารถแก้บทพิสูจน์ได้
ใช้อันนี้ทำ Folders ได้ไหม?
https://www.danieltemkin.com/Esolangs/Folders/
รายการไดเรกทอรีกินพื้นที่อยู่ใน MFT แต่ Explorer นับเฉพาะบล็อกที่ถูกจัดสรรในที่อื่น จึงแค่ไม่แสดงออกมาเท่านั้น
ถ้าสร้างไดเรกทอรีว่างต่อไปเรื่อย ๆ MFT จะใหญ่ขึ้นและสุดท้ายก็จะมีปัญหาเรื่องพื้นที่
ไฟล์เล็ก ๆ ก็คล้ายกัน โดยไฟล์ข้อความว่างจะเห็นว่ามีขนาด 0 ไบต์ และขนาดบนดิสก์ 0 ไบต์ และแม้ใส่ข้อมูลราว 400 ไบต์ ข้อมูลก็ยังอยู่ในรายการไดเรกทอรีของ MFT ที่จัดสรรไว้ล่วงหน้า ทำให้ Explorer ยังแสดงขนาดบนดิสก์เป็น 0
ถ้าเพิ่มข้อมูลเป็นสองเท่า ก็จะมีการจัดสรรบล็อกดิสก์ ทำให้เห็นความยาว 800 ไบต์ และขนาดบนดิสก์ 4,096 ไบต์ และแม้จะลดกลับมาเหลือ 400 ไบต์ ข้อมูลก็จะไม่กลับเข้า MFT จึงยังคงกิน 4,096 ไบต์ต่อไป
ถึงอย่างนั้นก็ไม่ได้ลดทอนความเพลิดเพลินกับผลงานที่ยอดเยี่ยมนี้โดยรวม
ผมไม่เข้าใจว่านี่แสดง ความเป็นทัวริงสมบูรณ์ ได้อย่างไร
การอิมพลีเมนต์ออโตมาตา Rule 110 ดูเหมือนจะติดทั้งข้อจำกัดด้านความกว้างและจำนวนรอบที่วนซ้ำ
จำนวนสถานะสำหรับความกว้างที่กำหนดมีจำกัด จึงไม่เป็นทัวริงสมบูรณ์ และเพราะมันจบการทำงานเสมอ จึงไม่เป็นทัวริงสมบูรณ์เช่นกัน
สามารถเขียนการอิมพลีเมนต์ Rule 110 ที่มีความกว้างและความลึกแบบกำหนดได้ตามอำเภอใจ กล่าวคือขยายได้ไม่สิ้นสุด ได้หรือไม่?
คอมพิวเตอร์จริงก็ใช้หน่วยความจำจำกัด ไม่ได้มีเทปอนันต์ ดังนั้นไม่ว่าภาษาหรือวิธีไหนก็ไม่ผ่านเงื่อนไขนั้นอยู่แล้ว
มีระบุว่าจะอัปเดตบทความหากสามารถแก้บทพิสูจน์ได้
ถูกถอนแล้ว
มีเขียนไว้ว่า “เนื่องจากมีข้อบกพร่องในบทพิสูจน์ จึงขอถอนคำกล่าวอ้างที่ว่าพิสูจน์ได้ว่า find + mkdir เป็นทัวริงสมบูรณ์”
นึกว่าจะได้เห็น แลมบ์ดาแคลคูลัส ในรูปแบบน่าสนใจ แต่ในความเป็นจริงกลับพึ่งพา regex parser ของ find สำหรับการคำนวณ
ตัวอย่างที่ยังจำได้คือ http://realgl.blogspot.com/2013/08/battlecode.html และให้ดูส่วน “Regular Expression Pathfinding”
บทพิสูจน์นี้น่าจะทำให้ง่ายขึ้นมากถ้าใช้ tag system(https://en.m.wikipedia.org/wiki/Tag_system) แทน เซลลูลาร์ออโตมาตา
ไม่มีอิมพลีเมนต์ใดเป็นอนันต์ได้จริง แต่ในกรณีนี้ค่า PATH_MAX ที่โดยทั่วไปเป็น 4096 ดูต่ำเป็นพิเศษ
บน GNU ดูเหมือนว่าจะยังทำงานได้แม้ความยาวพาธเกิน 4096
เห็นว่าได้ทดสอบกับความยาวพาธถึง 30k
ซอฟต์แวร์/บริการที่อิมพลีเมนต์หรือประมวลผล regex (RE, RegExp) หรือองค์ประกอบภายในสายโซ่ของซอฟต์แวร์/บริการ อาจมีความเป็นไปได้ที่จะ ทัวริงสมบูรณ์
ในบริบทนั้น หากความปลอดภัยเป็นเรื่องสำคัญ ก็ควรตรวจสอบว่ามีความเป็นทัวริงสมบูรณ์หรือไม่
ถ้าจะให้ได้ความเป็นทัวริงสมบูรณ์ จำเป็นต้องมี 2 สแตก
แต่ไลบรารี regex จำนวนมากก็รองรับความสามารถที่มากกว่า “regex” แบบง่าย ๆ มาก
find ของผมไม่เพียงแต่เป็นทัวริงสมบูรณ์แบบพิสูจน์ได้เท่านั้น แต่ยังไม่ใช่ Turing tarpit และยังคอมไพล์เป็น native code ได้ด้วย