Turing machine Updated +Created
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: 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.
Formal language theory Updated +Created
Computer scientist Updated +Created
Cryptography Updated +Created
Hash function Updated +Created
Applications:
Computer science bibliography Updated +Created