find + mkdir полны по Тьюрингу

Введение

Мы покажем, что система, имеющая лишь команды GNU find и mkdir, полна по Тьюрингу.

Хорошо известно, что команды sed и awk сами по себе полны по Тьюрингу, но мне не удалось найти информации о Тьюринг-полноте find + mkdir.

Доказательство основано на реализации таг-системы.

Мы по порядку рассмотрим реализацию цикла, FizzBuzz и таг-системы.

Справочные материалы

• https://manpages.org/find

• https://manpages.org/mkdir

Реализация

Конструкция цикла

Показанный ниже код рекурсивно создаёт папки и входит в бесконечный цикл:

mkdir x
find x -execdir mkdir x/x ;

find x возвращает список файлов в x, включая x. При выводе в списке x запускается mkdir для создания x/x, которая затем включается в следующую итерацию find, приводя к созданию x/x/x, и так далее.

Чтобы ограничить глубину создания папок, мы можем использовать опцию -maxdepth:

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

Этот код прекратит выполнение после создания x/x/x/x/x. Заменив 3 на N , мы получим N+2 уровней папок x.

FizzBuzz

Опция -regex команды find позволяет фильтровать имена файлов, которые будут подвергаться последующим действиям. Благодаря этому мы можем отфильтровать количества x/, кратные 3, 5 и 15, а объединив это с циклом, можно реализовать FizzBuzz. В показанном ниже коде -regextype posix-extended используется для удобства чтения, но то же самое теоретически можно реализовать с любым синтаксисом регулярных выражений.

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 "FizzBuzzn" -o 
-regex 'd((/x){5})+' -printf "Buzzn" -o 
-regex 'd((/x){3})+' -printf "Fizzn" -o 
-regex 'd(/x)+' -printf "%dn"

Результат исполнения

Во второй строке создаётся x/... /x (30 x) внутри d, после чего в третьей строке выводится FizzBuzz, если количество x оказывается кратным 15, Buzz, если кратным 5, Fizz, если кратным 3, а в противном случае — глубина файла относительно d, то есть количество x.

Реализация таг-системы

Таг-система — это триплет (m,A,P), где

• m — это положительное целое число.

• A — конечный алфавит, содержащий символ останова H.

• P — порождающее правило для каждого алфавита.

Получив исходную строку, система многократно выполняет следующие действия:

1. Если длина строки меньше m или её начальный символ x равен H, то выполняется останов. В противном случае P(x) добавляется в конец.

2. Удаляются первые m символов.

и выводит строку в случае останова.

Известно, что существует таг-система с m=2,∣A∣=576 , в которой реализована универсальная машина Тьюринга (De Mol, L., 2008), поэтому система, способная работать с таг-системой такого размера, полна по Тьюрингу.

Здесь мы используем пример таг-системы с m=2,∣A∣=4 из Википедии, и покажем его реализацию.

Базовая идея заключается в итеративном добавлении описывающего следующее состояние пути до файла к описывающему состоянию пути до файла при помощи разделителя _. Например, если за состоянием _/b/a/a/_ идёт следующее состояние a/c/c/a , то получившийся путь до файла будет иметь вид _/b/a/a/_/a/c/c/a/_, и этот процесс повторяется, пока система не выполнит останов. Вот время исполнения в папке создаётся не больше одного файла.

