Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
A model of computation is currently defined on wikipedia as:
a model which describes how an output of a mathematical function is computed given an input.
Is it therefore correct, at least as a rough approximation, to conceive of a model of computation as "reverse engineering a function"?
The Wikipedia definition is rather hard to understand, since it isn't formal. If you're looking for an informal definition, you should think of a model of computation as synonymous with a programming language. There is absolutely no connection to reverse engineering.
In theory of computation, we are often interested in computing Boolean functions on strings. That is, the function gets as input some string, and outputs either Yes or No. For simplicity, let us assume that the input is a binary string, and the output is a bit which represents the answer.
A model of computation specifies how programs correspond to functions. Assuming that a program is also a binary string, a model of computation is a function $M$ that accepts as input two binary strings, a program and an input, and outputs a single bit. The function computed by a program $p$ is given by $x \mapsto M(p,x)$.
For example, we can take as our model of computation the C language, with some input/output convention in which the input is a binary string and the output is a bit. The value of $M(p,x)$ is then the output of the C program $p$ when run on the input $x$ (if $p$ is not valid, we can let $M(p,\cdot)$ compute some arbitrary fixed function, say $M(p,x) = 0$).
The most popular model of computation in theory of computation classes is the Turing machine model (which is actually a collection of closely related models). When describing algorithms, we are usually implicitly working over a different model of computation, the RAM machine (once again, really a class of similar models).
All reasonable models of computation are equivalent in the sense that they define the same set of functions, known as the computable functions (another term is recursive functions). They differ in the resources needed to compute functions, what is known as computational complexity.
