Lemmy: Bestiverse
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS BotMB to Hacker NewsEnglish · 2 months ago

Turing Completeness of GNU Find: From Mkdir-Assisted Loops to Standalone Comput

arxiv.org

external-link
message-square
0
link
fedilink
4
external-link

Turing Completeness of GNU Find: From Mkdir-Assisted Loops to Standalone Comput

arxiv.org

RSS BotMB to Hacker NewsEnglish · 2 months ago
message-square
0
link
fedilink
Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation
arxiv.org
external-link
The Unix command \texttt{find} is among the first commands taught to beginners, yet remains indispensable for experienced engineers. In this paper, we demonstrate that \texttt{find} possesses unexpected computational power, establishing three Turing completeness results using the GNU implementation (a standard in Linux distributions). (1) \texttt{find} + \texttt{mkdir} (a system that has only \texttt{find} and \texttt{mkdir}) is Turing complete: by encoding computational states as directory paths and using regex back-references to copy substrings, we simulate 2-tag systems. (2) GNU \texttt{find} 4.9.0+ alone is Turing complete: by reading and writing to files during traversal, we simulate a two-counter machine without \texttt{mkdir}. (3) \texttt{find} + \texttt{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 \texttt{find} among the ``surprisingly Turing-complete'' systems, highlighting the hidden complexity within seemingly simple standard utilities.

Comments

alert-triangle
You must log in or # to comment.

Hacker News

hackernews

Subscribe from Remote Instance

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !hackernews@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

Posts from the RSS Feed of HackerNews.

The feed sometimes contains ads and posts that have been removed by the mod team at HN.

Source of the RSS Bot

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 585 users / day
  • 2.15K users / week
  • 4.38K users / month
  • 9.65K users / 6 months
  • 2 local subscribers
  • 4.7K subscribers
  • 48.7K Posts
  • 25K Comments
  • Modlog
  • mods:
  • patrick
  • RSS Bot
  • BE: 0.19.15
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org