In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin's NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started the population process of these new classes assigning several undecidable problems to them. We justify that some super-Turing models of computation, i.e., models going beyond Turing machines, are tremendously expressive and they allow to accept arbitrary languages over a given alphabet including those undecidable ones. We prove also that one of such super-Turing models of computation - the \$-Calculus, designed as a tool for automatic problem solving and automatic programming, has also such tremendous expressiveness. We investigate also completeness of cost metrics and meta-search algorithms in \$-calculus.

In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are ℋ-complete (hypercomputation complete). We propose also two other classes: 𝒰-complete (universal complete) and 𝒟-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.

Cloud computing deals with accessing services and resources in distributed environments needed to perform functions with dynamically changing needs. The cloud provides a virtualization of resources that maintains and manages itself. The DIME Network Architecture was introduced as a new approach to handle dynamic aspects of cloud computing, i.e., self-repairs, auto-scaling, live-migration, end-to-end service transaction security, and so on. It was hypothesized that for such self-reference features, conventional Turing machines fall short. In this paper, we investigate this claim in more depth.

Expressiveness and convergence of evolutionary computation (EC) is studied using the evolutionary automata model. It turns out that all standard classes of evolutionary automata are equally expressive when they operate in the terminal mode, i.e. in the terminal mode, evolutionary finite automata (EFA) are as expressive as evolutionary pushdown automata, evolutionary linearly bounded automata, evolutionary Turing machines or evolutionary inductive Turing machines. For example, the simplest class of evolutionary automata, EFA, can accept all recursively enumerable languages (i.e. EFA have power of Turing machines) and even more—they can accept languages that are not recursively enumerable. Due to utilization of evolutionary automata, we obtain also very simple sufficient conditions for convergence of EC.

The aim of this paper is the development of foundations for evolutionary computation. We introduce and study two classes of evolutionary automata: bounded and periodic evolutionary machines.

In this paper we study expressiveness of evolutionary computation. To do so we introduce evolutionary automata and define their several subclasses. To our surprise, we got the result that evolving finite automata by finite automata leads outside its class, and allows to express for example pushdown automata or Turing machines. This explains partially why Larry Fogel restricted representation in Evolutionary Programming to finite state machines only. The power of evolution is enormous indeed!

The aim of this paper is the development of foundations for evolutionary computations. To achieve this goal, a mathematical model of evolutionary automata is introduced and studied. The main classes of evolutionary automata considered in this paper are evolutionary Turing machines and evolutionary inductive Turing machines. Various subclasses and modes of evolutionary computation are defined. Problems of existence of universal objects in these classes are explored. Relations between Turing machines, inductive Turing machines, evolutionary Turing machines, and evolutionary inductive Turing machines are investigated.

The goal of this paper is to study the process of evolution of evolution. In other words, we study evolution that adapts evolutionary algorithms in parallel with their solutions. For this purpose, we define and investigate several extensions of evolutionary Turing machine model: self-constructing evolutionary Turing machines (SETM), self-constructing evolutionary Turing machines with a basic constructor (SBETM), self-constructing evolutionary Turing machines with a basic constructor and control information (CSBETM), and self-constructing evolutionary Turing machines with evolvable control information (CSETM). Such properties as expressiveness and complexity of different types of self-constructing evolutionary Turing machines are studied. It is demonstrated how self-constructive abilities allow one to essentially increase efficiency of evolutionary processes in general and evolutionary computations, in particular. We also investigate computation and construction universatility in the context of these new models.

In 1995 Russell and Norvig presented a unified approach to AI as the area based on bounded rational agents using utilities to direct search for problem solving under bounded resources. This paper extends this work further in the direction of the computational theory targeting intractable and undecidable problems and based on resource bounded computation and process algebras.

It is interesting that typically in the proof of convergence of evolutionary algorithms only elitist selection is considered. In this paper, we stress out that truly in reaching optimum of the fitness function completeness of search plays probably even more important role. The elitist selection helps in reaching the optimum. It allows to converge faster and not to lose the optimum in cases when we are uncertain that the optimum has been reached. An evolutionary search using elitist selection, but being incomplete, will not reach the optimum. This paper provides sufficient conditions for finding the best (optimal) solutions, or the best (totally optimal) solutions with minimal search costs. To do that we utilized a new formal model of evolutionary computation the evolutionary Turing machine. The results are applicable both to genetic algorithms, genetic programming, evolution strategies and evolutionary programming. The problem of finding total optimum, optimizing together the quality of solution together with an evolutionary algorithm is considered as a multiobjective optimization allowing to tackle real-world problems where the complexity of evolutionary search becomes an issue. A new classification of evolutionary procedures into easy, hard, and solvable in the limit classes, is proposed.

In This work we present a unified view of AI inspired by ideas from evolutionary computation as design of bounded rational agents. The approach specifies optimal programs rather than optimal actions, and is based on process algebras and anytime algorithms. The search method described in This work is so general than many other search algorithms, including evolutionary search methods, become its special case. We present a practical design of the programming language and environment targeting real-time complex domains. As AI systems move into more complex domains, all problems become real-time, because the agent never have long enough time to solve the decision problem exactly.

