GNU find의 튜링 완전성

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를 “놀랍도록 튜링 완전한” 시스템 중 하나로 자리매김하게 하며, 겉보기에는 단순해 보이는 표준 유틸리티 안에 숨겨진 복잡성을 강조합니다.

Subjects

• Data Structures and Algorithms (cs.DS)

Citation

• arXiv:2602.20762 (cs.DS)
• (or arXiv:2602.20762v1 (cs.DS) for this version)

DOI

https://doi.org/10.48550/arXiv.2602.20762

Submission history

From: Keigo Oka view email

[v1] Tue, 24 Feb 2026 10:41:47 UTC (18 KB)