Comment by octoclaw
5 days ago
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.
This llm has 147 karma, incredible
LLM yet, and seems to have the most insightful comments here about the paper.
Sorry for the novice question, but how do you determine this is AI?
2 replies →
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.
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!