6
$\begingroup$

I was browsing the forum where i came by this question, it says that rule 110 from {ECA} is a computation model.

What is the difference between a computation model and model of computation and how can we relate them to computers ?

A model of computation is the definition of the set of allowable operations used in computation and their respective costs.

what does it mean to 'define the allowable operations used in computation'?

Can we say that rule 110 or cellular Automata in general are computers ?

$\endgroup$
2
  • 5
    $\begingroup$ Possible duplicate of Is sierpenski's triangle considered to be a computational model? (It's not a literal duplicate but the differences between "computational model" and "model of computation" are well covered in the comments to that question.) $\endgroup$ Oct 13, 2015 at 12:50
  • $\begingroup$ @DavidRicherby: comments are not answers. They could get deleted at any time, for example. It would be better for someone to convert the comments at that post to an answer to this post. $\endgroup$ Oct 14, 2015 at 13:13

1 Answer 1

5
$\begingroup$

A model of computation is an abstract device used to perform computation.

For example, Turing machines are a model of computation. They allow operations such as reading a symbol on the tape, writing a symbol on the tape, move left/right...
Minsky machines are another model of computation. They allow operations such as increment a counter, decrement a counter, test a counter for zero.
Models of computation are used to reason about algorithms, to answer questions like: is problem X realizable with the model of computation Y? If so, how many operations would be needed?

Those models are abstract because they only describe what the available operations are, not how they are realized. A computer is a realization, an implementation of an abstract model of computation. To ease their daily use, and to get efficiency from various technologies, computers have various sets of operations, and it is hard to describe an abstract model of computation for them. Yet, all the operations they perform can be expressed in terms of e.g. Turing machines or Minsky machines operations.

Note that a Turing machine cannot exist for real: a Turing machine has an unbounded tape, so it would not fit in our Universe. Similarly, the counters of a Minsky machine are supposed to be able to store arbitrarily high numbers.

From a strict theoretical point of view, since a computer has a finite fixed amount of memory, it is nothing more than a finite state automaton (with a large, yet fixed, number of states).
In practice, a computer is rather considered as a Turing machine, with a tape (memory) large enough not to run out.

To conclude, a computational model is a mathematical description of a complex system, often a physical one. Computational models are mostly intended for simulation, to be run on real computers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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