. Theory of Computation
To capture the idea of computation, the theory of Partial Recursive Functions asks: Can we view a computational process as being generated by combining a few basic processes ? It therefore tries to identify the basic processes, called the initial functions. It then goes on to identify combining techniques, called operators that can generate new processes from the basic ones. The choice of the initial functions and the operators is quite arbitrary and we have our first set of questions that can develop the theory of computation further. For example,
Is the choice of the initial functions unique ? Similarly, is the choice of the operators unique ? If different initial functions or operators are chosen will we have a more restricted theory of computation or a more general theory of computation ? .
one of the simplest models of computation. When interconnected, discrete finite state automata have the ability to exhibit interesting dynamical behavior. These characteristics make DFA an ideal unit with which to build a system suitable for studying the connection between dynamical behavior and computational ability. The automaton sensor is the device by which data is input. For example the automaton could have a thermometer reading temperature, a magnet reading a hard drive, an antenna reading radio waves, or anything else that would import information. We restrict the accuracy of the imported information by allowing the automaton to recognize only a finite number of different input values or symbols.
Because operation continues until the input source has been exhausted, it is often practical to place a finite limit on the amount of information that may be made available to an automaton for input.