Investigations on the approximability and computability of the Hilbert transform with applications

It was recently shown that on a large class of important Banach spaces there exist no linear methods which are able to approximate the Hilbert transform from samples of the given function. This implies that there is no linear algorithm for calculating the Hilbert transform which can be implemented on a digital computer and which converges for all functions from the corresponding Banach spaces. The present paper develops a much more general framework which also includes non-linear approximation methods. All algorithms within this framework have only to satisfy an axiom which guarantees the computability of the algorithm based on given samples of the function. The paper investigates whether there exists an algorithm within this general framework which converges to the Hilbert transform for all functions in these Banach spaces. It is shown that non-linear methods give actually no improvement over linear methods. Moreover, the paper discusses some consequences regarding the Turing computability of the Hilbert transform and the existence of computational bases in Banach spaces.     

Mathematical Theory of Phenotypical Selection

A general concept of phenotypical structure over a genotypical structure is developed. The direct decompositions of multilocus phenotypical structures are considered. Some aspects of phenotypical heredity are described in terms of graph theory. The acyclic phenotypical structures are introduced and studied on this base. The evolutionary equations are adjusted to the phenotypical selection. It is proved that if a phenotypical structure is acyclic then the set of fixed points of the corresponding evolutionary operator is finite except for a proper algebraic subset of the operator space. Some applications of this theorem are given.     

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.     

A Real Number Structure that is Effectively Categorical

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers.     

Physically-relativized Church-Turing Hypotheses: Physical foundations of computing and complexity theory of computational physics

We turn the physical Church-Turing Hypothesis from an ambiguous source of sensational speculations into a (collection of) sound and well-defined scientific problem(s):Examining recent controversies and causes for misunderstanding concerning the state of the Church-Turing Hypothesis (CTH), it is suggested to study the CTH ‘sharpened’ relative to an arbitrary but specific physical theory - rather than vaguely referring to “nature” in general. For this purpose we apply, and emphasize the utility of, concepts from philosophy: physical structuralism, ontological commitment, and constructivism. This general approach is then illustrated with some exemplary results on computability and complexity theory in computational physics.     

The Theory of Finite Models without Equal Sign

In this paper, it is the first time ever to suggest that we study the model theory of all finite structures and to put the equal sign in the same situtation as the other relations. Using formulas of infinite lengths we obtain new theorems for the preservation of model extensions, submodels, model homomorphisms and inverse homomorphisms. These kinds of theorems were discussed in Chang and Keisler＇s Model Theory, systematically for general models, but Gurevich obtained some different theorems in this direction for finite models. In our paper the old theorems manage to survive in the finite model theory. There are some differences between into homomorphisms and onto homomorphisms in preservation theorems too. We also study reduced models and minimum models. The characterization sentence of a model is given, which derives a general result for any theory T to be equivalent to a set of existential-universal sentences. Some results about completeness and model completeness are also given.     

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.     

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.     

An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system

This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self‐delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program‐size complexity H (s) of a given finite binary string s. In the standard way, H (s) is defined as the length of the shortest input string for U to output s. In the other way, the so‐called universal probability m is introduced first, and then H (s) is defined as –log₂ m (s) without reference to the concept of program‐size. Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator‐valued measure (POVM) in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour‐El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi‐POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi‐POVM. The validity of this definition is discussed. In what follows, we introduce an operator version (s) of H (s) in a Hilbert space of infinite dimension using a universal semi‐POVM, and study its properties. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Linear codes and modular curves

Results of recent investigations at the juncture of coding theory, the theory of computability, and algebraic geometry over finite fields are presented. The basic problems of the asymptotic theory of codes and Goppa's construction of codes on the basis of algebraic curves are presented, and a detailed algorithmic analysis is given of the codes arising on the modular curves of elliptic modules of V. G. Drinfel'd.Translated from Itogi Nauki i Tekhniki, Seriya Sovremennye Problemy Matematiki, Noveishie Dostizheniya, Vol. 25, pp. 209–257, 1984.     

Shape sensitivity analysis of thin-shell structures

This paper presents explicit formulas for shape sensitivity analysis of thin shell structures. The curvature distribution is the design to be determined. The thin-shell theory employed is the general Koiter model in the Cartesian coordinates. For the shape sensitivity formulation, both the direct differentiation method and the material derivative concept have been used. The two formulations are shown to be equivalent. A computer program based on these formulations has been developed and applied to examples. The shape sensitivity results obtained have been compared to those obtained by finite differencing.     

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.     

Complexity of games and bounded rationality

An attempt is made to propose a concept of limited rationality for choice junctions based on computability theory in computer science.

Starting with the observation that it is possible to construct a machine simulating strategies of each individual in society, one machine for each individual's preference structure, we identify internal states of this machine with strategies or strategic preferences. Inputs are possible actions of other agents in society thus society is effectively operating as a game generated by machines. The main result states that effective realization of game strategies bound by the “complexity of computing machines'.     

Group actions on algebras and the graded Lie structure of Hochschild cohomology

Hochschild cohomology governs deformations of algebras, and its graded Lie structure plays a vital role. We study this structure for the Hochschild cohomology of the skew group algebra formed by a finite group acting on an algebra by automorphisms. We examine the Gerstenhaber bracket with a view toward deformations and developing bracket formulas. We then focus on the linear group actions and polynomial algebras that arise in orbifold theory and representation theory; deformations in this context include graded Hecke algebras and symplectic reflection algebras. We give some general results describing when brackets are zero for polynomial skew group algebras, which allow us in particular to find noncommutative Poisson structures. For abelian groups, we express the bracket using inner products of group characters. Lastly, we interpret results for graded Hecke algebras.     

Asymptotically optimal pointwise and minimax quickest change-point detection for dependent data

We consider the quickest change-point detection problem in pointwise and minimax settings for general dependent data models. Two new classes of sequential detection procedures associated with the maximal “local” probability of a false alarm within a period of some fixed length are introduced. For these classes of detection procedures, we consider two popular risks: the expected positive part of the delay to detection and the conditional delay to detection. Under very general conditions for the observations, we show that the popular Shiryaev–Roberts procedure is asymptotically optimal, as the local probability of false alarm goes to zero, with respect to both these risks pointwise (uniformly for every possible point of change) and in the minimax sense (with respect to maximal over point of change expected detection delays). The conditions are formulated in terms of the rate of convergence in the strong law of large numbers for the log-likelihood ratios between the “change” and “no-change” hypotheses, specifically as a uniform complete convergence of the normalized log-likelihood ratio to a positive and finite number. We also develop tools and a set of sufficient conditions for verification of the uniform complete convergence for a large class of Markov processes. These tools are based on concentration inequalities for functions of Markov processes and the Meyn–Tweedie geometric ergodic theory. Finally, we check these sufficient conditions for a number of challenging examples (time series) frequently arising in applications, such as autoregression, autoregressive GARCH, etc.     

Incomplete observations in a linear identification problem

The article considers a highly general linear identification problem for an unknown vector parameter from output observations. The main focus is on sufficiency of a finite number of observations of the output signal for unique estimation of the unknown vector parameter. Two general sufficient conditions are obtained, ensuring unique computability of the unknown vector parameter from finitely many observations of the output signal.     

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.     

A constructive method for solving the displacement boundary-value problem of elastostatics by use of global basis systems

In this paper we are concerned with the three-dimensional homogeneous isotropic elastostatic boundary-value problem. Global basis vector fields are shown to be constructive structures for approximating the solution. The theoretical tool is a regularity condition developed from the classical integral equation approach. The paper ends with some reflections on the practical computability and numerical applicability.