How does an automaton actually “compute”?

Question

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.

Answer 1

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.

Answer 2

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''.