THE UNI V ER SITY OF M I CHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Communication Sciences Final Report AUTOMATON RESEARCH: DESIGN, CONSTRUCTION, COMPLEXITY, ADAPTATION Logic of Computers Group ORA Project 03105 supported by: DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NOo Nonr-1224(21) WASHINGTON, D.C, administered through: urlu;E OF RESEARCH ADMINISTRATION ANN ARBOR February 1968 Distribution of this document is unlimited,

\jCAJ\ \K k

RESEARCH PROGRESS REPORT Title: "Automaton Research: Design, Construction, Complexity, Adaptation," Logic of Computers Group, The University of Michigan Final Report 03105-51-F, Contract No, Nonr-1224(21). Background: The Logic of Computers Group of the Department of Communication Sciences of The University of Michigan is investigating the application of logic and mathematics to the design of computing automata. Condensed Report Contents: The Office of Naval Research sponsored research program of the Logic of Computers Group of The University of Michigan is reviewed, and principal resulting reports and papers listed. The research first concentrated on showing the existence or non-existence of mechanical design procedures for computing automata. Later research included research on problems of automata which grow and reproduce, and problems of measuring the complexity of machines. Automaton composition de-composition problems were studied employing the methods ot group and semi-group theory, category theory, and graph theory. Some problems of adaptation and learning in machines, as well as the relationship between probabilistic and deterministic machines were also examined. For Further Information: The complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center. A few copies are available for distribution by the author.

INTRODUCTION Research on Task NR 049-114 under Contract Nonr 1224 (21) began 1 January 1957 and continued to 31 December 1967. In the eleven years of the contract, 50 technical reports of research in the field of theory of automata and logical design of computer nets were submitted to the Office of Naval Research, This final report of research under Nonr 1224 (21) consists of three parts: Io A brief summary review of the research performed; II, A listing of the principal reports and publications resulting from the research; and III. A listing of the scientific personnel whose ONR supported research led to the obtaining of advanced degrees at The University of Michigano PART I In the early years of this ONR sponsored research, attention was focussed on finding appropriate mathematical languages for the description of automaton structure and behavior, and then showing the existence or nonexistence of mechanical design procedures for classes of automata whose design specifications are expressed in the languages~ Thus (of the list of Part II of this report) 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, and 32 all fall in this category. This research on design algorithms led to several foundational mathematical studies especially Items 16, 17, 18, and 19. In Item 20, several research areas were reviewed; these included problems of machines which grow and reproduce, and problems of the measuring of the complexity (and thus capabilities) of machines. Work on growing and cellular 1

machines is reported in Items 29 and 50, while research on automaton structural and behavioral complexity measures is presented in 21, 22, and 46. The general problem of finding appropriate simple automaton sub-units from which all machines could be built and into which all machines could be decomposed, led to a program of research into the use of algebraic and graph theoretic techniques for describing machines. Work in this area is reported in Items 24, 26, 27, 31, 35, 36, 37, 40, 42, 43, 44, 45, and 48. Problems of securing adaptive behavior in machines is discussed in Items 20, 41, and 47. Some practical issues in the design of the next generation of computers are discussed in Item 38, while in Items 34 and 39, the relationship between completely deterministic machines and machines which (like all physical machines) have some probability of incorrect behavior is analyzed. PART II A LIST OF THE PRINCIPAL REPORTS AND PUBLICATIONS (The work listed here was supported in whole or in part by funds supplied through Nonr 1224 (21). Some of the work here listed was supported in part by the U.S. Army principally through the Army Signal Corps-Monmouth and the Army Research Office-Durham, and by the National Science Foundation and the National Institutes of Health.) 1. "Realization of Events by Logical Nets," I. M. Copi, C. C. Elgot and J. B. Wright, Journal of the Association for Computing Machinery5 (1958) 181-196. Also: in Sequential Machines ed. E. F. Moore Addision-Wesley, 1964, 175-192. 2. "Quantifier Elimination in a Problem of Logical Design," C. C. Elgot and J. B. Wright, Michigan Mathematical Journal 6 (1959) 65-69. 2

