GNU Find의 튜링 완전성: Mkdir‑지원 루프에서 독립 실행형 Comput까지

Source: Hacker News

Abstract

Unix 명령어 find는 초보자에게 가장 먼저 가르치는 명령어 중 하나이지만, 숙련된 엔지니어에게도 여전히 없어서는 안 될 도구입니다. 본 논문에서는 find가 예상치 못한 계산 능력을 가지고 있음을 보여주며, GNU 구현(리눅스 배포판에서 표준으로 사용)을 이용한 세 가지 튜링 완전성 결과를 제시합니다.

1. find + mkdir (오직 find와 mkdir만을 갖는 시스템)는 튜링 완전합니다: 계산 상태를 디렉터리 경로로 인코딩하고 정규식 백레퍼런스를 이용해 부분 문자열을 복사함으로써 2‑tag 시스템을 시뮬레이션합니다.
2. GNU find 4.9.0+ 단독도 튜링 완전합니다: 탐색 중 파일을 읽고 쓰는 방식을 통해 mkdir 없이 두 카운터 기계를 시뮬레이션합니다.
3. 정규식 백레퍼런스 없이 find + mkdir 역시 튜링 완전합니다: 정규식 패턴을 디렉터리 이름에 직접 인코딩하는 트릭을 사용해 동일한 계산 능력을 얻습니다.

이 결과들은 find를 “놀랍게도 튜링 완전한” 시스템 중 하나로 자리매김하게 하며, 겉보기에는 단순해 보이는 표준 유틸리티 안에 숨겨진 복잡성을 강조합니다.