computation

Computation

The mechanical process of transforming input to output via fixed rules.

An algorithm is an abstract description of a computation, while a program is a concrete implementation of that algorithm in a specific model of computation. The computation is the actual execution of that program on input data.

Model of computation

A formal framework specifying what computation means.

It answers:
What constitutes a valid program?
What are the rules of execution?
What does it mean for something to be computable?

Examples: lambda calculus, turing machine.

Computation is constructive math … the subset of mathematics that can be implemented (is real / actually works).

Like a function definition in the header file indicating a return with infinitely many digits, and after you’ve read all these digits, the universe can go to the next step… such a function cannot be implemented, but under the hood you can do a good approximation, or you have some process that gives you more and more digits the longer you compute but you never get to the last one and you work in parallel.
→ In practice you can work with the “header files” of classical mathematics, as long as you bear in mind that this is not the foundational structure of the universe, because it cannot actually be implemented.
→ What Gödel and others have discovered is that if you assume that it could be implemented, your computer would break. (Entscheidungsproblem)