John Holland
ABSTRACT
This paper describes a universal computer capable of simultaneously executing an arbitrary number of sub-programs, the number of such sub-programs varying as a function of time under program control or as directed by input to the computer. Three features of the computer are:
(1) The structure of the computer is a 2-dimensional modular (or iterative) network so that, if it were constructed, efficient use could be made of the high element density and "template" techniques now being considered in research on microminiature elements.
(2) Sub-programs can be spatially organized and can act simultaneously, thus facilitating the simulation or direct control of "highly-parallel" systems with many points or parts interacting simultaneously (e.g. magneto-hydrodynamic problems or pattern recognition).
(3) The computer's structure and behavior can, with simple generalizations, be formulated in a way that provides a formal basis for theoretical study of automata with changing structure (cf. the relation between Turing machines and computable numbers).
Recommendations
Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata
Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures - Volume 5504The nonemptiness problem for nondeterministic automata on infinite words can be reduced to a sequence of reachability queries. The length of a shortest witness to the nonemptiness is then polynomial in the automaton. Nonemptiness algorithms for ...
Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
In this paper we study languages accepted by nondeterministic $\log n$-tape automata that scan their input only once and relate their computational power to two-way $\log n$-tape automata. We show that for the one-way $\log n$-tape automata the ...
Comments