This paper examines the limitations of Turing Machines as a complete model of computation, and presents several models that extend Turing Machines. Dynamic interaction of clients and servers on the Internet, an infinite adaptation from evolutionary computation, and robots sensing and acting are some examples of areas that cannot be properly described using Turing Machines and algorithms. They require new models of computation going beyond Turing Machines. We refer to such new models as superTuring models of computation. Three superTuring models of computation, namely Interaction Machines, the π calculus and the $-calculus are presented and explained, focussing on why they are better for the solution of computational problems. We expect that superTuring computation will become the central programming paradigm in the future.

We return to the no free lunch theorem, which is one of the most important theorems from the evolutionary computation foundations. We show that the no free lunch theorem can be interpreted as a trivial property of recursively enumerable languages. We demonstrate that if we consider not all problems and cost functions, i.e., a nontrivial property, the problem of finding the best evolutionary algorithm becomes Turing machine undecidable. We also demonstrate, that in spite of this negative result, the task of search for the best evolutionary computation operator is not so futile. In fact, evolutionary computation itself, being nonalgorithmic, may allow to find the best evolutionary operator in infinity, and to increase indefinitely its quality in the finite time.

Evolutionary computation (EC) has traditionally been used for the solution of hard optimization problems. In the general case, solutions found by evolutionary algorithms are satisficing, given current resources and constraints, but not necessarily optimal. Under some conditions, evolutionary algorithms are guaranteed (in infinity) to find an optimal solution. However, evolutionary techniques are not only helpful for dealing with intractable problems. In this paper, we demonstrate, that EC is not restricted to algorithmic methods, and is more expressive than Turing machines.

Evolutionary computation in its essence represents a multi-agent competitive probabilistic search. It is useful for solutions of polynomial and hard optimization problems. The solutions found by evolutionary algorithms are not guaranteed to be optimal and evolutionary search is computationally very expensive. Using a generic -calculus approach to AI, based on process algebras and anytime algorithms, we show that evolutionary search can be considered a special case of -calculus k/spl Omega/-search, and we present some results about completeness, optimality and search costs for evolutionary computation. The main result of the paper is to demonstrate how using -calculus to make evolutionary computation totally optimal, i.e., how to allow to find the best quality solution with minimal search cost.

The Applied Research Laboratory Penn State University "Ocean SAmpling MObile network" (SAMON) Project is developing the simulation testbed for the oceanographic communities interactions through the Web interface and the simulation based design of Autonomous Ocean Sampling Program missions. In this paper, a current implementation of the SAMON is presented, and a formal model based on interactive automata is described. The basic model is extended by process algebra constructs to handle mobility, evolution and learning. To allow cooperation of heterogeneous vehicles a generic behavior message-passing language is presented.

The paper deals with a generic solution of the Mutual Exclusion Problem using semaphores only. We use in the solution weakly fair binary semaphores and (not necessarily fair) semaphores with initial value k. All semaphores are simple in that the P and V operations on them are paired in the natural way avoiding split semaphores. No auxiliary shared variables are used. We define a general form of the mutual exclusion problem. We claim: (1) All mutual exclusion problems can be solved using only simple semaphores. (2) All mutual exclusion problems can be solved fairly (with bounded waiting) using simple semaphores (weakly fair binary and initially–k; semaphores). We give some bounds on how many semaphores are needed for standard problems. The solutions given may be inefficient: a mutual exclusion problem which can be solved in linear time and space with shared variables may require exponentially many semaphores.

The paper concentrates on the problem of integrating genetic programming, neural networks, autonomous agents with some symbolic AI techniques. For this purpose, it introduces and employs the S-calculus, which is a general model of computation with a quantitative aspect (cost) allowing naturally to express optimization and modification in dynamic parallel AI systems. The papers presents basic operators of the calculus, and a basic inference engine, so called modifying algorithm, used for problem solving. Next the approach is illustrated through a series of examples from various domains, including symbolic and subsymbolic systems.

The design, specification, and preliminary implementation of the SEMAL language, based upon the Calculus of Self-modifiable Algorithms model of computation is presented. A Calculus of Self-modifiable Algorithms is a universal theory for parallel and intelligent systems, integrating different styles of programming, and applied to a wealth of domains of future generation computers. It has some features from logic, rule-based, procedural, functional, and object-oriented programming. It has been designed to be a relatively universal tool for AI similar to the way Hoare’s Communicating Sequential Processes and Milner’s Calculus of Communicating Systems are basic theories for parallel systems. The formal basis of this approach is described. The model is used to derive a new programming paradigm, so-called cost languages and new computer architectures cost-driven computers. As a representative of cost languages, the SEMAL language is presented.

According to many authors, neural networks and adaptive expert systems may provide the foundations of sixth-generation computers. Neural networks use lower hardware-like concepts and they are based on continuous and numeric type computation. On the other hand, adaptive expert systems use inference rules and perform high-level symbolic computations. the approaches may seem to be totally different, but they do exhibit similar properties: learning, flexibility, parallel search, generalization, and association. This article takes up the problem of the design of a common model for neural networks and adaptive expert systems. For this purpose the Calculus of Self-Modifiable Algorithms, a general tool for problem solving, is used. This joint approach to expert systems and neural networks emphasize their analogies, rather than their differences. © 1993 John Wiley & Sons, Inc.