Fixed Points for Algorithmic Classes

M. Burgin

Let A be a class of algorithms over a set X and E be a set of functions having the form f : X^{m} → X^{n} where n and m are arbitrary natural numbers. \underline{Definition 1.} A one-to-one mapping u : A → X is called a constructive internal naming of A if u^{−}1 and u are defined by some algorithms in A. \underline{Remark.} When X = N, then u is called an enumeration. \underline{Definition 2.} A mapping F:A → E is called a natural projection if for any algorithm A from A and any x from X we have F (A(x)) = A(x). \underline{Definition 3.} A function K(z, x) from E (algorithm H(z, x) from A) is called universal in E (in A) at the level n if for any g(x) from E (any A(x) from A) for some fixed z = a and any x from X we have K(a, x) = g(x)(H(a, x) = A(x)). \underline{Theorem 1.} A has a universal algorithm iff E has a universal function. \underline{Definition 4.} A oneto-one mapping u : X^{n} → X is called a linearization for the level n. Let us assume that E contains universal functions and linearization for each level n and all its iterations w(z(x)) = K(z, x) where is a universal algorithm in A. \underline{Algorithmic Fixed Point Theorem.} For any A(x_{1}, ..., x_{n} + 1) from A there is such B(x_{1}, ..., x_{n}) from A that w(A(x_{1}, ..., x_{n}, B(x_{1}, ..., x_{n}))) = w(B(x_{1}, ..., x_{n})). \underline{Corollary 1.} For any A(x) from A there is such a from X that w(A(a)) = w(a). Let U be some universal class of recursive algorithms. \underline{Corollary 2 (Kleene Fixed Point Theorem).} For any A(x_{1}, ..., x_{n} + 1) from U there is such B(x_{1}, ..., x_{n}) from U that w(A(x_{1}, ..., x_{n}, B(x_{1}, ..., x_{n}))) = w(B(x_{1}, ..., x_{n})). Let V be some universal class of recursive algorithms[M. Burgin, Super-recursive algorithms as a tool for high performance computing, High Performance Computing, Proceedings, San Diego, 1999]. \underline{Corollary 3.} For any A(x_{1}, ..., x_{n} +1) from V there is such B(x_{1}, ..., x_{n}) from V that w(A(x_{1}, ..., x_{n}, B(x_{1}, ..., x_{n}))) = w(B(x_{1}, ..., x_{n})).

Address: University of Southern California, Los Angeles, CA 90089, USA

E-mail: mburgin@pollux.usc.edu