[Solved]: What exactly is computation?

Problem Detail: 

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?

Asked By : Kelmikra

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43938