GN⁺: `find`와 `mkdir`의 튜링 완전성

개요

• GNU의 find와 mkdir 명령어만으로 시스템이 튜링 완전함을 증명하려는 시도
• sed와 awk 명령어는 튜링 완전함이 잘 알려져 있지만, find와 mkdir의 튜링 완전성에 대한 참고 자료는 없음
• 증명은 Rule 110을 실행할 수 있음을 보여주는 일반적인 기법을 활용
• 루프, FizzBuzz, Rule 110의 구현 순서로 설명

구현

루프 구성

• 다음 코드는 디렉토리를 재귀적으로 생성하고 무한 루프를 만듦

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

• find x는 x 아래의 파일을 나열하고, x가 나열되면 x/x를 생성
• 디렉토리 생성 깊이를 제한하려면 -maxdepth 옵션을 사용

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

FizzBuzz

• find의 -regex 옵션을 사용하여 파일 이름을 필터링하고, 루프와 결합하여 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"
  

Rule 110 구현

• 루프와 조건 분기를 사용할 수 있게 되면 임의의 프로그램을 작성 가능
• 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 \;
  

예상 질문과 답변

• 파일 경로 길이 제한으로 인해 임의 크기의 오토마타를 실행할 수 없는가?

  • mkdir는 특정 길이 이상의 파일 경로를 전달하면 실패하지만, 위 코드는 이를 피함
  • find는 30000 이상의 경로에서도 작동함

• 위 코드가 POSIX 사양에 따라 작동이 보장되는가?

  • 아니며, 디렉토리 검색 중 파일이 추가되면 동작이 지정되지 않음
  • 사용된 도구 버전:

    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
    

GN⁺의 정리

• find와 mkdir 명령어만으로 튜링 완전성을 증명하려는 시도는 흥미로움
• Rule 110의 구현을 통해 이를 증명하려는 접근 방식은 창의적임
• POSIX 사양에 따른 동작 보장은 없지만, GNU 도구에서는 성공적으로 작동함
• 비슷한 기능을 가진 프로젝트로는 sed와 awk가 있음