- Yalnızca GNU
find ve mkdir ile bile, dizin oluşturma ve dolaşma sırası kullanılarak döngüler ve durum geçişleri kurulabiliyor; böylece basit dosya yardımcı programlarının birleşimi bir hesaplama modeli haline geliyor
- Kanıt, bir tag system uygulaması üzerinden ilerliyor; Rule 110 tabanlı ilk sürümdeki kanıt, sonsuz yineleme işleme sorunu nedeniyle düzeltilmiş
- Temel döngü,
find x -execdir mkdir x/x \; komutunun yeni dizinleri sürekli keşfetmesi üzerine kurulu ve -regex eklendiğinde FizzBuzz benzeri koşullu dallanma da mümkün oluyor
- Tag system uygulaması durumu dosya yolu olarak ifade ediyor ve back-reference kullanarak baştaki
m karakter çıkarıldıktan sonra kalanı kopyalıyor
- POSIX, arama yapılan dizine dosya eklendiğinde davranışı unspecified bırakıyor; bu nedenle sonuç, GNU araçlarının gözlemlenen davranışına ve verilen ortama bağlı
GNU find ve mkdir ile hesaplama modeli kurmak
Dizin oluşturmanın yarattığı döngü
- Aşağıdaki kod, dizinleri özyinelemeli olarak oluşturup sonsuz döngüye giriyor
mkdir x
find x -execdir mkdir x/x \;
find x, x altındaki dosyaları listeliyor ve buna x'in kendisi de dahilx listelendiğinde mkdir, x/x dizinini oluşturuyor; sonraki find yinelemesinde ise yeni oluşan x/x da dahil ediliyor- Bu süreç tekrarlandıkça
x/x/x, x/x/x/x gibi yollar oluşmaya devam ediyor
-maxdepth seçeneği kullanılırsa oluşturma derinliği sınırlandırılabiliyor
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- Bu örnek,
x/x/x/x/x oluşturduktan sonra sonlanıyor
find -regex ile FizzBuzz uygulaması
find komutunun -regex seçeneği, sonraki eylemin uygulanacağı dosya adlarını filtreleyebiliyor- Bu filtre döngüyle birleştirilerek,
x/ sayısının 3, 5 ve 15'in katı olup olmadığını ayırt eden bir FizzBuzz uygulanıyor
- Örnek, okunabilirlik için
-regextype posix-extended kullanıyor; ancak aynı yaklaşımın başka regex sözdizimleriyle de mümkün olduğu belirtiliyor
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"
- İkinci satır,
d altında art arda 30 adet x içeren bir yol oluşturuyor
- Üçüncü satır,
x sayısı 15'in katıysa FizzBuzz, 5'in katıysa Buzz, 3'ün katıysa Fizz, aksi halde d'ye göre derinliği yazdırıyor
- Çalışma çıktısı OneCompiler örneğinde görülebilir
Tag system ile Turing tamlığını göstermek
- Tag system,
(m, A, P) bileşenlerinden oluşuyor
m pozitif bir tamsayıA, durma simgesi H'yi içeren sonlu bir alfabeP, her alfabe sembolü için üretim kuralı
- Başlangıç dizgesi verildiğinde sistem şu süreci tekrar ediyor
- Dizge uzunluğu
m'den küçükse veya ilk karakter H ise duruyor
- Aksi halde ilk karakter
x için P(x) dizgenin sonuna ekleniyor
- Baştaki
m karakter siliniyor
m=2, |A|=576 olan bir tag system'in evrensel Turing makinesi olduğu biliniyor; dolayısıyla bu boyuttaki bir tag system'i çalıştırabilen sistem Turing tam sayılıyor
- Pratik uygulama örneği olarak Wikipedia'daki
m=2, |A|=4 olan basit 2-tag system kullanılıyor
Durumu dosya yolu olarak kullanma yöntemi
- Temel fikir, durumu temsil eden dosya yolunun sonuna bir sonraki durumu sürekli eklemek
- Durumlar arasında ayırıcı olarak
_ kullanılıyor
- Örnek:
_/b/a/a/_
- Sonraki durum
a/c/c/a ise yol _/b/a/a/_/a/c/c/a/_ oluyor
- Çalışma sırasında herhangi bir dizinin içinde birden fazla dosya bulunmaması sağlanıyor
- Uygulama, durma simgesine rastlanana veya dizge uzunluğu
m'ye eşit ya da ondan küçük olana kadar sonraki durumu eklemeyi sürdürüyor
find koşul ifadesi genel olarak üç bölüm halinde çalışıyor
- Durma koşulu denetimi
- Back-reference kullanarak önceki durumdan ilk
M karakter çıkarıldıktan sonra kalan kısmı kopyalama
a, b, c için üretim kurallarını uygulama
- Örnek üretim kuralları şöyle
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- Çalışma sonucunda beklenen
_/H/c/c/c/c/c/c/a/_ çıktısı elde ediliyor
- Bu çalıştırmanın çıktısı da OneCompiler örneği olarak sunuluyor
Back-reference ve genişletilebilirlik
- FizzBuzz uygulaması genel regex kullanırken, tag system uygulaması back-reference
\2 kullanıyor
- Back-reference sayesinde önceki durumdan ilk
m karakter dışındaki kısım kopyalanabiliyor
- Bu yapı, daha büyük sabit boyutlu alfabelere genişletilebiliyor
- Kullanılabilecek karakterler yetersiz kalırsa, her dosya adında tek karakter yerine birden fazla karakter kullanılarak bu aşılabiliyor
- Böylece
find + mkdir birleşiminin Turing tam olduğu sonucuna varılıyor
POSIX kısıtları ve çalışma ortamı
- Dosya yolu uzunluğu sınırları yüzünden keyfi büyüklükte otomatları çalıştırmak mümkün olmayabilir; ancak sunulan kod, keyfi uzunluktaki dosya yollarını doğrudan
mkdir'e vermeyecek şekilde tasarlanmış
- Testlerde
find, 30000 karakteri aşan yollarda da çalıştı ve ek bir sınır bulunamadı
- POSIX düzeyinde bir garanti yok
- POSIX
find belgesi, arama sırasında dizine dosya eklenmesi durumundaki davranışın unspecified olduğunu açıkça belirtiyor
- GNU dışındaki araçların davranışı doğrulanmadı
- Kullanılan ortam şu şekilde
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 yorum
Hacker News yorumları
Sayfanın en üstünde zaten şöyle yazıyor: find + mkdir’in Turing tamlığı iddiası geri çekildi
Kanıtta bir kusur olduğu için find + mkdir’in Turing tam olduğunu kanıtladığı iddiasını geri çektiğini söylüyor ve https://news.ycombinator.com/item?id=41117141 bağlantısına bakılmasını istiyor
Kanıt düzeltilebilirse yazıyı güncelleyeceğini söylüyor
Bununla Folders uygulanabilir mi?
https://www.danieltemkin.com/Esolangs/Folders/
Dizin girdileri MFT içinde yer kaplar; yalnızca Explorer başka yerde ayrılmış blokları saydığı için bu görünmez
Boş dizinler oluşturmaya devam ederseniz MFT büyür ve sonunda alan sorunu çıkar
Küçük dosyalar için de benzer: boş bir metin dosyası boyut 0 bayt, disk boyutu 0 bayt olarak görünür; içine yaklaşık 400 bayt koysanız bile veri önceden ayrılmış MFT’nin dizin girdisinin içine sığar ve Explorer’da disk boyutu 0 görünür
Veriyi iki katına çıkarırsanız bir disk bloğu ayrılır; uzunluk 800 bayt, disk boyutu 4.096 bayt görünür. Sonra tekrar 400 bayta düşürseniz bile veri MFT’ye geri dönmez ve 4.096 bayt kaplamaya devam eder
Yine de genel olarak bu harika çalışmanın tadını çıkarmaya engel değil
Bunun Turing tamlığını nasıl gösterdiğini anlamıyorum
Kural 110 otomatı uygulaması hem genişlik sınırına hem de yineleme sayısı sınırına takılıyor gibi görünüyor
Verilen genişlikteki durum sayısı sonlu olduğundan Turing tam değil; her zaman sonlandığı için de yine Turing tam değil
Keyfi, yani sonsuza kadar genişletilebilir genişlik ve derinliğe sahip bir Kural 110 uygulaması yazılabilir mi?
Gerçek bilgisayarlar da sonsuz bant değil, sonlu bellek kullanır; dolayısıyla dil veya yöntem ne olursa olsun bu koşulu karşılamazlar
Kanıt düzeltilebilirse yazıyı güncelleyeceğini söylüyor
Geri çekildi
“Kanıtta bir kusur olduğu için find + mkdir’in Turing tam olduğunu kanıtladığı iddiamı geri çekiyorum” deniyor
İlginç bir lambda hesabı biçimi kullanacağını sanmıştım; gerçekte ise hesaplama için yalnızca find’ın regex ayrıştırıcısına dayanıyormuş
Aklımda kalan örneklerden biri http://realgl.blogspot.com/2013/08/battlecode.html; “Regular Expression Pathfinding” bölümüne bakın
Bu kanıt, hücresel otomat yerine etiket sistemi (https://en.m.wikipedia.org/wiki/Tag_system) kullanılırsa çok daha basit hale gelebilir gibi görünüyor
Hiçbir uygulama sonsuz olamaz, ama bu durumda tipik değeri 4096 olan PATH_MAX özellikle düşük görünüyor
GNU’da 4096’dan uzun yol uzunluklarında da çalışıyor gibi görünüyor
görünüşe göre 30k yol uzunluğuna kadar test etmişler
Regex’i (RE, RegExp) uygulayan veya tüketen yazılımlar/servisler ya da bir yazılım/servis zincirindeki bileşenler potansiyel olarak Turing tam olabilir
Bu bağlamda güvenlik önemliyse Turing tamlığı olup olmadığı denetlenmeli
Turing tamlığı elde etmek için 2 yığıt gerekir
Bununla birlikte birçok regex kütüphanesi basit “regex”ten çok daha fazla özellik destekler
Benim find’ım kanıtlanabilir biçimde Turing tam olmakla kalmıyor; Turing tarpiti de değil, yerel koda derleniyor