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

Новости Отредактировано

Как ни странно, даже самые простые команды вроде find и mkdir в bash-скриптах могут скрывать в себе неожиданные секреты

334 открытий6К показов

В мире программирования команды 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 можно реализовать тьюринг-полную систему тегов.

334 открытий6К показов

Также рекомендуем

В Steam началась распродажа игр для программистов в честь Ады Лавлейс — первого в мире разработчика

Steam запускает распродажу игр для программистов в честь Дня Ады Лавлейс с 7 по 14 октября. В акции представлены игры, стимулирующие изучение программирования и инженерии

Stack Overflow: «80% разработчиков несчастны». Как так вышло?

Есть популярный миф, что работа программистом — это про написание кода 2-3 часа в день, а остальное время свободное. Но данные свежего опроса показали иную картину

Библиотека программиста: 37 книг для того, чтобы разобраться в IT

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

На каком языке писать сайт в 2024 году

Сергей Немчинский обсуждает выбор технологий для создания сайта в 2024 году и рассматривает фронтенд- и бэкенд-технологии.