`find` ve `mkdir` komutlarının Turing tamlığı

Genel Bakış

• Yalnızca GNU'nun find ve mkdir komutlarıyla sistemin Turing tam olduğunu kanıtlama girişimi
• sed ve awk komutlarının Turing tam olduğu iyi biliniyor, ancak find ve mkdirin Turing tamlığına dair başvuru kaynağı yok
• Kanıt, Rule 110'u çalıştırabildiğini göstermeye yönelik genel bir tekniği kullanıyor
• Açıklama; döngüler, FizzBuzz ve Rule 110'un uygulanması sırasıyla ilerliyor

Uygulama

Döngü oluşturma

• Aşağıdaki kod dizinleri özyineli olarak oluşturur ve sonsuz bir döngü meydana getirir

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

• find x, x altındaki dosyaları listeler ve x listelendiğinde x/x oluşturulur
• Dizin oluşturma derinliğini sınırlamak için -maxdepth seçeneği kullanılır

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

FizzBuzz

• findin -regex seçeneği dosya adlarını filtrelemek için kullanılır ve döngüyle birleştirilerek FizzBuzz uygulanır

  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"
  

Rule 110 uygulaması

• Döngü ve koşullu dallanma kullanılabildiğinde keyfi programlar yazmak mümkün hale gelir
• Bunu kanıtlamak için Rule 110 uygulanır

  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 \;
  

Beklenen sorular ve yanıtlar

• Dosya yolu uzunluğu sınırı nedeniyle keyfi büyüklükte bir otomata çalıştırılamaz mı?

  • mkdir, belirli bir uzunluğun üzerindeki dosya yolları verildiğinde başarısız olur, ancak yukarıdaki kod bundan kaçınır
  • find, 30000'den uzun yollarda da çalışır

• Yukarıdaki kodun POSIX belirtimine göre çalışmasının garanti edildiği söylenebilir mi?

  • Hayır; dizin taraması sırasında dosya eklenirse davranış tanımlanmamıştır
  • Kullanılan araç sürümleri:

    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
    

GN⁺ özeti

• Yalnızca find ve mkdir komutlarıyla Turing tamlığını kanıtlama girişimi ilgi çekici
• Bunu Rule 110 uygulamasıyla kanıtlama yaklaşımı yaratıcı
• POSIX belirtimine göre çalışma garantisi olmasa da GNU araçlarında başarıyla çalışıyor
• Benzer işlevlere sahip projeler arasında sed ve awk bulunuyor