3
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ We do not assume that TM's compute all computable functions. In most developments of computability theory, the computable functions are defined to be as those computed by TM's. $\endgroup$ Nov 30, 2012 at 13:26
  • 1
    $\begingroup$ Yes, of course you're right. I was referring to the Church Turing thesis. $\endgroup$
    – adrianN
    Nov 30, 2012 at 15:35
  • $\begingroup$ i can clearly understand you part for the part of a cell having two states (alive or dead) as ( 0 or 1) i am wondering what would it be if the cell have infinite states of numbers ? i.e instead of each cell having (0 & 1), it would have (0,1,2,3,4 ... infinite) what these numbers will represent ?? we have 0 = dead and 1 = alive but what is 2 ?? 3,4, or even 5 ? Any thoughts? $\endgroup$
    – abc
    Oct 24, 2015 at 15:22
  • 1
    $\begingroup$ @Abdulrhman They're just states of your cells. As with anything in computing, the meaning of your states is up to you. The same way that computers sometimes use the number 61 to represent lowercase 'a' and sometimes for something completely different. $\endgroup$
    – adrianN
    Oct 26, 2015 at 6:50

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.