# What is computation?

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.

• Even the case of 2 + 2 != 6 - 2 is actually complicated. In terms of actual computers, it is very possible that some layer(s) of the software/hardware stack that will calculate this apply various transformations so that what the lower levels do is not immediately understandable. Apr 28, 2023 at 21:22
• This book may be relevant: amazon.com/Computability-Theory-Introduction-Recursion-ebook/dp/…. Apr 28, 2023 at 21:26
• What part of Turing's work is "unsatisfying?" He defines an abstract computer on the basis of capability to achieve certain operations. Those operation are computation. Apr 28, 2023 at 22:08
• The standard reference on conceptual analysis of computation is Sieg, Calculations by Man and Machine: Conceptual Analysis, but I doubt that he will satisfy you. On the classical conception, computation is not an abstract process. It is defined functionally, i.e. indifferently to implementation, which can be abstract or concrete, physical or mental. But it is meant to be an idealized model of "mechanistic procedure" for an implementor with human-like limitations, even when it is a machine or an abstraction. Apr 29, 2023 at 5:55

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.

• Thank you! I suppose what I am hung up on is the idea of a formalism based on "how would a human carry out a recipe for symbol manipulation," coming to be the basis for understanding how consciousness emerges from physical systems or how physics/causation works at a fundemental level. It seems almost idealist, which is generally not what these theories have in mind. The formalism of quantum mechanics has many interpretations, as does logic itself, so I'm just surprised. I have read the SEP articles on information and physical computation closely, but will give the CT one a closer look. Apr 29, 2023 at 12:07
• CTM proponents often endose some form of functionalism, which can go thru in principle for dualism as well. But in practice most are physicalists. Apr 29, 2023 at 17:29
• As for your comments about 2+2 != 6 -2, you may wish to look up the conncept of observational equivalence Apr 29, 2023 at 17:31
• Doesn't a TM have unbounded memory? That's the entire point, else it's a finite state automaton. Apr 30, 2023 at 1:13
• @user4894 bounded memory corresponds to finite states in TM. A TM is a "finite state automaton" - it has finitely many states Apr 30, 2023 at 2:36