This book began as a series of lecture notes for a course called Introduc­ tion to Adaptive Systems which I developed for undergraduate Computing Science majors at the University of Alberta and first taught in 1973. The objective of the course has been threefold: (l) to expose undergraduate computer scientists to a variety of subjects in the theory and application of computation, subjects which are too often postponed to the graduate level or never taught at all; (2) to provide undergraduates with a background sufficient to make them effective participants in graduate level courses in Automata Theory, Biological Information Processing, and Artificial Intelligence; and (3) to present a personal viewpoint which unifies the apparently diverse aspects of the subject matter covered. All of these goals apply equally to this book, which is primarily designed for use in a one semester undergraduate computer science course. I assume the reader has a general knowledge of computers and programming, though not of particular machines or languages. His mathematical background should include basic concepts of number systems, set theory, elementary discrete probability, and logic.

Inhalt

I Information and automata.- 1 Communication theory.- 1.1 Communication systems.- 1.2 Information and entropy.- 1.3 Channel capacity.- Exercises.- 2 Coding information.- 2.1 Efficient codes.- 2.2 Error correcting codes.- Exercises.- 3 Finite automata.- 3.1 Modular nets.- 3.2 State transition functions.- 3.3 Regular expressions.- Exercises.- 4 Turing machines.- 4.1 Turing and Wang formulations.- 4.2 Universal Turing machines.- 4.3 Computability and unsolvability.- 4.4 Grammars and machines.- Exercises.- 5 Cellular automata.- 5.1 Von Neumann's machines.- 5.2 Arbib's machine.- Exercises.- II Biological information processing.- 6 Biochemical coding and control.- 6.1 Biological cells.- 6.2 Informational macromolecules.- 6.3 The genetic code.- 6.4 Biochemical control processes.- Exercises.- 7 Genetic information transmission.- 7.1 Recombination in viruses and bacteria.- 7.2 Recombination in higher organisms.- 13 Populations and evolution.- Exercises.- 8 Neural information transmission.- 8.1 Neural architecture.- 8.2 Neurons and synapses.- 8.3 Neural signals 101 Bibliography.- Exercises.- 9 Neural input-output.- 9.1 Reflex and motor systems.- 9.2 Sensory systems.- 9.3 The visual system.- Exercises.- 10 Computer simulation models.- 10.1 Kabrisky's vision model.- 10.2 Finley's cell assembly model.- 10.3 Weinberg's E. coli model.- Exercises.- III Artificial intelligence.- 11 Pattern recognition.- 11.1 Perceptrons.- 11.2 A feature detection system.- 11.3 Scene analysis.- Exercises.- 12 Game playing.- 12.1 Game trees.- 12.2 The Samuel checker player.- 12.3 Chess playing.- Exercises.- 13 Theorem proving.- 13.1 Logic systems.- 13.2 The Logic Theorist.- 13.3 Resolution theorem proving.- Exercises.- 14 Problem solving.- 14.1 Problem representations.- 14.2 The General Problem Solver.- 14.3 Other problem solving programs.- Exercises.- 15 Natural language processing.- 15.1 Linguistics.- 15.2 The work of Quillian.- 15.3 The work of Winograd.- 15.4 The work of Schank.- Exercises.