computer science

Computer science is the study of computation: what can be computed, how efficiently, and with what resources. It rests on two foundational questions, whether a problem is solvable (computability theory) and how many resources it takes (complexity theory), and its core abstractions are algorithms, data structures, formal languages, automata and Turing machines.

Computer science is the study of computation: what can be computed, how efficiently, and with what resources. It rests on two foundational questions, whether a problem is solvable (computability theory) and how many resources it takes (complexity theory), and its core abstractions are algorithms, data structures, formal languages, automata and Turing machines.

Quantum computing leaves the boundary of what can be computed where it is and moves only the speed of some problems: a quantum computer can be simulated by a classical one, at an exponential cost.

The Church-Turing thesis (1936) holds that any function computable by an effective procedure can be computed by a Turing machine, which 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 knowing that a solution exists and being able to find it is the gap between computability and complexity.