Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary cellular automata and I understand them.ie. the rules, states, colours, etc. and how they work. What I really don't get however is how they are viewed as an abstraction of computing. Why are automata even used to represent computers??

They begin in some state and run forever(unless a terminating state is specified). The critical point I'm trying to make here is that they receive no external input and are essentially functions of themselves:their current state is some function of its starting state.

share|improve this question
add comment

2 Answers

The Turing Machine is just a simple model of a computer. On the one hand one has only a restricted set of operations. On a modern PC, you have more operations. On the other hand one has infinite space and time, which is not true for a modern PC. So, the goal is just, that you can analyze the Turing Machine easily. So you say, you could combine these simple operations to get the complex operations of modern PCs and you assume that memory limitations aren't an issue, which is true for most software.

Then it's easy to analyze, wether an algorithm can run on a computer or whether a programming language is Turing-complete.

You can program a Turing Mashine, if you write some bits on this infinite large band of memory ;-). I think you will find some Turing simulators in the web or you watch this nice example video of a counting program.

share|improve this answer
add comment

The simplest model of a computer consists of an automaton plus its tape(s).

The input is on the tape at the time the automaton starts. The program is in (i.e., defines) the automaton, or it is part of the input (for a universal Turing machine).And the output is on the tape at the time the automaton stops (if it stops). Not stopping also happens in real programs if there are infinite loops.

Thus a (general enough) automaton captures all features of a real program execution. Indeed, one can map any algorithm onto a Turing machine, and this gives the standard, mathematically rigorous definition of the term ''algorithm''.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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