# Демонстрация таг-системы с m=2, реализованной при помощи только `find` и `mkdir`,
# на основе примера из Википедии.
# en.wikipedia.org/wiki/Tag_system#Example:_A_simple_2-tag_illustration
# '_' используются как разделители между состояниями.
mkdir _
# Порождающие правила для таг-системы, задаваемые как константы.
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
# Исходное состояние (окружённое _).
mkdir -p /b/a/a/
# Алфавиты (постоянного размера)
S="(/[abcH])"
# Продолжаем добавлять следующее состояние в конец состояния, пока не встретим символ останова
# /b/a/a/ -> /b/a/a//a/c/c/a/_ -> /b/a/a//a/c/c/a//c/a/c/c/b/a/H/ -> ... -> ...//H/c/c/c/c/c/c/a/ (halt)
#
# Строка 2:    условие останова
# Строки 3-6:  копируем предыдущее состояние, удаляя M символов из начала благодаря использованию обратных ссылок.
# Строки 7-29: применяем порождающее правило для a, b, c.
find _ -regextype posix-extended -empty ( 
-regex "._/H.|.*(/[^/]?){, -prune -o 
    -regex ".*_" class="formula inline">S{" class="formula inline">S)/a ( -execdir mkdir a/a b/a c/a H/a _/a ; -o -true ) -o 
    -regex ".*_" class="formula inline">S{" class="formula inline">S)/b ( -execdir mkdir a/b b/b c/b H/b _/b ; -o -true ) -o 
    -regex ".*_" class="formula inline">S{" class="formula inline">S)/c ( -execdir mkdir a/c b/c c/c H/c _/c ; -o -true ) -o 
    -regex ".*_" class="formula inline">S{" class="formula inline">S)/H ( -execdir mkdir a/H b/H c/H H/H _/H ; -o -true ) -o 
    ( 
        -regex ".*_/a" class="formula inline">S/ ( 
            -execdir find a ; -execdir mkdir -p a/" class="formula inline">PROD_A/ ; -o 
-execdir find b ; -execdir mkdir -p b/mkdir -p c/" class="formula inline">PROD_A/_ ; -o 
-execdir find H ; -execdir mkdir -p H/mkdir -p _/" class="formula inline">PROD_A/_ ; 
) -o 
-regex "./b" class="formula inline">S*" ( 
-execdir find a ; -execdir mkdir -p a/mkdir -p b/" class="formula inline">PROD_B/ ; -o 
-execdir find c ; -execdir mkdir -p c/mkdir -p H/" class="formula inline">PROD_B/_ ; -o 
-execdir find _ ; -execdir mkdir -p /".*_/c" class="formula inline">S*/ ( 
            -execdir find a ; -execdir mkdir -p a/" class="formula inline">PROD_C/_ ; -o 
-execdir find b ; -execdir mkdir -p b/mkdir -p c/" class="formula inline">PROD_C/_ ; -o 
-execdir find H ; -execdir mkdir -p H/mkdir -p _/" class="formula inline">PROD_C/_ ; 
) 
) 
) &> /dev/null
# Выводим результат. (/H/c/c/c/c/c/c/a/)
find _ -depth ! -empty -name _ -execdir find _ -empty ; -quit

Результат исполнения

Мы видим, что действительно выводится ожидаемый результат /H/c/c/c/c/c/c/a/. В реализации FizzBuzz использовались обычные регулярные выражения, а здесь, как можно заметить, мы используем обратные ссылки (2), благодаря чему можно копировать предыдущее состояние без первых m символов.

Очевидно, что эту конструкцию можно расширить до большего размера алфавита (неизменного). (Проблему нехватки символов можно легко решить, давая каждому файлу имя из нескольких символов.)

Следовательно, find + mkdir полны по Тьюрингу.

Ожидаемые вопросы и ответы на них

• Возможно ли, что мы не сможем выполнить автомат произвольного размера из-за ограничений на длину пути до файлов?

  • Не думаю, что это так. mkdir завершится сбоем, если передать ей путь до файла определённой длины или длиннее, но в коде мы тщательно избегаем передачи непосредственно mkdir путей до файлов произвольной длины . Судя по моим тестам, find работает, даже когда пути длиннее 30000, и предела мне найти не удалось.

• Гарантирует ли спецификация POSIX работу этого кода?

  • К сожалению, нет. В ней чётко говорится, что поведение не охватывается спецификацией, если файл добавляется в папку, поиск по которой происходит во время исполнения (источник). Я не проверял поведение никаких других инструментов, кроме GNU.

  • Я использовал следующие версии инструментов:

-> % find --version | head -1 && mkdir --version | head -1 && uname -a
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