3. "Series-Parallel Graphs and Lattices," C. C. Elgot and J. B. Wright, Duke Mathematical Journal, 26 (1959) 325-338. 4. "The Non-Existence of Certain Algorithms of Finite Automata Theory," J. R. Buchi, C. C. Elgot, J. B. Wright, (Abstract) Notices American Mathematical Society 5, No. 1 (Feb. 1958), 98. 5. "Decision Problems of Weak Second-Order Arithmetics and Finite Automata. Part I," J. R. Buchi and C. C. Elgot (Abstract) Notices American Mathematical Society 5, 7 (Dec. 1958), 834. 6. "Weak Second-Order Arithmetic and Finite Automata, " J. R. Buchi, Zeitschrift fuir Mathematische Logik und Grundlagen der Mathematik 6 (1960) 66-92. 7. "Decision Problems of Weak Second-Order Arithmetics and Finite Automata," Part II. C. C. Elgot (Abstract) Notices American Mathematical Society 6, 1 (Feb. 1959), 48. 8. "Decision Problems of Finite Automata Design and Related Arithmetics," C. C. Elgot, Transactions American Mathematical Society, 98 (1961) 21-51. Errata, ibid., 103 (1962) 558-559. 9. "Regular Canonical Systems and Finite Automata," J. R. Buchi, Technical Report, University of Michigan (December 1959). Also: Archiv fir Mathematische Logik und Grundlagenforschung 6, 5/4 (1962), 91-111. 10. "Computation, Structure and Behavior in Fixed and Growing Automata, " A. W. Burks, Self-Organizing Systems, New York, Pergamon Press, 1960, 282-311. Also: (Revised version): Behaviorial Science 6, 1 (1961) 5-22. 11. "On a Problem of Tarski," J. R. Buchi, Technical Note University of Michigan, July 1960. 12. "On a Problem of Tarski," J. R. Buchi, Abstract: Notices American Mathematical Society 7, 3, 381-382. 13. "On a Decision Method in Restricted Second Order Arithmetic," J. R. Buchi; Logic, Methodology and Philosophy of Science: Proceedings of the 1960 International Congress, ed. Nagel, Suppes. Tarski, Stanford U1 Press, 1-11. 14. "Sequence Generators and Digital Computers," A. W. Burks and J. B. Wright, Recursive Function Theory: Proceedings of Symposia in Pure Mathematics, 5, 139-199, American Mathematical Society, 1962. 15. "Sequence Generators, Graphs, and Formal Languages," A. W. Burks and J. B. Wright, Information and Control 5 (1962) 204-212. 5

16. "Inseparable Sets and Reducibility," S. Tennenbaum, Technical Report University of Michigan, July 1961. 17. "Turing Machines and the Entscheidungsproblem," J. R. Buchi, Abstract: Notices American Mathematical Society 8, 4 (1961) 354. 18, "Turing Machines and the Entsheidungsproblem," J. R. Buchi, Mathematische Annalen, 148 (1962) 201-213. 19o "On Validity in Finite Domains," J. R. Buchi, Abstract: Notices American Mathematical Society 8, 4 (1961). 20. "Concerning Efficient Adaptive Systems," J. H. Holland, Self-Organizing Systems-1962, New York, Pergamon Press, 1962 (Manuscript preparation and publication: ONR supported). 21. "The Star-height of Regular Expressions," L. C. Eggan, Abstract: Notices American Mathematical Society, 9, 4 (1962) 298. 22. "The Star-height of Regular Expressions," L. C. Eggan, Michigan Mathematical Journal 10 (1963), 385-397. 23. "Commutative Machines," R. Laing and J. B. Wright, Technical Report, University of Michigan, December 1962. 24. "Normal Monoids and Factor Monoids of Commutative Monoids," Y. Give'on, Technical Report, University of Michigan, May 19635 25. "Notes on Mathematical Automata Theory," J. W, Thatcher, Technical Note, University of Michigan, December 1963o 26. "The Theory of Algebraic Automata I: Morphisms and Regular Systems," Y Give'on, Technical Note, University of Michigan, January 1964. 27. "Outline for an Algebraic Study of Event Automata," Y. Give'on, Technical Report, University of Michigan, June 1964. 28. "Lattice Matrices," Y. Give'on, Information and Control 1, 4, (1964), 477-484. (Revised and prepared for publication under Nonr 1224 (21))o 29. "Variants of Thatcher's Algorithm for Constructing Pulsers," S. Hedetniemi, University of Michigan Technical Report, August 1964. 30. "Universality in the Von Neumann Cellular Model," J. Wo Thatcher, University of Michigan Technical Report, September 1964. Also: To appear in Essays in Cellular Automata edo A. Wo Burks, University of Illinois Press, 4

