find + mkdir are Turing complete

Introduction

We will show that a system with only GNU commands find And mkdiris Turing complete.

It is well known that teams sed And awk are Turing complete themselves, but I couldn't find any information about Turing completeness find + mkdir.

The proof is based on the implementation tag systems.

We will consider the implementation of the cycle, FizzBuzz and tag system in order.

Reference materials

Implementation

Cycle construction

The code below recursively creates folders and enters an infinite loop:

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

find x returns a list of files in xincluding x. When outputting in a list x is starting up mkdir for creation x/xwhich is then included in the next iteration findleading to the creation x/x/xand so on.

To limit the depth of folder creation, we can use the option -maxdepth:

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

This code will stop executing after creation x/x/x/x/x. Replacing 3 on N we will get N+2 folder levels x.

FizzBuzz

Option -regex teams find allows you to filter the names of files that will be subject to subsequent actions. Thanks to this, we can filter the quantities x/multiples of 3, 5 and 15, and by combining this with a loop, you can implement FizzBuzz. In the code shown below -regextype posix-extended is used for readability, but the same can theoretically be achieved with any regular expression syntax.

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"

Result of execution

The second line creates x/... /x (30 x) inside dafter which the third line displays FizzBuzzif the quantity x turns out to be a multiple of 15, Buzzif a multiple of 5, Fizzif it is a multiple of 3, otherwise the file depth relative to dthat is, the number x.

Implementation of tag system

The tag system is a triplet (m,A,P)Where

• m — is a positive integer.

• A — the final alphabet containing the stop symbol H.

• P — the generating rule for each alphabet.

Once the source string is received, the system repeatedly performs the following actions:

1. If the string length is less than m or its initial symbol x equal Hthen a stop is performed. Otherwise P(x) is added to the end.

2. The first ones are removed m characters.

and outputs a string when stopped.

It is known that there is a tag system with m=2,∣A∣=576 which implements a universal Turing machine (De Mol, L., 2008), so a system capable of handling a tag system of this size is Turing complete.

Here we use example tag systems with m=2,∣A∣=4 from Wikipedia, and we will show its implementation.

The basic idea is to iteratively append the next state file path to the state file path using a separator _. For example, if the state _/b/a/a/_ the next state is in progress a/c/c/a then the resulting path to the file will look like this _/b/a/a/_/a/c/c/a/_and this process is repeated until the system stops. Here is the execution time in the folder no more than one file is created.

# Демонстрация таг-системы с 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

Result of execution

We see that the expected result is indeed displayed. /H/c/c/c/c/c/c/a/. In the FizzBuzz implementation we used regular expressions, but here, as you can see, we use backreferences (\2), thanks to which it is possible to copy the previous state without the first m characters.

Obviously, this construction can be extended to a larger (unchanging) alphabet size. (The problem of running out of characters can easily be solved by giving each file a name of several characters.)

Hence, find + mkdir Turing complete.

Expected questions and answers to them

• Is it possible that we cannot execute an arbitrary size automaton due to file path length limitations?

  • I don't think so. mkdir will fail if passed a path to a file of a certain length or longer, but in the code we carefully avoid passing it directly mkdir paths to files of arbitrary length. According to my tests, find It works even when the paths are longer than 30000, and I couldn't find the limit.

• Does the POSIX specification guarantee that this code will work?

  • Unfortunately, no. It clearly states that the behavior is not covered by the specification if a file is added to a directory that is searched at runtime (source). I have not tested the behavior of any tools other than GNU.

  • I used the following versions of the tools:

-> % 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