> The theory of what can be computed versus what cannot. A mathematical problem is _computable_ if it can be solved in principle by a computing device - [[Regular Expressions]] - [[DFA]] - [[Turing Machine]] - [[Turing Complete]] - [[Halting Problem]] - [[NP Hard Problems]] - [[Entscheidungsproblem]] - computability determines if a problem can even be solved by a [[💽 COMPUTER ENGINEERING|Computer]] in the very 1st place - [[Halting Problem]] for example simply can't be solved - moreover, there are classes of problems that are technically solvable, but take too much memory or time (# steps) to solve, we analyze this in [[Complexity Theory]] https://cs.stackexchange.com/questions/47383/what-is-the-difference-between-complexity-theory-and-computability-theory https://plato.stanford.edu/entries/computability/ https://www.coursera.org/learn/cs-algorithms-theory-machines/lecture/7Fk8M/overview