The computability potential scale of all finite algebras

Comparison is suggested between the computability potential scales of algebras of different cardinalities and prove the undecidability of the elementary theory of the computability potential scale of all finite algebras.     

Dense computability structures

We examine computability structures on a metric space and the relationships between maximal, separable and dense computability structures. We prove that in a computable metric space which has the effective covering property and compact closed balls for a given computable sequence which is a metric basis there exists a unique maximal computability structure which contains that sequence. Furthermore, we prove that each maximal computability structure on a convex subspace of Euclidean space is dense. We also examine subspaces of Euclidean space on which each dense maximal computability structure is separable and prove that spheres, boundaries of simplices and conics are such spaces.     

Computable Real-Valued Functions on Recursive Open and Closed Subsets of Euclidean Space

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.     

Conditional computability of real functions with respect to a class of operators

For any class of operators which transform unary total functions in the set of natural numbers into functions of the same kind, we define what it means for a real function to be uniformly computable or conditionally computable with respect to this class. These two computability notions are natural generalizations of certain notions introduced in a previous paper co-authored by Andreas Weiermann and in another previous paper by the same authors, respectively. Under certain weak assumptions about the class in question, we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. The introduced notions have some similarity with the uniform computability and its non-uniform extension considered by Katrin Tent and Martin Ziegler, however, there are also essential differences between the conditional computability and the non-uniform computability in question.     

Computability of String Functions Over Algebraic Structures Armin Hemmerling

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper.     

Computability of the ergodic decomposition

The study of ergodic theorems from the viewpoint of computable analysis is a rich field of investigation. Interactions between algorithmic randomness, computability theory and ergodic theory have recently been examined by several authors. It has been observed that ergodic measures have better computability properties than non-ergodic ones. In a previous paper we studied the extent to which non-ergodic measures inherit the computability properties of ergodic ones, and introduced the notion of an effectively decomposable measure. We asked the following question: if the ergodic decomposition of a stationary measure is finite, is this decomposition effective? In this paper we answer the question in the negative.     

欧氏空间上Co-regular集的表示式

For the computability of co-regular subsets in metric spaces, the properties of the co-regular subsets and several reasonable representations on co-regular sets have been suggested in this paper. As last, the 'weaker or stronger' relations of these representations have been revealed.     

Computability Over Structures of Infinite Signature

Continuing the paper [7], in which the Blum-Shub-Smale approach to computability over the reals has been generalized to arbitrary algebraic structures, this paper deals with computability and recognizability over structures of infinite signature. It begins with discussing related properties of the linear and scalar real structures and of their discrete counterparts over the natural numbers. Then the existence of universal functions is shown to be equivalent to the effective encodability of the underlying structure. Such structures even have universal functions satisfying the s-m-n theorem and related features. The real and discrete examples are discussed with respect to effective encodability. Megiddo structures and computational extensions of effectively encodable structures are encodable, too. As further variants of universality, universal functions with enumerable sets of program codes and such ones with constructible codes are investigated. Finally, the existence of m-complete sets is shown to be independent of the effective encodability of structures, and the linear and scalar structures are discussed once more, under this aspect.     

Effective continuities on effective topological spaces

We extend a notion of effective continuity due to Mori, Tsujii and Yasugi to real-valued functions on effective topological spaces. Under reasonable assumptions, Type-2 computability of these functions is characterized as sequential computability and the effective continuity. We investigate effective uniform topological spaces with a separating set, and adapt the above result under some assumptions. It is also proved that effective local uniform continuity implies effective continuity under the same assumptions.     

On centain decompositions of Gödel numberings

Summary We define certain decompositions of the functions that describe Gödel numberings of the partial recursive functions (Section 2). These decompositions reflect the way in which concrete Gödel numberings may be obtained from the known computability formalisms. We show that such decompositions exist for all partial recursive functions (Section 3). It turns out that there is an intimate connection between these decompositions and Blum's step counting functions which yields a suggestive interpretation of Blum's notion (Section 4). In terms of these decompositions we, finally, give an exact formulation for a basic problem in the theory of computability formalisms, which, on an intuitive level, would read as follows: Find conditions on the expressive power of one step in a given computability formalism such that all partial recursive functions can be represented within that formalism. We derive two theorems which may be regarded as a first step in a thorough study of this problem.     

Computability of measurable sets via effective topologies

We investigate in the frame of TTE the computability of functions of the measurable sets from an infinite computable measure space such as the measure and the four kinds of set operations. We first present a series of undecidability and incomputability results about measurable sets. Then we construct several examples of computable topological spaces from the abstract infinite computable measure space, and analyze the computability of the considered functions via respectively each of the standard representations of the computable topological spaces constructed. The authors are supported by grants of NSFC and DFG.     

Finding Global Minima with a Computable Filled Function

The Filled Function Method is an approach to finding global minima of multidimensional nonconvex functions. The traditional filled functions have features that may affect the computability when applied to numerical optimization. This paper proposes a new filled function. This function needs only one parameter and does not include exponential terms. Also, the lower bound of weight factor a is usually smaller than that of one previous formulation. Therefore, the proposed new function has better computability than the traditional ones.     

Approximate decidability in euclidean spaces

We study concepts of decidability (recursivity) for subsets of Euclidean spaces ?^k within the framework of approximate computability (type two theory of effectivity). A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces.     

Analytical properties of resource-bounded real functionals

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0, 1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.     

Continuous refinement equations and subdivision

This paper is concerned with the study of a general class of functional equations covering as special cases the relation which defines theup-function as well as equations which arise in multiresolution analysis for wavelet construction. We discuss various basic properties of solutions to these functional equations such as regularity, polynomial containment within the space spanned by their integer shifts and their computability by subdivision algorithms.     

Is the Mandelbrot set computable?

This work is concerned with the question whether the Mandelbrot set is computable. The computability notions that we consider are studied in computable analysis and will be introduced and discussed. We show that the exterior of the Mandelbrot set, the boundary of the Mandelbrot set, and the hyperbolic components satisfy certain natural computability conditions. We conclude that the two‐sided distance function of the Mandelbrot set is computable if the famous hyperbolicity conjecture is true. We also formulate the question whether the distance function of the Mandelbrot set is computable in terms of the escape time. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Turing oracle machines, online computing, and three displacements in computability theory

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines (a-machines). To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine (o-machine) and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form.A number of topics arose from Turing functionals including continuous functionals on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14.     

Non-computable Julia sets

We show that under the definition of computability which is natural from the point of view of applications, there exist non-computable quadratic Julia sets.

     

On the scale of local computability potentials of algebras

The concept of the scale of local computability (local program-computability possibilities) of all universal algebras is introduced. The properties of this scale are studied.