Ciro Santilli
OurBigBook.comThe dominating model of a computer.
The model is extremely simple, but has been proven to be able to solve all the problems that any reasonable computer model can solve, thus its adoption as the "default model".
The smallest known Turing machine that cannot be proven to halt or not as of 2019 is 7,918-states: www.scottaaronson.com/blog/?p=2725. Shtetl-Optimized by Scott Aaronson is just the best website.
A bunch of non-reasonable-looking computers have also been proven to be Turing complete for fun, e.g. Magic: The Gathering.
Ancestors
Incoming links
- Automated theorem proving by halting problem reduction
- Busy beaver function
- Busy beaver scale
- Primitive recursive function
- R
- Recursively enumerable language
- The beauty of mathematics
- Turing complete
- Turing machine decider
- Turing machine regex tape notation
- Undecidability requires infinitely many inputs
- Undecidable problem