# `find`와 `mkdir`의 튜링 완전성

> Clean Markdown view of GeekNews topic #16116. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=16116](https://news.hada.io/topic?id=16116)
- GeekNews Markdown: [https://news.hada.io/topic/16116.md](https://news.hada.io/topic/16116.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-08-01T09:43:15+09:00
- Updated: 2024-08-01T09:43:15+09:00
- Original source: [ogiekako.vercel.app](https://ogiekako.vercel.app/blog/find_mkdir_tc)
- Points: 1
- Comments: 0

## Topic Body

### 개요

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

### 구현

#### 루프 구성

- 다음 코드는 디렉토리를 재귀적으로 생성하고 무한 루프를 만듦
  ```sh
  mkdir x
  find x -execdir mkdir x/x \;
  ```
- `find x`는 `x` 아래의 파일을 나열하고, `x`가 나열되면 `x/x`를 생성
- 디렉토리 생성 깊이를 제한하려면 `-maxdepth` 옵션을 사용
  ```sh
  mkdir x
  find x -maxdepth 3 -execdir mkdir x/x \;
  ```

#### FizzBuzz

- `find`의 `-regex` 옵션을 사용하여 파일 이름을 필터링하고, 루프와 결합하여 FizzBuzz를 구현
  ```sh
  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을 구현하여 이를 증명
  ```sh
  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 사양에 따라 작동이 보장되는가?
  - 아니며, 디렉토리 검색 중 파일이 추가되면 동작이 지정되지 않음
  - 사용된 도구 버전:
    ```sh
    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`가 있음

## Comments



_No public comments on this page._