[seanstrom]

Hey I was wondering what maths are at the foundation of computer science. Could you explain which ones you think are at the foundation?

For context, I’m not sure something like calculus would be a foundational math (though it could be), but something like Boolean logic would be (right?)

[rramadass]

Discrete Maths (https://en.wikipedia.org/wiki/Discrete_mathematics) is what you are looking for;

Specifically : Logic(Propositional and Predicate), Boolean Algebra, Proofs(Inductive, Deductive, Transformational), Set Theory, Relations, Functions, Lambda Calculus, Formal Systems.

They are all interrelated but some are foundational. Thus for example Set Theory and Logic are foundational while the others are built on top; Set Theory leads to Relations and Functions, Proofs are the process of applying Logic, Lambda Calculus is Function Abstraction taken to extreme and Formal Systems teach you how to build Symbolic Systems (Models) without reference to any specific Domain of Discourse.

[SulphurCrested]

A background in "pure maths" is extremely useful. You don't necessarily have to remember many (or perhaps any) of the particular definitions and theorems, but the ability to formulate definitions and prove results about them is valuable. I've seen software documentation that actually assumes it. This is what mathematicians call "mathematical sophistication".

For example, proof by induction is the same basic idea as terminating recursion.

Other things in computing were designed by mathematicians and kind of assume you see things a bit that way. The pointer arithmetic and "inside out" declarations of C are perfectly sensible if you think mathematically – Dennis Ritchie was a mathematician. Likewise, Stroustrup's use of 0 for the nil pointer in C++ would have been understood without explanation by the people down the corridor from him at Bell Labs. Mathematicians often use 0 to represent some distinguished element of a set that is not necessarily a set of numbers.

An example of a specific use of maths in computing is relational databases. Relations are kinds of sets.

Some results in cooperating processes and distributed computing that software engineers should know are proven mathematically. If you can't read a proof, you can't read the paper/textbook and are reduced to "remembering" the result rather than internalising it.

[j-pb]

We are in the age of machine learning, whenever you search for something online, take a photo with your phone, drive in your (diver assisted) car, filter out spam, get a product or video recommendation, you are using a system that is founded on calculus.

Just because computer science started with file systems and regexes (discrete math) doesn't mean that the systems of today or tomorow don't have very different foundations.

[scrapheap]

I'm pretty certain that the systems of today have the same foundations as those of yesterday, we've just abstracted them away so we don't directly see it as often.

[j-pb]

That doesn't make a lot of sense given the novel hardware that runs in a lot of chips these days. TPUs, neural accellerators, perceptron branch prediction, flash based neural networks.

Thise are not abstractions over existing posix APIs or von neumann architectures, they are novel ways to do computation from a different branch of math.

Heck we don't even know if some of these are not breaking the church turing thesis by computing with true real numbers and not the computable subset that turing machines can handle.

[ghoshbishakh]

Everything is discrete. Computers cannot handle "true" real numbers.

[j-pb]

Digital computer cannot handle true real numbers.

Analog computers MIGHT.

It really depends on how quantized our universe is. If you have papers that show full quantization including tunneling probabilities e.t.c please share them! The physical existence of the reals has been a white whale of mine for some time ^^'.

[seanstrom]

Yeah these are good points. I guess we could also add AI to the list (AI before ML), since it also has use of calculus I think.

I’m now wondering whether to consider both of these subjects foundational to CS or a CS degree. My gut says yes since so much relies on ML and AI is used a bunch (e.g. games and stuff).

[j-pb]

AMR Ryzen uses perceptrons in it's branch predictor, I'd say that's pretty foundational.

[ghoshbishakh]

Boolean math (building the computing device), then discrete maths (combinatorics for algorithms and DS), followed by probability and statistics (for algorithms as well as ML/AI).