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. They begin in some state and run forever(unless a terminating state is specified). The 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, unlike realistic computers.

For the above reasons I'd like to know why automata are used to represent computers. More generally how can a machine be used to represent a computation?

Answer 1

Most generally, an automata is a model of computation that describes the process how to convert an input to a solution. Converting means that there is a certain set of finite, elementary, local transformation rules, that is applied to the input. The idea behind the automata might be motivated by mechanical designs, however the concept is purely mathematical. In other words an instance of an automaton is a simplistic form of an algorithm. The concept of an automaton describes the way how computations in this model are carried out. Different models have different computational powers.

A realistic computer can be also described as a mathematical model. However the setting here is slightly different, since you will not want to build a new computer for every algorithmic problem you encounter. Also a computer is an interactive system, whereas classical automata are not. The closest model for a computer is the DFA. A computer has a large but finite set of ressources, hence the status of the system can be determined by a fixed-size description (think of a huge core dump). Depending on the input (clock, user input, etc.) the computer jumps form one state to a new state in a certain well-defined and unique way.

You might be disappointed, when you hear that closest model to a realistic computer is a DFA. But you should think of an automaton more as a formalism how to write an algorithm. And from that perspective, the way you write software (algorithms) on you computer, is equivalent to writing Turing machine programs.

Maybe you are confused by the fact, that automata work on strings, and not on other problem instances. However, this is not a big deal, since we can encode an instance as a string.

Answer 2

The input is what's initially written on the tape of the Turing machine. For cellular automata, I suppose the input is the initial pattern of life and dead cells. Then the rules of the machine define what kind of function to compute on the input.

Since we assume that there are e.g. TM rules to compute any computable function, we can use a TM as a model of computation.