COMMUNICATION WITH AUTOMATA: Volume 1 Supplement 1
Abstract
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) The following postulates are assumed: (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. (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. Suitable conceptual structures for an exact theory of communication are then discussed, and a theory of communication proposed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1966
- Accession Number
- AD0630125
Entities
People
- Carl A. Petri