I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition.

Dictionary.com's definitions of computation, computing, calculate, and compute are circular, so it doesn't help.

Wikipedia defines computation to be "any type of calculation that follows a well-defined model." It defines calculation as "the deliberate process that transforms one or more inputs into one or more results, with variable change." But it seems this definition includes many actions as computations even though they aren't typically thought of as computation.

For example, wouldn't this entail that, say, a bomb exploding is a computation, with the input being the fuse being lighted and the output being the explosion?

So, what exactly is computation?

  • $\begingroup$ That's a great, classical, question. $\endgroup$ – Ran G. Jun 25 '15 at 22:48
  • $\begingroup$ Duplicate? $\endgroup$ – Raphael Jun 25 '15 at 23:53
  • $\begingroup$ @Raphael As far as I know, computation != an algorithm. Perhaps the execution of an algorithm is computation, though. $\endgroup$ – Kelmikra Jun 26 '15 at 0:12
  • $\begingroup$ For me, "P is computable" == "There is an algorithm that solves P" (for P some problem). This may be a result from my TCS perspective, though. $\endgroup$ – Raphael Jun 26 '15 at 6:04
  • 1
    $\begingroup$ @XiangJi As far as I know, Introduction to Algorithms, a very popular book on algorithms, never defines computation. $\endgroup$ – Kelmikra Jul 2 '15 at 10:35

Perhaps the problem here is looking a for a highly specific definition of a very general concept. I don't see the problem of viewing virtually everything as a computation. Although we don't think about it, everything we do is expressible in terms of the Physics of the component parts, down to at least quarks buzzing about. We have the same situation with computation. There's inputs, outputs and a process (all of which could be trivial). Whether they're interesting or useful as computations or models of computation is a very different question.

The strongest working definition we have comes via the (strong) Church-Turing Thesis, which states that every possible physically realizable model of computation is no more powerful than a Turing Machine. If you believe that this is true, then although we may have lots of way to express things, ultimately we can reduce every computation to a Turing Machine, hence giving a definition of computation as "anything we can reduce to a Turing Machine".

In this model, the exploding bomb is a computation. It's not a widely applicable one (we hope ;) ), but we can model in some fashion with a Turing Machine (though there is an argument here about the nature of the output and the equivalence with the TM's output). It's also not a good model of computation in general, in that it seems unlikely that the exploding bomb model is Turing complete.

  • 2
    $\begingroup$ Rather off-topic, but I bet the exploding bomb model is Turing complete! Explosions could set off other explosions, which could be used to propagate signals and make or-gates. Bomb b could be set to explode at a given time via a device, but a nearby bomb could disable the device while not causing b to explode, which allows for not-gates. $\endgroup$ – Kelmikra Jun 26 '15 at 8:10
  • $\begingroup$ @Kyth'Py1k like domino gates? I don't think that will be turing complete because you can't loop indefinitely as the "computation" will always stop based on the size of the machine/minefield $\endgroup$ – ratchet freak Jun 26 '15 at 8:53
  • 1
    $\begingroup$ @ratchetfreak Not unless the bombs' remains are made into new bombs via nanobots in them and then repositioned... $\endgroup$ – Kelmikra Jun 26 '15 at 9:57

This is the question that Turing set out to solve in his famous 1936 paper, On computable numbers, with an application to the Entscheidungsproblem, a paper in which he comes up with (what came to be known as) the Turing machine model. See in particular Section 9.

Turing's work is in the context of computable numbers. There are other notions of computation appropriate for computing other kinds of structures, and their study forms part of computation theory (also known as recursion theory).

The main difference between the common notion of computation and your example (an exploding bomb) is the thing being computed. What is being computed by your exploding bomb? Another difference is the computational means, but one can envision a mechanical contraption which uses bombs to compute something more legitimate.

Another point is whether the classical notions of computation apply to what we perceive today as computation – namely, two-way interaction between the computer and the user. This is a common criticism levelled against the classical notional of computability, though interaction can be modelled using the tools of computation theory (it's just not what you learn in class).

  • $\begingroup$ Of course an explosion is a computation. It "computes" exactly the unitary transformation that describes explosion. BTW, many time the physicists I met were "upset" when you say that (say) some quantum gate computes a unitary, rather than evolve it, or transform the physical system accordingly ("does the gate take a pen and paper and compute the unitary"?) :) $\endgroup$ – Ran G. Jun 25 '15 at 23:14
  • $\begingroup$ I read section nine of "On computable numbers, with an application to the Entscheidungsproblem," but it didn't really seem to help. Though I didn't read it extremely thoroughly, it seemed to be laying the groundwork for Turing machines. Are you saying that computation is anything that can be modeled as an action done by a Turing machine? If so, wouldn't almost everything be a computation? For example, bombs explosions could be modeled as a Turing machine such that the positions, velocity, and types of the quantum particles of the surrounding particles are encoded as binary. $\endgroup$ – Kelmikra Jun 26 '15 at 0:17
  • $\begingroup$ "What is being computed by your exploding bomb?" The change in the states of the particles surrounding the bomb according to the laws of physics are being computed. $\endgroup$ – Kelmikra Jun 26 '15 at 0:19
  • $\begingroup$ "Another point is whether the classical notions of computation apply to what we perceive today as computation – namely, two-way interaction between the computer and the user." I don't think this is quite what is considered computation. Autonomous robots are thought of as doing computations, even though they need not interact with users. $\endgroup$ – Kelmikra Jun 26 '15 at 0:20
  • 1
    $\begingroup$ Obviously you and I have rather different concepts of computation. Mine is "calculation by mechanical means", a vague concept which was made precise by Turing. Yours is different, and more general. Since computation means different things to different people, perhaps you can clarify your concept of computation. Note that a dictionary definition is here completely superfluous; meaning doesn't come from the dictionary, it comes from the speakers and from usage. $\endgroup$ – Yuval Filmus Jun 26 '15 at 2:32

