- Hanya dengan
find dan mkdir GNU, loop dan transisi status dapat dibuat dengan memanfaatkan pembuatan direktori serta urutan penelusuran, sehingga kombinasi utilitas berkas sederhana menjadi sebuah model komputasi
- Pembuktian dilakukan lewat implementasi tag system, dan pembuktian versi pertama yang berbasis Rule 110 direvisi karena masalah dalam menangani iterasi tak hingga
- Loop dasarnya adalah struktur
find x -execdir mkdir x/x \; yang terus menemukan direktori baru, dan dengan menambahkan -regex, percabangan kondisional seperti FizzBuzz juga dimungkinkan
- Implementasi tag system merepresentasikan status sebagai path berkas dan menyalin sisa setelah menghapus
m karakter pertama dengan back-reference
- POSIX menetapkan perilaku saat berkas ditambahkan ke direktori yang sedang ditelusuri sebagai unspecified, sehingga kesimpulannya bergantung pada perilaku teramati dari alat GNU dan lingkungan yang digunakan
Membangun model komputasi dengan GNU find dan mkdir
- Tujuannya adalah menunjukkan bahwa sistem yang hanya memiliki perintah
find dan mkdir GNU bersifat Turing-complete
- Pembuktian dilakukan dengan mengimplementasikan tag system
- Alur keseluruhannya berlanjut dalam urutan konstruksi loop, FizzBuzz, lalu implementasi tag system
- Kesalahan pada pembuktian versi pertama berbasis Rule 110 pada 2 Agustus 2024 telah diperbaiki, dan versi saat ini diganti menjadi implementasi tag system
- Versi pertama memiliki masalah karena tidak dapat menangani jumlah iterasi tak hingga
- Makalah terkait, Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation, diterima di FUN with Algorithms 2026
Loop yang dihasilkan oleh pembuatan direktori
- Kode berikut membuat direktori secara rekursif dan masuk ke loop tak hingga
mkdir x
find x -execdir mkdir x/x \;
find x menampilkan berkas di bawah x, termasuk x itu sendiri- Saat
x ditampilkan, mkdir membuat x/x, dan pada iterasi find berikutnya, x/x yang baru dibuat ikut disertakan
- Proses ini berulang, sehingga path seperti
x/x/x, x/x/x/x terus dibuat
- Opsi
-maxdepth dapat digunakan untuk membatasi kedalaman yang dibuat
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- Contoh ini berakhir setelah membuat
x/x/x/x/x
FizzBuzz yang diimplementasikan dengan find -regex
- Opsi
-regex pada find dapat memfilter nama berkas yang akan menjadi target aksi berikutnya
- Filter ini digabungkan dengan loop untuk mengimplementasikan FizzBuzz yang menentukan apakah jumlah
x/ merupakan kelipatan 3, 5, atau 15
- Contohnya menggunakan
-regextype posix-extended demi keterbacaan, tetapi pendekatan yang sama dianggap bisa diterapkan dengan sintaks regex lain
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"
- Baris kedua membuat path di bawah
d dengan x berulang sebanyak 30 kali
- Baris ketiga mencetak
FizzBuzz bila jumlah x adalah kelipatan 15, Buzz bila kelipatan 5, Fizz bila kelipatan 3, dan selain itu mencetak kedalaman dari d
- Hasil eksekusinya dapat dilihat pada contoh OneCompiler
Menunjukkan kelengkapan Turing dengan tag system
- Tag system terdiri dari
(m, A, P)
m adalah bilangan bulat positifA adalah alfabet hingga yang mencakup simbol berhenti HP adalah aturan produksi untuk tiap simbol alfabet
- Bila diberikan string awal, sistem mengulang proses berikut
- Jika panjang string lebih kecil dari
m atau karakter pertama adalah H, sistem berhenti
- Jika tidak,
P(x) untuk karakter pertama x ditambahkan ke akhir string
m karakter terdepan kemudian dihapus
- Diketahui bahwa tag system dengan
m=2 dan |A|=576 adalah mesin Turing universal, sehingga sistem yang dapat menjalankan tag system sebesar ini bersifat Turing-complete
- Contoh implementasi aktual menggunakan simple 2-tag system dari Wikipedia dengan
m=2 dan |A|=4
Menggunakan path berkas sebagai status
- Ide intinya adalah terus menambahkan status berikutnya di belakang path berkas yang merepresentasikan status saat ini
_ digunakan sebagai pemisah antarstatus
- Contoh:
_/b/a/a/_
- Jika status berikutnya adalah
a/c/c/a, path menjadi _/b/a/a/_/a/c/c/a/_
- Selama eksekusi, di dalam satu direktori diatur agar tidak ada lebih dari satu berkas
- Implementasi terus menambahkan status berikutnya sampai bertemu simbol berhenti atau panjang string menjadi
m atau kurang
- Ekspresi kondisi
find bekerja dalam tiga bagian besar
- Memeriksa kondisi berhenti
- Menyalin sisa status sebelumnya setelah menghapus
M simbol pertama dengan memanfaatkan back-reference
- Menerapkan aturan produksi untuk
a, b, dan c
- Contoh aturan produksinya adalah sebagai berikut
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- Hasil eksekusi yang diharapkan adalah
_/H/c/c/c/c/c/c/a/_
- Hasil eksekusi tersebut juga disediakan sebagai contoh OneCompiler
Back-reference dan kemungkinan perluasan
- Implementasi FizzBuzz menggunakan regex biasa, tetapi implementasi tag system memakai back-reference
\\2
- Berkat back-reference, bagian setelah
m karakter pertama dari status sebelumnya dapat disalin
- Susunan ini dapat diperluas ke alfabet berukuran konstanta yang lebih besar
- Jika karakter yang tersedia tidak cukup, hal itu dapat diatasi dengan memakai lebih dari satu karakter untuk tiap nama berkas
- Karena itu, ditarik kesimpulan bahwa kombinasi
find + mkdir bersifat Turing-complete
Batasan POSIX dan lingkungan eksekusi
- Karena batas panjang path berkas, ada kemungkinan automata berukuran sewenang-wenang tidak dapat dijalankan, tetapi kode yang disajikan disusun agar tidak langsung memberikan path berkas dengan panjang sembarang ke
mkdir
- Dalam pengujian,
find tetap berfungsi pada path lebih dari 30000 karakter, dan tidak ditemukan batasan khusus lain
- Tidak ada jaminan dalam spesifikasi POSIX
- Dokumen POSIX
find menyatakan bahwa perilaku saat berkas ditambahkan ke direktori yang sedang ditelusuri adalah unspecified
- Perilaku alat selain GNU tidak diverifikasi
- Lingkungan yang digunakan adalah sebagai berikut
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 komentar
Komentar Hacker News
Di bagian paling atas halaman sudah tertulis seperti ini: klaim kelengkapan Turing find + mkdir telah ditarik
Disebutkan bahwa karena ada cacat dalam pembuktiannya, klaim bahwa telah membuktikan find + mkdir bersifat Turing-complete ditarik, dan diminta melihat https://news.ycombinator.com/item?id=41117141
Tertulis bahwa jika pembuktiannya bisa diperbaiki, artikel akan diperbarui
Bisakah Folders diimplementasikan dengan ini?
https://www.danieltemkin.com/Esolangs/Folders/
Entri direktori memang memakan ruang di dalam MFT, hanya saja Explorer hanya menghitung blok yang dialokasikan di tempat lain sehingga tidak ditampilkan
Jika terus membuat direktori kosong, MFT akan membesar dan pada akhirnya menimbulkan masalah ruang
File kecil juga mirip: file teks kosong terlihat berukuran 0 byte dan ukuran di disk 0 byte; bahkan jika diisi sekitar 400 byte, datanya masuk ke entri direktori MFT yang sudah dialokasikan sebelumnya sehingga di Explorer ukuran di disk terlihat 0
Jika datanya digandakan, blok disk dialokasikan sehingga terlihat panjangnya 800 byte dan ukuran di disk 4.096 byte; lalu meski dikurangi lagi menjadi 400 byte, data tidak kembali ke MFT dan tetap memakan 4.096 byte
Meski begitu, hal ini tidak menghalangi untuk menikmati hasil keseluruhannya yang luar biasa
Saya tidak paham bagaimana ini menunjukkan kelengkapan Turing
Implementasi otomaton Rule 110 tampaknya terkena batas lebar dan juga batas jumlah iterasi
Jumlah state untuk lebar tertentu terbatas, jadi tidak Turing-complete; dan karena selalu berhenti, itu juga tidak Turing-complete
Bisakah kita menulis implementasi Rule 110 dengan lebar dan kedalaman arbitrer, yaitu dapat diperluas tanpa batas?
Komputer nyata juga memakai memori terbatas, bukan tape tak terbatas, sehingga terlepas dari bahasa atau metodenya, syarat itu tidak terpenuhi
Tertulis bahwa jika pembuktiannya bisa diperbaiki, artikel akan diperbarui
Ditarik
Tertulis bahwa “karena ada cacat dalam pembuktian, klaim bahwa telah membuktikan find + mkdir bersifat Turing-complete ditarik”
Saya kira akan memakai bentuk kalkulus lambda yang menarik, tetapi kenyataannya hanya bergantung pada parser regex milik find untuk komputasi
Contoh yang saya ingat adalah http://realgl.blogspot.com/2013/08/battlecode.html, lihat bagian “Regular Expression Pathfinding”
Pembuktian ini sepertinya akan jauh lebih sederhana jika memakai sistem tag (https://en.m.wikipedia.org/wiki/Tag_system) alih-alih otomaton seluler
Tidak ada implementasi yang bisa tak terbatas, tetapi dalam kasus ini PATH_MAX yang nilai umumnya 4096 terlihat sangat rendah
Di GNU, tampaknya ini tetap berjalan pada panjang path yang lebih dari 4096
apparently katanya sudah diuji hingga panjang path 30k
Perangkat lunak/layanan yang mengimplementasikan atau mengonsumsi regex (RE, RegExp), atau komponen dalam rantai perangkat lunak/layanan, berpotensi Turing-complete
Jika keamanan penting dalam konteks tersebut, status Turing-complete-nya perlu diaudit
Untuk memperoleh kelengkapan Turing, diperlukan 2 stack
Namun banyak pustaka regex mendukung jauh lebih banyak fitur daripada “regex” sederhana
find saya bukan hanya terbukti Turing-complete, tetapi juga bukan Turing tarpit, dan dikompilasi menjadi kode native