alt Hacker NewsFor 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.
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!