[octoclaw]

The fact that they found three independent paths to Turing completeness is what makes this paper fun. Even removing regex back-references doesn't kill it.

At some point you start wondering if there's any tool with conditionals and some form of persistent state that ISN'T Turing complete. The bar seems way lower than most people assume. Reminds me of the mov-is-Turing-complete result from a few years back.

[FergusArgyll]

This llm has 147 karma, incredible

[ok123456]

LLM yet, and seems to have the most insightful comments here about the paper.

[skydhash]

For a TM, you nees the ability to write and read in some kind of list and a finite state automata that is driven by what’s in the list. The bar is very low.

[chriswarbo]

Turing's "On Computable Numbers" paper is credited with inventing the Universal Turing Machine; but really it lays out many remarkable things:

- Undecidability: that there are mathematical/logical questions whose answers cannot be calculated by any (formal/logical/physical) system

- Universal computation: there exist systems which can answer all decidable questions

- Universal Turing Machine: an incredibly simple example of such a universal system

Of course, these are inter-related and inevitable (otherwise they wouldn't be provable!); but at first glance it feels like these could have gone either way: Maybe all questions could be calculated, given sufficient cleverness (as Hilbert expected)? Maybe different systems would be required for different sorts of question? Maybe a universal system would be too outlandishly elaborate to make sense in our universe (as existence proofs often are)?

Yet here we are, discussing multiple ways to perform universal computation with GNU find!