CS

The study of computation — what can be computed, how efficiently, and with what resources.

The study of computation — what can be computed, how efficiently, and with what resources.

Two foundational questions: "is this problem solvable?" (computability theory) and "how many resources does it take?" (complexity theory)

Core abstractions: algorithms, data structures, formal languages, automata, Turing machines.

The Church-Turing thesis (1936): any function computable by an effective procedure can be computed by a Turing machine — defines the boundary of what computation can do.

In ML: neural networks are universal function approximators (Cybenko 1989), but training them is a different question from whether the function exists. The gap between "a solution exists" and "we can find it" is the gap between computability and complexity.