What is computation?

Question

The most common definitions of computation I have seen are in terms of "what Turing Machines, Lambda Calculus, etc. do," which is unsatisfying. The definition of computable functions does not seem to be a definition of what computation itself, as a process, is.

I have not been able to find anything like the sort of deep conceptual analysis that exists for similar questions like: "what are numbers," "what are propositions," etc. E.g., if numbers are an "abstract object," would that make computation an "abstract process"? Or is computation just the step-wise enumeration of 'relations' or entailment (which there is a solid literature for)? I know there isn't a definitive answer, I'm just looking for some sort of exploration of the topic so I'm not working in the dark.

We can say 2 + 2 = 4 and 6 - 2 = 4, but these are not computed the same way.

There is a lot in the physics literature and the philosophy of physics literature on "what is a computer," physically speaking. Obviously, the physical instantiation of adding two groups of two things together is different from throwing out two of six things. This would suggest that, vis-á-vis computation, 2 + 2 ≠ 6-2, which is very different from how we think of identity in numbers. That is, the outputs are equivalent, but not the processes by which we get the output.

This seems relevant to issues in the philosophy of information vis-á-vis the "scandal of deduction," that deterministic computation does not produce new information, and the problem of non-constructive rigid designators. It also seems relevant to the philosophy of physics re: pancomputationalism (all the rage in popular science it seems), but I can't find anything really in depth.

Answer 1

Maybe we can start historically. Turing is attempting to capture the informal notion of effective or mechanistic process. His 1936 highlights the following, where computer denotes an actual agent:

(a): Computation is determinstic

(b): Bounded memory of computer

(c): Bounded observation of computer: the computer can only intake finitely amounts of data at a time.

This list is not exhaustive. Turing was very influential, the Church_turing thesis asserts that the philosophical nature of mechanical process is captured by the formal notion of Turing machine. So your requests for an actual analysis of compoutational process are immediately answered if Church-Turing is true.

So is it true? Well, the standard arguments are as follows (Kleene 1952)

(i): All paradigmatically computable processes have turned out to be recursive ( ie captured bt the notion of a TM)

(ii): All other attempts at an analysis of mechanistic process are equivalent to TMs.

In particular, indeterminsitic systems such as Posts are seen to be equivalent with Determinsitic TMs. Post was originally working with logics, which brings us to another notion of computation, as espoused by Kripke 2013 ( and with precursors in Leibniz): computation is just deduction. The blind manipulation of symbols according to lgocial rules is computation. These observations can be made more formal via the curry howard correspondence. Again, if you accept church turing, we can say even more: these two viewpoints are in fact "philosophically" equivalent.

A further survey of arguments for and against can be seen at SEPs page on Church turing. Typically each different formalism was accompanied ny a (brief) defense of hy it captured the notion of effective procedure. So it may serve you to read say Church, Post, Schonfinkel, Turing, Godel/Heberand on their original motivations.

Lastly, I note that we have now come full circle: whereas Turing based his notion of computation on what human computers could do, proponents of computational theory of mind now use TMs ( and computatiuonal models more generally) to "explain" computational notions in human agents.