DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.36

Turing Completeness of GNU find: From mkdir-Assisted Loops to Standalone Computation

Authors: Keigo Oka

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

The Unix command find is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that find possesses unexpected computational power, establishing three Turing completeness results using the GNU implementation (a standard in Linux distributions). (1) find + mkdir is Turing complete. By encoding computational states as directory paths and using regex back-references to copy substrings, we simulate 2-tag systems using only the find and mkdir executables. (2) GNU find 4.9.0+ alone is Turing complete: by reading and writing to files during traversal, we simulate a two-counter machine without mkdir. (3) find + mkdir without regex back-references is still Turing complete: by a trick of encoding regex patterns directly into directory names, we achieve the same power. These results place find among the "surprisingly Turing-complete" systems, highlighting the hidden complexity within seemingly simple standard utilities.

Cite as

Keigo Oka. Turing Completeness of GNU find: From mkdir-Assisted Loops to Standalone Computation. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{oka:LIPIcs.FUN.2026.36,
  author =	{Oka, Keigo},
  title =	{{Turing Completeness of GNU find: From mkdir-Assisted Loops to Standalone Computation}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.36},
  URN =		{urn:nbn:de:0030-drops-257555},
  doi =		{10.4230/LIPIcs.FUN.2026.36},
  annote =	{Keywords: Turing completeness, GNU find, tag system, counter machine}
}

Document

DOI: 10.4230/LIPIcs.FUN.2026.37

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers

Authors: Keigo Oka, Naoki Inaba, and Akira Iino

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

You find a stain on the wall and decide to cover it with non-overlapping stickers of a single identical shape (rotation and reflection are allowed). Is it possible to find a sticker shape that fails to cover the stain? In this paper, we consider this problem under polyomino constraints and complete the classification of always-coverable stain shapes (polyominoes). We provide proofs for the maximal always-coverable polyominoes and construct concrete counterexamples for the minimal not always-coverable ones, demonstrating that such cases exist even among hole-free polyominoes. This classification consequently yields an algorithm to determine the always-coverability of any given stain. We also show that the problem of determining whether a given sticker can cover a given stain is NP-complete, even though exact cover is not demanded. This result extends to the 1D case where the connectivity requirement is removed. As an illustration of the problem complexity, for a specific hexomino (6-cell) stain, the smallest sticker found in our search that avoids covering it has, although not proven minimum, a bounding box of 325 × 325.

Cite as

Keigo Oka, Naoki Inaba, and Akira Iino. Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 37:1-37:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{oka_et_al:LIPIcs.FUN.2026.37,
  author =	{Oka, Keigo and Inaba, Naoki and Iino, Akira},
  title =	{{Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{37:1--37:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.37},
  URN =		{urn:nbn:de:0030-drops-257560},
  doi =		{10.4230/LIPIcs.FUN.2026.37},
  annote =	{Keywords: polyomino, covering, NP-completeness}
}

Search Results

Documents authored by Oka, Keigo

Turing Completeness of GNU find: From mkdir-Assisted Loops to Standalone Computation

Abstract

Cite as

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers

Abstract

Cite as

Thanks for your feedback!

Could not send message