patternMinor
What exactly is computation?
Viewed 0 times
computationexactlywhat
Problem
I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition.
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#43938, answer score: 6
Revisions (0)
No revisions yet.