On it's most basic level, a computation is just a mapping between some set $A$ to some set $B$. every $x\in A$ is called an input and the computation maps this input to some output $y\in B$. The mapping needs to be defined on its entire domain: if some input $x\in A$ is not mapped by the computation, then the computation on $x$ is not defined.(1)

The other great answers in this thread try to plot the connection between this mapping and the method of achieving it. That is, they explain that to "compute" the output of some input $x$, we need a systematic, well defined method that takes us from an input $x$ to its output $y$. While true, this is not necessary to define computation. Indeed, if you encounter a Genie, and every time you give them a number $x$ they answer with $y$, then they compute something (even if this mapping is not recursive, and no computer can produce it).

In this very broad way to see computation, any physical device is a computer: it transfers the physical system at time $t=0$ (its input) to a different system at time $t=1$ (the output). Moreover, this computation is well defined (i.e., can be specified in a compact way, e.g., by unitary matrices). If you design the device properly, it can perform almost any (recursive) computation you desire. (Scott Aaronson talks quite a bit about "Can Nature compute problems", although his focus is mainly on NP-complete problems, this is very relevant to this discussion).

Bottom line: any mapping defines a computation. Any "device" that transforms an input to the corresponding output, performs ("computes") that specific computation.

(1) we can extend the discussion to these types of computations, which will make sense when you think on funcitons which are not recursive, but I prefer not to go there.

  • $\begingroup$ The problem with this definition is that it doesn't correspond to how the word "computation" is actually used. PCs are thought of as doing computations, while, say, explosives are not. $\endgroup$ – Kelmikra Jun 29 '15 at 3:55
  • $\begingroup$ IMHO a mapping is exactly what a computation is not. I think you confuse syntax and semantics. Clearly you understand mapping as an input-output relation, however defined. By all my books, that is semantics. The computation is the means used to actually get the output corresponding to some input through a sequence of steps. While you might say that any computation defines a mapping (if only a syntactic one), I think it is wrong to consider that a mapping defines a computation, unless you carefully explain that you are going into hypercomputing which seems a bit beyond the question. $\endgroup$ – babou Jun 29 '15 at 11:54
  • $\begingroup$ I should clarify the spirit of my answer (I realize it is not worded that way): the mapping itself is not a computation. The process of converting an input into an output is a computation of that specific mapping (function). What I was trying to convey is that the specific process is relevant, any such process is a computation (even a very abstract one, e.g., an "oracle"). $\endgroup$ – Ran G. Jul 11 '15 at 16:24

I will not attempt to define what a computation is, which was done rather well by Luke Mathieson and Yuval Filmus.

However, thinking about an exploding device as a computation lead me to an important side issue: if the explosion is a computation, then what does it compute? Other than a representation of the device after it has exploded.

What I am aiming at is that we can define fairly precisely what we consider to be a computation, and even what can be seen (contrived?) as one. We can describe a computation. But can we tell what it is computing?

Computation, as commonly defined, is a purely syntactic game. It is a game of physical structures that are being transformed according to precise rules. Since our only tool (up to standard transformations) for representing physical structures is ultimately the string of symbols, computation ends up being defined as some kind of formal transformations on strings of symbols. This is true of Turing Machines, lambda-calculus, partial recursive functions, and other less popular models. The word calculus (as in lambda-calculus) actually reflects this view as, in Latin, calculi are small stones used for representation.

But what this does not tell is what meaning is to be attached to this syntax, what it represents. Here is what little I think I understand, as I am not a specialist of such issues (so double check me). The problem is covered by model theory.

Given a formal system of representations, possibly associated with a logic (axioms and inference rules) or a computation system (transformation rules), a model of the formal theory is a mathematical stucture with components that follow these rules.

The same computation, or more precisely the same description of a computation can actually have many models corresponding to very different entities.

For example, a GCD algorithm describe a computation. But it may be interpreted on natural numbers, or on polynomials.

This is remindful of Bertrand Russell'quote:

Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true.

The situation is pretty much the same for computation. It is a formal game, where the moves can be understood in many different ways. But there are actually deep ties between Mathematics formally defined by axiomatic systems and Computation Theory.

Computation, algorithmics, was defined to solve mathematical problems, and many of the modern concepts were thought of by logicians who were trying to understand the mechanisms that allow us to prove theorems, starting from axioms and applying inference rules.

Hence, to come back to the exploding device, it can certainly be construed as a manipulation of a representation, i.e. as a calculation. But it is generally pretty hard to associate to it any meaning other than itself.

However, this is not always true, or was not. The principle of analog computation relies on the idea that different representation system can be used for calculations that are related in some precise way. Then we can calculate with one system to have an idea of what the other sytem (too unwieldy to actually use, for example a universe :) would calculate in the corresponding setting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.