A completude de Turing de `find` e `mkdir`

Visão geral

• Uma tentativa de provar que o sistema é Turing-completo usando apenas os comandos find e mkdir do GNU
• Comandos como sed e awk são amplamente conhecidos por serem Turing-completos, mas não há materiais de referência sobre a completude de Turing de find e mkdir
• A demonstração usa a técnica geral de mostrar que é possível executar o Rule 110
• A explicação segue a ordem: loops, FizzBuzz e implementação do Rule 110

Implementação

Construção de loops

• O código abaixo cria diretórios recursivamente e forma um loop infinito

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

• find x lista os arquivos abaixo de x e, quando x é listado, cria x/x
• Para limitar a profundidade de criação dos diretórios, use a opção -maxdepth

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

FizzBuzz

• Usa a opção -regex do find para filtrar nomes de arquivos e a combina com loops para implementar FizzBuzz

  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"
  

Implementação do Rule 110

• Quando é possível usar loops e desvios condicionais, torna-se possível escrever programas arbitrários
• Isso é demonstrado implementando o Rule 110

  WIDTH=16
  ITER=15
  mkdir -p p/0/0/0/0/0/0/0/0/0/0/0/0/0/0/0/1
  O='(/?1)'
  Z='(/?[0p])'
  X='(/?[01p])'
  W0="($X{$WIDTH})"
  W1="($X$W0)"
  W2="($X$W1)"
  ZERO="($Z$Z$Z|$O$Z$Z|$O$O$O)"
  ONE="($O$O$Z|$O$Z$O|$Z$O$O|$Z$O$Z|$Z$Z$O)"
  find p -regextype posix-extended \
  -regex "$W1$W2{$ITER}" -fprint /dev/null \
  -o -regex "$W1$W2{0,$ITER}" \( -execdir mkdir 0/p 1/p \; -o -execdir mkdir 0/p/p 1/p/p \; \) \
  -o -regex "$W2*" -fprint /dev/null \
  -o -regex "$X*$ZERO$W0" -execdir mkdir 0/0 1/0 p/0 \; \
  -o -regex "$X*$ONE$W0" -execdir mkdir 0/1 1/1 p/1 \; \
  2> /dev/null
  find p -regextype posix-extended \
  -regex "p$W2{0,$ITER}" -execdir find p -mindepth $WIDTH -maxdepth $WIDTH \;
  

Perguntas e respostas esperadas

• Não seria impossível executar um autômato de tamanho arbitrário por causa do limite de comprimento do caminho de arquivo?

  • mkdir falha ao receber um caminho de arquivo acima de certo comprimento, mas o código acima evita isso
  • find funciona mesmo com caminhos acima de 30000

• O funcionamento do código acima é garantido pela especificação POSIX?

  • Não; se arquivos forem adicionados durante a busca em diretórios, o comportamento não é especificado
  • Versões das ferramentas usadas:

    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
    

Resumo do GN⁺

• A tentativa de provar a completude de Turing usando apenas os comandos find e mkdir é interessante
• A abordagem de demonstrar isso por meio da implementação do Rule 110 é criativa
• Embora não haja garantia de comportamento pela especificação POSIX, isso funciona com sucesso nas ferramentas GNU
• Projetos com funcionalidade parecida incluem sed e awk