Вот это поворот: комбинация команд find и mkdir из GNU оказалась тьюринг-полной

Использование команд find и mkdir в bash-скриптах позволяет реализовать сложные алгоритмы и вычисления. Узнайте, как эти команды помогают достигать новых высот в программировании.

Новости Tproger

В мире программирования команды find и mkdir из пакета GNU давно используются для управления файловой системой.

Однако недавнее открытие показало, что сочетание этих команд может достичь тьюринг-полноты. Это означает, что они способны имитировать поведение любой другой вычислительной системы, включая выполнение сложных алгоритмов и программ.

Доказательство

Исследователи показали тьюринг-полноту комбинации команд find и mkdir с помощью реализации систем тегов (tag systems).

Система тегов — это триплет (m, A, P), где m — положительное целое число, A — конечный алфавит, включающий символ завершения H, и P — правило производства для каждого символа алфавита.

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

Простейшая демонстрация заключается в создании бесконечного цикла:

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

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

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

Пример FizzBuzz

Используя опцию -regex команды find, можно фильтровать имена файлов и выполнять действия в зависимости от результата:

			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"

Этот код создает иерархию каталогов, где выводится FizzBuzz, если количество каталогов кратно 15, Buzz — если кратно 5, Fizz — если кратно 3, и количество каталогов в противном случае.

Реализация систем тегов

Системы тегов — это пример, показывающий, как можно реализовать тьюринг-полный механизм с помощью команд find и mkdir. В данном примере используется система тегов с m = 2 и алфавитом из четырех символов.

			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])"

find _ -regextype posix-extended -empty -a \( \
    -regex ".*_/H.*_|.*_(/.)?/_" -prune -o \
    -regex ".*_$S{$M}($S*)/a$S*/_\2" \( -execdir mkdir a/a b/a c/a H/a _/a \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/b$S*/_\2" \( -execdir mkdir a/b b/b c/b H/b _/b \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/c$S*/_\2" \( -execdir mkdir a/c b/c c/c H/c _/c \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/H$S*/_\2" \( -execdir mkdir a/H b/H c/H H/H _/H \; -o -true \) -o \
    \( \
        -regex ".*_/a$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_A/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_A/_ \; -о \
            -execdir find c \; -execdir mkdir -п c/$PROD_A/_ \; -о \
            -execdir find H \; -execdir mkdir -п H/$PROD_A/_ \; \
        \) -o \
        -regex ".*_/b$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -п a/$PROD_B/_ \; -о \
            -execdir find b \; -execdir mkdir -п b/$PROD_B/_ \; -о \
            -execdir find c \; -execdir mkdir -п c/$PROD_B/_ \; -о \
            -execdir find H \; -execdir mkdir -п H/$PROD_B/_ \; \
        \) -о \
        -regex ".*_/c$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -п a/$PROD_C/_ \; -о \
            -execdir find b \; -execdir mkdir -п b/$PROD_C/_ \; -о \
            -execdir find c \; -execdir mkdir -п c/$PROD_C/_ \; -о \
            -execdir find H \; -execdir mkdir -п H/$PROD_C/_ \; \
        \) \
    \) \
\) &> /dev/null

find _ -regextype posix-extended -regex ".*_/H" -execdir find H -empty -printf "%h\n" \;

Этот код демонстрирует, как с помощью комбинации команд find и mkdir можно реализовать тьюринг-полную систему тегов.