The $-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems

The $-calculus is the extension of the pi-calculus, built around the central notion of cost and allowing infinity in its operators. We propose the $-calculus as a more complete model for problem solving to provide a support to handle intractability and undecidability. It goes beyond the Turing Machine model. We define the semantics of the $-calculus using a novel optimization method (the k Omega-optimization), which approximates a nonexisting universal search algorithm and allows the simulation of many other search methods. In particular, the notion of total optimality has been utilized to provide an automatic way to deal with intractability of problem solving by optimizing together the quality of solutions and search costs. The sufficient conditions needed for completeness, optimality and total optimality of problem solving search are defined. A very flexible classification scheme of problem solving methods into easy, hard and solvable in the limit classes has been proposed. In particular, the third class deals with non-recursive solutions of undecidable problems. The approach is illustrated by solutions of some intractable and undecidable problems. We also briefly overview two possible implementations of the $-calculus. (c) 2007 Elsevier B.V. All rights reserved.