TY - THES
T1 - Communication with automata
T3 - Technical report RADC-TR-65-377, Volume I, Final Report, Supplement I
A1 - Petri,Carl Adam
Y1 - 2010/11/25
N2 - The theory of automata is shown not capable of representing the actual physical flow of information in the solution of a recursive problem. The argument proceeds as follows:
1. We assume the following postulates:
a) there exists an upper bound on the speed of signals;
b) there exists an upper bound on the density with which information can be stored.
2. Automata of fixed, finite size can recognize, at best, only iteratively defined classes of input sequences. (See Kleene (11) and Copi, Elgot, and Wright (8).)
3. Recursively defined classes of input sequences that cannot be defined iteratively can be recognized only by automata of unbounded size.
4. In order for an automaton to solve a (soluble) recursive problem, the possibility must be granted that it can be extended unboundedly in whatever way might be required.
5. Automata (as actual hardware) formulated in accordance with automata theory will, after a finite number of extensions, conflict with at least one of the postulates named above.
Suitable conceptual structures for an exact theory of communication are then discussed, and a theory of communication proposed.
All of the really useful results of automata theory may be expressed by means of these new concepts. Moreover, the results retain their usefulness and the new nrocedure has definite advantages over the older ones.
The proposed representation differs from each of the presently known theories concerning information on at least one of the following essential points:
1. The existence of a metric is assumed for either space nor time nor for other physical magnitudes.
2. Time is introduced as a strictly local relation between states.
3. The objects of the theory are discrete, and they are combined and produced only by means of strictly finite techniques.
The following conclusions drawn from the results of this work may be cited as of some practical interest:
1. The tolerance requirements for the response characteristics of computer components can be substantially weakened if the computer is suitably structured.
2. It is possible to design computers structurally in such a way that they are asynchronous, all parts operating in parallel, and can be extended arbitrarily without interrupting their computation.
3. For complicated organizational processes of any given sort the theory yields a means of representation that with equal rigor and simplicity accomplishes more than the theory of synchronous automata.
KW - Petri-Netz
KW - Automat
CY - Hamburg
PB -
AD -
L2 - http://edoc.sub.uni-hamburg.de/informatik/volltexte/2010/155
ER -