Skip navigation

Theory of Computation

  • Page 2 of 4

Randomization is an important tool in the design of algorithms, and the ability of randomization to provide enhanced power is a major research topic in complexity theory. Noam Nisan continues the investigation into the power of randomization and the relationships between randomized and deterministic complexity classes by pursuing the idea of emulating randomness, or pseudorandom generation.


There is increasing interest in genetic programming by both researchers and professional software developers. These twenty-two invited contributions show how a wide variety of problems across disciplines can be solved using this new paradigm.

New Directions

Classical computationalism—-the view that mental states are computational states—-has come under attack in recent years. Critics claim that in defining computation solely in abstract, syntactic terms, computationalism neglects the real-time, embodied, real-world constraints with which cognitive systems must cope. Instead of abandoning computationalism altogether, however, some researchers are reconsidering it, recognizing that real-world computers, like minds, must deal with issues of embodiment, interaction, physical implementation, and semantics.

Too often, designers of computer systems, both hardware and software, use models and concepts that focus on the artifact while ignoring the context in which the artifact will be used. According to this book, that assumption is a major reason for many of the failures in contemporary computer systems development. It is time for designers and users to join forces in the design of computer systems.

Automated reasoning has matured into one of the most advanced areas of computer science. It is used in many areas of the field, including software and hardware verification, logic and functional programming, formal methods, knowledge representation, deductive databases, and artificial intelligence. This handbook presents an overview of the fundamental ideas, techniques, and methods in automated reasoning and its applications. The material covers both theory and implementation.

Automated reasoning has matured into one of the most advanced areas of computer science. It is used in many areas of the field, including software and hardware verification, logic and functional programming, formal methods, knowledge representation, deductive databases, and artificial intelligence. This handbook presents an overview of the fundamental ideas, techniques, and methods in automated reasoning and its applications. The material covers both theory and implementation.


Genetic programming is a form of evolutionary computation that evolves programs and program-like executable structures for developing reliable time- and cost-effective applications. It does this by breeding programs over many generations, using the principles of natural selection, sexual recombination, and mutuation. This third volume of Advances in Genetic Programming highlights many of the recent technical advances in this increasingly popular field.


Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation

"Simulation," writes Gary Flake in his preface, "becomes a form of experimentation in a universe of theories. The primary purpose of this book is to celebrate this fact."In this book, Gary William Flake develops in depth the simple idea that recurrent rules can produce rich and complicated behaviors.

Exploratory Essays in Philosophical Computer Modeling


Philosophical modeling is as old as philosophy itself; examples range from Plato's Cave and the Divided Line to Rawls's original position. What is new are the astounding computational resources now available for philosophical modeling. Although the computer cannot offer a substitute for philosophical research, it can offer an important new environment for philosophical research.

Computational Models of Institutions and Groups

The globalization of the economy, increasing number of transnational organizations, and rapid changes in robotics, information, and telecommunication technologies are just a few of the factors significantly altering organizational time scales, forms, complexity, and environments. Time scales have shrunk, new organizational forms are emerging, and organizational environments are expanding and mutating at unprecedented rates. Computational modeling affords opportunities to both understand and respond to these complex changes.

  • Page 2 of 4