Generation of Primes by a One-Dimensional Real-Time Iterative Array

ABSTRACT

A construction is given of a one-dimensional iterative of finite-state sequential machines, which can generate in real time the binary sequence representing the set of prime numbers.

REFERENCES

• 1: ATRUBIN, A.J. An iterative one-dimensional real-tlme multiplier. Term paper for Appl. Math., Harvard University, 1962 (ditto).
• 2: COLE, S: N. Real-time computation by iterative arrays of finite-state machines. Doctoral Thesis, Report BL-36, Harvard University, 1964.
• 3: Seymour Ginsburg, Introduction to Mathematical Machine Theory, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1982
• 4: GoTo, E. A minimum time solution of the firing-squad problem. Course notes for Appl. Math., Harvard University, 1962, pp. 52-59 (ditto).
• 5: HEsIE, F. C. Iterative Arrays of Logical Circuits. M.I.T. Press, 1962.
• 6: MOORE, E.F. Gedanken experiments on sequential machines. Automata Studies, Prince. ton, 1956, pp. 129-153.
• 7: MooaE, E.F. The firing squad synchronization problem. In Sequential Machines: Selected Papers, Addison-Wesley, 1964, pp. 213-214.
• 8: WAKSMAN, A. An optimum solution to the firing squad synchronization problem. Is press.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Theory, Verification