Ciro Santilli
🔗

Turing machine | 🗖 nosplit | ↑ parent "Computer science" | 90, 2, 165

🔗
The 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: https://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.
🔗
🔗