Kelengkapan Turing pada `find` dan `mkdir`

Gambaran umum

• Upaya untuk membuktikan bahwa sistem bersifat Turing complete hanya dengan perintah GNU find dan mkdir
• Kelengkapan Turing dari perintah sed dan awk sudah dikenal luas, tetapi tidak ada referensi tentang kelengkapan Turing dari find dan mkdir
• Pembuktian memanfaatkan teknik umum dengan menunjukkan bahwa Rule 110 dapat dijalankan
• Dijelaskan secara berurutan melalui implementasi loop, FizzBuzz, dan Rule 110

Implementasi

Menyusun loop

• Kode berikut membuat direktori secara rekursif dan menghasilkan loop tak hingga

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

• find x mencantumkan file di bawah x, dan ketika x tercantum, x/x dibuat
• Untuk membatasi kedalaman pembuatan direktori, gunakan opsi -maxdepth

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

FizzBuzz

• Menggunakan opsi -regex pada find untuk memfilter nama file, lalu menggabungkannya dengan loop untuk mengimplementasikan 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"
  

Implementasi Rule 110

• Jika loop dan percabangan kondisional dapat digunakan, maka program arbitrer dapat ditulis
• Hal ini dibuktikan dengan mengimplementasikan 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 \;
  

Pertanyaan dan jawaban yang diperkirakan

• Apakah automata berukuran arbitrer tidak bisa dijalankan karena batas panjang path file?

  • mkdir gagal jika diberi path file yang melebihi panjang tertentu, tetapi kode di atas menghindari hal itu
  • find tetap bekerja bahkan pada path yang melebihi 30000

• Apakah kode di atas dijamin bekerja sesuai spesifikasi POSIX?

  • Tidak, karena jika file ditambahkan saat pencarian direktori berlangsung, perilakunya tidak ditentukan
  • Versi tool yang digunakan:

    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
    

Ringkasan GN⁺

• Upaya membuktikan kelengkapan Turing hanya dengan perintah find dan mkdir sangat menarik
• Pendekatan yang mencoba membuktikannya melalui implementasi Rule 110 bersifat kreatif
• Meski tidak ada jaminan perilaku menurut spesifikasi POSIX, pendekatan ini berhasil berjalan di tool GNU
• Proyek dengan fungsi serupa antara lain sed dan awk