31. "Toward a Homological Algebra of Automata," Y. Give'on (This work consists of 4 parts; these appeared as separate reports during 1965; the parts are as follows: I. 1. The Representation and Completeness Theorem for Categories of Automata II. 2. A Note on Some Well-Known Functors of Automata III. 3. Composition Series of Automata, 4. Extensions of Q-Automata IV. 5. The Characterization of Projective Automata) 52. "Decision Problems for Multiple Successor Arithmetics," J. W. Thatcher, University of Michigan Technical Report April 1965. Also: Journal of Symbolic Logic 31, 2 (1966), 182-190 33. "Tape Machine Realization of Commutative Regular Events," R. Laing, University of Michigan Technical Report, October 1965. 54. "Equivalences Between Probabilistic and Deterministic Sequential Machines," C. V. Page, University of Michigan Technical Report, April 1965. Also: Information and Control 4, 469-520 (1966) 35. "Transparent Categories and Categories of Transition Systems, " Y. Give'on, University of Michigan Technical Report May 1965. Also: (Related paper) 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design (Record of Sixth Annual Symposium) 235-241. Also: (Related paper) Proceedings of the Conference on Categorical Algebra: La Jolla 1965, eds. Eilenberg, Harrison, MacLane, and Rohrl, Springer Verlag 1966, 317-330. Also: (Related paper) Logic, Computability and Automata, ed. F. Cannonitio, Thompson Book Co. Washington D.C. 36. "A Homomorphic Theory of Content-Free Languages and Its Generalizations," Y. Give'on, University of Michigan Technical Report, September 1965. 37. "Homomorphisms of Graphs," S. Hedetniemi, University of Michigan Technical Report, December 1965. 38. "Iterative Circuit Computers: Characterization and Resume of Advantages and Disadvantages," J. H. Holland, Microelectronics and Large Systems, eds. Mathis, Witey, Spandorfer. Spartan Press, 1965, 171-178. 39. "Equivalences Between Probabilistic Sequential Machines," C. V. Page, University of Michigan Technical Report, December 1965. 40. "On Some Categorical Algebra Aspects of Automata Theory: The Categorical Properties of Transition Systems, Y. Give'on University of Michigan Technical Report, February 1966.

41. "Non-Linear Environments Permitting Efficient Adaptation," J. H. Holland, Computers and Information Sciences-l, ed. J T. Tou, Academic Press 1967, 147-164. 42. "Homomorphisms of Graphs and Automata," S. Hedetniemi, University of Michigan Technical Report, August 1966. 43. "Degenerate Automata: Some Relationships Involving Semi-Group Order and Regular Events," B. Zeigler, University of Michigan Technical Report, December 1966. 44. "On Hereditary Properties of Graphs," S. Hedetniemi, University of Michigan Technical Report, February 1967. 45. "Some Interpolation Theorems for Partitions of Graphs," S. Hedetniemi, University of Michigan Technical Report, March 1967. 46. "Realization and Complexity of Commutative Events," R. Laing, University of Michigan Technical Report, March 1967. 47. "A Class of Sequential Sampling Problems Arising in Certain Learning Situations," E. Bainbridge, University of Michigan Technical Report, December 1967. 48. "Decompositions of Automata Using Normal Submonoids," B. Zeigler, University of Michigan Technical Report, December, 1967. PART III ADVANCED DEGREES EARNED THROUGH ONR SPONSORED RESEARCH 1. Calvin Elgot obtained the Ph.D. in Mathematics from The University of Michigan; his dissertation is item 8 of the list of reports and publications. 2. James Thatcher obtained the Ph.D. in Communication Sciences from The University of Michigan; his dissertation is item 32 of the list of reports and publications. 3. Y. Give'on obtained the Ph.D. in Communications Sciences from The University of Michigan; his dissertation is item 40 of the list of reports and publications. 4. C. V. Page obtained the Ph.D. in Communication Sciences from The University of Michigan; his dissertation is item 39 of the list of reports and publications. 6

5, So Hedetniemi obtained the Ph.D. in Communication Sciences from The University of Michigan; his dissertation is item 42 of the list of reports and publications. In addition, at the conclusion of Nonr 1224 (21) five graduate students were pursuing research, with ONR contract support, which will lead to the Ph.Do in Communication Sciences at The University of Michigan. 7

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 20301 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Branch Office Room 239, Building 10 Box 39, Fleet Post Office Washington 25, D.C. New York, New York 09510 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground. Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office, Chicago Office 230 North Michigan Avenue 495 Summer Street Chicago, Illinois 60601 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office Washington,D.C. 20007 1076 Mission Street Attn: Code 042, Technical Library San Francisco, California 94103

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomies Division Attn: Code 432 Commanding Officer Dr. Kenneth Krohn Harry Diamond Laboratories Krohn Rhodes Research Institute, Inc. Washington, D.C. 20438 328 Pennsylvania Avenue, S. E. Attn: Library Washington 13, D. C. Commanding Officer and Director U. S. Naval Training Device Center Dr. Larry Fogel Orlando, Florida 52813 Decision Science, Inc. Attn: Technical Library 6508 Pacific Highway San Diego, California Department of the Army Office of the Chief of Research National Bureau of Standards and Development Applications Engineering Section Pentagon, Room 3D442 Washington 25, D. C. Washington 25, D.C. Attn: Miss Mary E. Stevens Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332

UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA - R&D (Security classification of title, body of abstract and indexing annotation must be entered when the overall report is claseified) 1. ORIGINATING ACTIVITY (Corporate author) 2.- REPORT SECURITY C LASSIFICATION Logic of Computers Group UNCLASSIFIED The University of Michigan 2b. GROUP Ann Arbor, Michigan 48104 3. REPORT TITLE AUTOMATON RESEARCH: DESIGN, CONSTRUCTION, COMPLEXITY, ADAPTATION 4. DESCRIPTIVE NOTES (Type of report and Inclusve dates) S. AUTHOR(S) (Last name. firat name, initial) Logic of Computers Group 6. REPORT DATE 7i. TOTAL NO. OF PAGES 7b. NO. OF REFS February 1968 7 8a. CONTRACT OR GRANT NO. 9a. ORIGINATOR'S REPORT NUMBER(S) Nonr-1224(21) b. PROJECT NO. 03105-51-F c. Sfbl. OTiHIR RI PORT NO(S) (Any othernumbere that may be assigned hi..rport) d. 10. A V A ILABILITY/LIMITAtiON NOTICES Qualified requesters may obtain copies of this report from DDC. Distribution of this document is unlimited. 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Office of Naval Research Department of the Navy [ WashingtQn 25, D. C 13. ABSTRACT The Office of Naval Research sponsored research program of the Logic of Computers Group of The University of Michigan is reviewed, and principal resulting reports and papers listed. The research first concentrated on showing the existence or non-existence of mechanical design procedures for computing automata. Later research included research on problems of automata which grow and reproduce, and problems of measuring the complexity of machines. Automaton composition decomposition problems were studied employing the methods of group and semi-group theory, category theory, and graph theory. Some problems of adaptation and learning in machines, as well as the relationship between probabilistic and deterministic machines were also examined. DD. JAN4 1473 UNCLASSIFIED Security Classification

UNCLASSIFIED Security Classification 14. KEY WORDS LINK A LINK B LINK C KEY WORDS ROLE WT ROLE WT ROLE WT Automata Decision Procedures Category Theory Adaptive Systems INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) Qualified requesters may obtain copies of this the report. ~~~~~~~~~~the report. ~report from DDC." 2a. REPORT SECURITY CLASSIFICATION: Enter the over2a..REPORT SECUTY CLASSIFICATION: Enter the. over- (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether a "Restricted Data" is included Marking is to be in accord- report by DDC not thozed ance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of 2b. GROUP: Automatic downgrading is specified in DoD Di- sers s ret tro Other qualified DDC rective 5200.10 and Armed Forces Industrial Manual. Enter userha through the group number. Also, when applicable, show that optional. markings have been used for Group 3 and Group 4 as author- (4). military agencies may obtain copies of this report directly from DDC. Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles in all cases should be unclassified.,, If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled. Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of."_ report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Serices, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 1L SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter last name, first name, middle initial. tory notes. If:.mlitary, show rank and branch of service. The name of the principal author is an absolute minimum requirement, 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay6. REPORT DATi-. Enter the date of the report as day, ig for) the research and development. Include'address. month, year, or month, year. If more than one date appears on the report, use date of publication, 13. ABSTRACT: Enter an abstract giving a brief and factual 7a. TrOTAL NUMBER OF PAGES: rThe t~ otal page count summary of the document indicative of the report, even though 7a. TOTAL NUMBER OF PaAGES: The total page count | it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information, be attached. 7b. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report. be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS). (S). (C), or (U) the report was written. There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number,. KY W y subproject number, system numbers, task number, etc14. KEY WORDS: Key words are technically meaningful terms or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 96. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other report numbers (either by the originator text. The assignment of links, rules, and weights is optional. or by the sponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any lim- itations on further dissemination of the report. other than those UNCLASS I FIED Security Classification

UNIVERSITY OF MICHIGAN 3 9015 02493 8378