GNU find가 튜링 완전하다는 증명: mkdir과 정규식의 광기

엔지니어 생활을 15년 넘게 하면서 수없이 많은 find 명령어를 쳐왔습니다. 보통은 로그 파일을 정리하거나, 잘못된 위치에 들어간 설정 파일을 찾기 위해서였죠. 우리에게 find는 그저 묵묵히 파일 시스템을 뒤지는, 지루하지만 믿음직한 도구일 뿐이었습니다.

그런데 최근 arXiv에 올라온 논문 하나가 제 커피를 뿜게 만들었습니다. 제목부터 심상치 않습니다. Turing Completeness of GNU find. 네, 맞습니다. 우리가 아는 그 find 명령어가 튜링 완전(Turing Complete)하다는 증명입니다.

오늘은 이 “광기 어린” 발견이 기술적으로 어떤 의미를 가지는지, 그리고 왜 개발자들이 이런 쓸데없어 보이는 것에 열광하는지 깊게 파고들어 보겠습니다.

그저 파일을 찾는 도구가 아니었다

이 논문의 핵심 주장은 간단합니다. GNU find 명령어의 기능들을 잘 조합하면, 이론상 모든 계산 가능한 문제 를 풀 수 있다는 것입니다. 단순히 파일을 검색하는 게 아니라, 파일 시스템 자체를 메모리(Tape)로 쓰고 find의 순회(Traversal) 기능을 CPU 사이클처럼 사용하는 것이죠.

논문에서는 세 가지 방식을 제시하는데, 그중 가장 흥미로운 메커니즘을 살펴보겠습니다.

1. 파일 시스템을 메모리로 사용하기

튜링 머신이 동작하려면 상태를 저장할 테이프가 필요합니다. 이 연구에서는 디렉토리 경로 가 그 역할을 합니다. find와 mkdir을 조합하여, 현재의 계산 상태를 디렉토리 깊이와 이름으로 인코딩합니다.

2. 무한 루프와 상태 전이

find는 기본적으로 디렉토리를 순회합니다. 그런데 만약 find가 탐색하는 도중에 새로운 디렉토리가 생성된다면 어떻게 될까요? find는 그 새로운 디렉토리도 탐색해야 합니다. 이 과정이 반복되면 무한 루프 가 만들어집니다.

연구진은 이 루프를 제어하기 위해 정규식(Regex)의 Back-reference 기능을 사용했습니다. -regex 옵션을 통해 현재 경로(상태)를 읽고, 그 패턴에 매칭될 때 -exec mkdir을 실행하여 다음 상태에 해당하는 디렉토리를 만듭니다. 즉, 파일 시스템의 상태가 다음 파일 시스템의 상태를 결정하는 Cellular Automaton 같은 구조가 되는 셈입니다.

3. 순수 find만으로도 가능하다

더 충격적인 건 GNU find 4.9.0 이상 버전부터는 mkdir 같은 외부 명령어 도움 없이, find 자체 기능만으로도 튜링 완전성을 달성했다는 점입니다. 이는 find가 순회 중에 파일에 읽고 쓰는 최적화나 기능들이 추가되면서 가능해진 것으로 보입니다. 논문에서는 이를 통해 Two-counter machine 을 시뮬레이션했습니다.

Hacker News의 반응: “그래서 둠(Doom)은 언제 돌아가죠?”

이 소식을 접한 Hacker News의 반응은 예상대로 뜨겁습니다. 한 유저는 “이론적으로 find로 둠(Doom)을 돌릴 수 있다는 소리네”라며 Doom Complete 라는 용어를 농담처럼 던졌습니다.

물론 I/O 처리가 극악이라 화면에 렌더링하는 건 불가능에 가깝겠지만, 계산 로직 자체는 구현 가능하다는 사실이 개발자들의 도전 정신을 자극하는 것 같습니다. 또 다른 유저는 “arXiv가 find 명령어를 처리하는 데 애를 먹고 있는 것 같다”며 논문 뷰어의 버그를 지적하기도 했습니다.

Accidental Turing Completeness의 위험과 매력

사실 이런 발견은 Accidental Turing Completeness (우연한 튜링 완전성)라고 불리는 현상의 전형적인 예입니다. CSS, Minecraft의 Redstone, 심지어 PowerPoint 애니메이션도 튜링 완전하다는 것이 증명된 바 있죠.

보안 관점에서 보면 이건 악몽일 수도 있습니다. 단순히 파일을 찾는 줄 알았던 명령어가, 악의적으로 조작된 디렉토리 구조 안에서는 무한 루프를 돌거나 임의의 계산을 수행하며 리소스를 고갈시킬 수 있다는 뜻이니까요. 시스템 관리자나 DevOps 엔지니어라면, 신뢰할 수 없는 입력값으로 find의 정규식 파라미터를 동적으로 생성하는 코드가 없는지 다시 한번 점검해볼 필요가 있습니다.

결론: 기술적 잉여력의 승리

솔직히 말해서, 현업에서 find로 복잡한 계산을 할 일은 죽을 때까지 없을 겁니다. 파이썬이나 Go를 놔두고 굳이 파일 시스템 I/O 병목이 걸리는 쉘 스크립트 덩어리를 쓸 이유는 없으니까요.

하지만 저는 이런 연구가 엔지니어링의 본질 을 보여준다고 생각합니다. 주어진 도구의 한계를 끝까지 밀어붙여 보는 호기심, “이게 될까?”라는 질문에 답하기 위해 밤을 새우는 집요함 말입니다.

GNU find는 이제 단순한 유틸리티가 아닙니다. 그것은 컴퓨팅 그 자체 입니다. 오늘 터미널을 열고 find를 칠 때, 잠시 경외심을 가져보는 건 어떨까요?

References: