- Mesmo usando apenas
find e mkdir do GNU, é possível criar loops e transições de estado usando a criação de diretórios e a ordem de percurso, transformando uma simples combinação de utilitários de arquivos em um modelo computacional
- A prova é feita por meio da implementação de um sistema de tags (tag system); a primeira versão da prova baseada na Rule 110 foi corrigida por causa de um problema no tratamento de repetições infinitas
- O loop básico tem a estrutura em que
find x -execdir mkdir x/x \; continua descobrindo novos diretórios, e adicionar -regex permite até desvios condicionais como FizzBuzz
- A implementação do sistema de tags representa o estado como um caminho de arquivo e usa retroreferências (back-references) para copiar o restante após remover os primeiros
m caracteres
- Como o POSIX deixa como unspecified o comportamento quando arquivos são adicionados a um diretório que está sendo pesquisado, a conclusão depende do comportamento observado das ferramentas GNU e do ambiente apresentado
Construindo um modelo computacional com GNU find e mkdir
- O objetivo é mostrar que um sistema que tem apenas os comandos
find e mkdir do GNU é Turing-completo
- A prova é conduzida implementando um sistema de tags
- O fluxo geral segue a ordem: construção de loops, FizzBuzz e implementação do sistema de tags
- Em 2 de agosto de 2024, foi corrigido um erro na primeira versão da prova baseada na Rule 110, e a versão atual passou a usar a implementação de um sistema de tags
- A primeira versão tinha o problema de não conseguir tratar um número infinito de repetições
- O artigo relacionado Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation foi aceito na FUN with Algorithms 2026
Loops criados pela criação de diretórios
- O código abaixo cria diretórios recursivamente e entra em um loop infinito
mkdir x
find x -execdir mkdir x/x \;
find x lista os arquivos sob x, incluindo o próprio x- Quando
x é listado, mkdir cria x/x, e na iteração seguinte de find o novo x/x passa a ser incluído
- À medida que esse processo se repete, caminhos como
x/x/x e x/x/x/x continuam sendo criados
- Usar a opção
-maxdepth permite limitar a profundidade de criação
mkdir x
find x -maxdepth 3 -execdir mkdir x/x \;
- Esse exemplo cria
x/x/x/x/x e então termina
FizzBuzz implementado com find -regex
- A opção
-regex do find permite filtrar os nomes de arquivos que serão alvo das ações seguintes
- Combinando esse filtro com o loop, implementa-se um FizzBuzz que determina se a quantidade de
x/ é múltipla de 3, 5 ou 15
- O exemplo usa
-regextype posix-extended para facilitar a leitura, mas considera-se que a mesma abordagem também é possível com outras sintaxes de expressões regulares
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"
- A segunda linha cria, sob
d, um caminho com 30 ocorrências consecutivas de x
- A terceira linha imprime
FizzBuzz se a quantidade de x for múltipla de 15, Buzz se for múltipla de 5, Fizz se for múltipla de 3 e, nos demais casos, a profundidade a partir de d
- O resultado da execução pode ser visto no exemplo do OneCompiler
Demonstrando completude de Turing com um sistema de tags
- Um sistema de tags é composto por
(m, A, P)
m é um inteiro positivoA é um alfabeto finito que inclui o símbolo de parada HP são as regras de produção de cada símbolo do alfabeto
- Dada uma string inicial, o sistema repete o seguinte processo
- Para se o comprimento da string for menor que
m ou se o primeiro caractere for H
- Caso contrário, adiciona
P(x) ao final da string para o primeiro caractere x
- Remove os primeiros
m caracteres
- Sabe-se que um sistema de tags com
m=2 e |A|=576 é uma máquina de Turing universal, e um sistema capaz de executar um sistema de tags desse tamanho é Turing-completo
- O exemplo real de implementação usa o 2-tag system simples da Wikipedia, com
m=2 e |A|=4
Usando caminhos de arquivos como estado
- A ideia central é continuar anexando o próximo estado ao caminho de arquivo que representa o estado
- Usa-se
_ como separador entre estados
- Ex.:
_/b/a/a/_
- Se o próximo estado for
a/c/c/a, o caminho se torna _/b/a/a/_/a/c/c/a/_
- A construção garante que, durante a execução, não haja mais de um arquivo dentro de um mesmo diretório
- A implementação continua adicionando o próximo estado até encontrar o símbolo de parada ou até que o comprimento da string se torne menor ou igual a
m
- A expressão condicional do
find funciona em três grandes partes
- Verificação da condição de parada
- Cópia do restante, depois de remover os primeiros
M caracteres do estado anterior, usando retroreferência
- Aplicação das regras de produção para
a, b e c
- As regras de produção do exemplo são as seguintes
M=2
PROD_A="c/c/b/a/H"
PROD_B="c/c/a"
PROD_C="c/c"
- Como resultado da execução, espera-se a saída
_/H/c/c/c/c/c/c/a/_
- Esse resultado de execução também é fornecido como exemplo do OneCompiler
Retroreferências e possibilidade de expansão
- A implementação do FizzBuzz usa expressões regulares comuns, mas a implementação do sistema de tags usa a retroreferência
\2
- Graças às retroreferências, é possível copiar a parte do estado anterior excluindo os primeiros
m caracteres
- Essa construção pode ser expandida para alfabetos de tamanho constante maior
- Se os caracteres disponíveis forem insuficientes, isso pode ser contornado usando mais de um caractere em cada nome de arquivo
- Portanto, chega-se à conclusão de que a combinação
find + mkdir é Turing-completa
Restrições POSIX e ambiente de execução
- Por causa do limite de comprimento de caminhos de arquivo, pode ser impossível executar autômatos de tamanho arbitrário, mas o código apresentado foi construído de modo a não passar diretamente ao
mkdir caminhos de arquivo de comprimento arbitrário
- Nos testes,
find funcionou mesmo com caminhos de mais de 30000 caracteres, e nenhum limite adicional foi encontrado
- Não há garantia pela especificação POSIX
- A documentação POSIX de
find afirma que o comportamento é unspecified quando arquivos são adicionados a um diretório que está sendo pesquisado
- O comportamento de ferramentas que não sejam GNU não foi verificado
- O ambiente usado foi o seguinte
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
1 comentários
Comentários do Hacker News
No topo da página já está escrito: a alegação de completude de Turing de find + mkdir foi retirada
Diz que, devido a uma falha na prova, a alegação de ter provado que find + mkdir é Turing-completo foi retirada, e pede para ver https://news.ycombinator.com/item?id=41117141
Também diz que atualizarão o texto se conseguirem corrigir a prova
Dá para implementar Folders com isso?
https://www.danieltemkin.com/Esolangs/Folders/
Entradas de diretório ocupam espaço na MFT, mas o Explorer só conta blocos alocados em outro lugar, então isso simplesmente não aparece
Se você continuar criando diretórios vazios, a MFT cresce e eventualmente haverá problema de espaço
Arquivos pequenos são parecidos: um arquivo de texto vazio aparece com tamanho 0 bytes e tamanho em disco 0 bytes, e mesmo colocando cerca de 400 bytes, os dados cabem na entrada de diretório pré-alocada da MFT, então no Explorer ainda aparece como tamanho em disco 0
Se você dobrar os dados, um bloco de disco é alocado e ele passa a aparecer com comprimento de 800 bytes e tamanho em disco de 4.096 bytes; se depois reduzir de novo para 400 bytes, os dados não voltam para a MFT e ele continua ocupando 4.096 bytes
Ainda assim, isso não atrapalha aproveitar o resultado excelente como um todo
Não entendo como isso mostra completude de Turing
A implementação do autômato de regra 110 parece esbarrar tanto num limite de largura quanto num limite de número de iterações
O número de estados para uma largura dada é finito, então não é Turing-completo, e como sempre termina, também não é Turing-completo
É possível escrever uma implementação de regra 110 com largura e profundidade arbitrárias, ou seja, infinitamente expansíveis?
Computadores reais também usam memória finita, não uma fita infinita, então essa condição não é satisfeita independentemente da linguagem ou método
Também diz que atualizará o texto se conseguir corrigir a prova
Retirado
Está escrito: “devido a uma falha na prova, retiro a alegação de que provei que find + mkdir é Turing-completo”
Achei que saberia usar uma forma interessante de cálculo lambda, mas na prática só dependia do parser de expressões regulares do find para fazer a computação
Um exemplo memorável é http://realgl.blogspot.com/2013/08/battlecode.html; basta ver a parte “Regular Expression Pathfinding”
Acho que essa prova ficaria muito mais simples usando um sistema de tags (https://en.m.wikipedia.org/wiki/Tag_system) em vez de um autômato celular
Nenhuma implementação pode ser infinita, mas neste caso o PATH_MAX, cujo valor comum é 4096, parece especialmente baixo
No GNU, aparentemente funciona mesmo com comprimentos de caminho maiores que 4096
Aparentemente, dizem ter testado até 30k de comprimento de caminho
Software/serviços que implementam ou consomem regex (RE, RegExp), ou componentes dentro de uma cadeia de software/serviços, podem ser potencialmente Turing-completos
Nesse contexto, se segurança for importante, vale auditar se há completude de Turing
Para obter completude de Turing, seriam necessárias duas pilhas
Mas muitas bibliotecas de regex suportam muito mais recursos do que uma simples “expressão regular”
O meu find não só é comprovadamente Turing-completo, como também não é um Turing tarpít e ainda compila para código nativo