In this note we define the amount of feedback in a realization of a sequential machine M, give a simple algorithm to compute the minimal amount of feedback which has to be present in any realization ...of M, and give a canonical realization of M which uses the minimal amount of feedback.
In this paper we study the problem of replacing (decomposing) a complex finite state sequential machine by several simpler ones which operate in parallel and yield the same result. In the first part, ...we give the necessary mathematical background and results. In the second part, we apply these results and derive the necessary and sufficient conditions for the existence of a decomposition for a given machine. If a decomposition exists then the required simpler machines which have to be connected in parallel are given.
Systems and computer science John Hart, Satoru Takasu
Systems and computer science,
1967, 19671215, 2019, 1967, 1967-12-15
eBook
This book presents the papers delivered at the Conference on Systems and Computer Science held at the University of Western Ontario in September 1965, focused on some of the concepts of Computer ...Science as a new field of study and at the same time provide a background for scientists looking at the subject for the first time.
We investigate the Kolmogorov complexity of real numbers. Let
K be the Kolmogorov complexity function; we determine the Hausdorff dimension and the topological dimension of the graph of
K. Since ...these dimensions are different, the graph of the Kolmogorov complexity function of the real line forms a fractal in the sense of Mandelbrot. We also solve an open problem of Razborov using our exact bound on the topological dimension.
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 nondeterministic model (1-NL) is computationally much more powerful than the deterministic model (1-L), that under one-way $\log n$-tape reductions there exist natural complete languages for these automata and that the complete languages cannot be sparse. Furthermore, we show that any language complete for nondeterministic one-way $\log n$-tape automata (under 1-L reductions) is also complete for the computationally more powerful nondeterministic two-way $\log n$-tape automata (NL) under two-way $\log n$-tape reductions. Therefore, for all bounds $T(n)$, $T(n) \geqq \log n$, the deterministic and nondeterministic $T(n)$-tape bounded computations collapse iff the nondeterministic one-way $\log n$-tape computations can be carried out by two-way deterministic log $n$-tape automata.
If all $NP$ complete sets are isomorphic under deterministic polynomial time mappings ($p$-isomorphic) then $P \ne NP$ and if all PTAPE complete sets are $P$-isomorphic then $P \ne {\text{PTAPE}}$. ...We show that all $NP$ complete sets known (in the literature) are indeed $p$-isomorphic and so are the known PTAPE complete sets. This shows that, in spite of the radically different origins and attempted simplification of these sets, all the known $NP$ complete sets are identical but for simple isomorphic codings computable in deterministic polynomial time. Furthermore, if all $NP$ complete sets are $p$-isomorphic then they all must have similar densities and, for example, no language over a single letter alphabet can be $NP$ complete, nor can any sparse language over an arbitrary alphabet be $NP$ complete. We show that complete sets in EXPTIME and EXPTAPE cannot be sparse and therefore they cannot be over a single letter alphabet. Similarly, we show that the hardest context-sensitive languages cannot be sparse. We also relate the existence of sparse complete sets to the existence of simple combinatorial circuits for the corresponding truncated recognition problem of these languages.
A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of the set ...of primes can be accepted by a pushdown or finite automaton. In view of this result an interesting open problem is to determine the "weakest" automaton which can accept the set of primes. It is shown that the linearly bounded automaton can accept the set of primes, and it is conjectured that no automaton whose memory grows less rapidly can recognize the set of primes. One of the results shows that if this conjecture is true, it cannot be proved by the use of arguments about the distribution of primes, as described by the Prime Number Theorem. Some relations are established between two classical conjectures in number theory and the minimal rate of memory growth of automata which can recognize the set of primes.
PDF
