{c}
{wiki}

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[]. https://www.scottaaronson.com/[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>.


Turing machine

Formal language theory

{wiki}

The list: https://complexityzoo.uwaterloo.ca/Complexity_Zoo


Computational problem

Computer scientist

Cryptography

{wiki}

= Hash
{synonym}

Applications:
* https://en.wikipedia.org/wiki/Hash_table[hash map] which is a O(1) amortized implementation of a map
* creating unbreakable chains of data, e.g. for https://stackoverflow.com/questions/22968856/what-is-the-file-format-of-a-git-commit-object-data-structure/37438460#37438460[Git commits] or <Bitcoin>. 
* storing passwords on a server in a way that if the password database is stolen, attackers can't reuse them on other websites where the user used the same password: https://security.blogoverflow.com/2013/09/about-secure-password-hashing/


Hash function

Computer science bibliography

{wiki}

A branch of <mathematics> that attempts to prove stuff about <computers>.

Unfortunately, all <software engineers> already know the answer to the useful theorems though (except perhaps notably for <cryptography>), e.g. all programmers obviously know that iehter <p versus NP problem>[P != NP] or that this is <independence (mathematical logic)>[unprovable or some other "for all practical purposes practice P != NP"], even though they don't have proof.

And 99% of their time, software engineers are not dealing with mathematically formulatable problems anyways, which is sad.

The only useful "computer science" subset every programmer ever needs to know is:
* for arrays: <dynamic array> vs <linked list>
* for <associative array>: <binary search tree> vs <hash table>. See also https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst/29548834#29548834[Heap vs Binary Search Tree (BST)]. No need to understand the algorithmic details of the hash function, the <NSA> has already done that for you.
* don't use https://en.wikipedia.org/wiki/Bubble_sort[Bubble sort] for sorting
* you can't parse HTML with regular expressions: https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454[] because of <formal language theory>

Funnily, due to the <formalization of mathematics>, <mathematics> can be seen as a branch of computer science, just like computer science can be seen as a branch of Mathematics!


Ciro Santilli @cirosantilli 37

 Children: Computer science