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

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

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

483 открытий11К показов

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

483 открытий11К показов

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

Курсы по Big Data, включая онлайн-обучение для аналитиков больших данных

Самые лучшие курсы по Big Data. В предложенной подборке актуальные варианты обучения от проверенных школ, а так же рейтинги и цены на курсы для аналитиков Big Data

COBOL в Японии: почему цифровое прошлое до сих пор определяет настоящее

Узнайте, почему в Японии COBOL до сих пор основа экономики, на нём всё ещё учатся программировать и к чему привело использование такого старого языка.

Устраиваем свой Data QA с PyTest и фикстурами

Рабочий подход к тестированию трансформации данных в ETL-процессах. На примере Python-проекта с pytest, allure и psycopg2 демонстрируется, как автоматизировать создание и наполнение таблиц, хранить схемы и данные, а затем сравнивать результат.

Минцифры запускает платформу для подтверждения ИТ-навыков: пройти тесты можно бесплатно и без диплома

Минцифры запустило платформу для бесплатного подтверждения ИТ-навыков. Доступны тесты по 5 языкам программирования и 12 теоретическим темам. Успешные участники получают сертификат, видимый в резюме и на Госуслугах.