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.     

On the computability of the Steenrod squares

We give explicitely the formulas of a sequence of morphisms which measure the failure of commutativity of the cup product on the cochain level, provided that we work with simplicial sets; these formulas are established in terms of the component morphisms of a given Eilenberg-Zilber contraction. As a consequence, in the case in which the simplicial set is finite in each dimension, we obtain an algorithm for calculating Steenrod squares.     

Computability and complexity of ray tracing

The ray-tracing problem is, given an optical system and the position and direction of an initial light ray, to decide if the light ray reaches some given final position. For many years ray tracing has been used for designing and analyzing optical systems. Ray tracing is now used extensively in computer graphics to render scenes with complex curved objects under global illumination. We show that ray-tracing problems in some three-dimensional simple optical systems (purely geometrical optics) are undecidable. These systems may consist of either reflective objects that are represented by rational quadratic equations, or refractive objects that are represented by rational linear equations. Some problems in more restricted models are shown to be PSPACE-hard or sometimes in PSPACE. A preliminary version of this paper appeared as “The Computability and Complexity of Optical Beam Tracing” in theProceedings of the 31st Annual Symposium on Foundations of Computer Science, October 1990, Vol. I, pp. 106–114. The research of J. H. Reif and A. Yoshida was supported in part by Air Force Contract No. AFOSR-87-0386, DARPA/ARO Contract No. DAAL03-88-K-0195, DARPA/ISTO Contract No. N00014-88-K-0458, and NASA subcontract 550-63 of primecontract NASS-30428. J.D. Tygar's research was supported in part by the Defense Advanced Research Projects Agency under Contract No. F33615-87-C-1449 and by a National Science Foundation Presidential Young Investigator Award under Contract No. CCR-8858087.     

Representation theorems for transfinite computability and definability

 We show how Kreisel's representation theorem for sets in the analytical hierarchy can be generalized to sets defined by positive induction and use this to estimate the complexity of constructions in the theory of domains with totality. Received: 21 January 1998 / Published online: 2 September 2002     

Computability of Minimizers and Separating Hyperplanes

We prove in recursive analysis an existence theorem for computable minimizers of convex computable continuous real-valued functions, and a computable separation theorem for convex sets in ?^m. Mathematics Subject Classification: 03F60, 52A40.     

The canonical Ramsey theorem and computability theory

Using the tools of computability theory and reverse mathematics, we study the complexity of two partition theorems, the Canonical Ramsey Theorem of Erdös and Rado, and the Regressive Function Theorem of Kanamori and McAloon. Our main aim is to analyze the complexity of the solutions to computable instances of these problems in terms of the Turing degrees and the arithmetical hierarchy. We succeed in giving a sharp characterization for the Canonical Ramsey Theorem for exponent 2 and for the Regressive Function Theorem for all exponents. These results rely heavily on a new, purely inductive, proof of the Canonical Ramsey Theorem. This study also unearths some interesting relationships between these two partition theorems, Ramsey's Theorem, and König's Lemma.

     

Computability by means of effectively definable schemes and definability via enumerations

Research partially supported by the Committee for Science at the Council of Ministers, Contract #247, 1987     

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.     

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.     

On the equivalence of stationary and finite-nonstationary nondeterministic automata

The synthesis problem for a generalized stationary nondeterministic automaton equivalent to an arbitrary given generalized finite-nonstationary nondeterministic automation is solved. A synthesis algorithm is described.     

Pincherle's theorem in reverse mathematics and computability theory

We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first ‘local-to-global’ principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms are necessary to prove Pincherle's theorem, does not have an unique or unambiguous answer, in contrast to compactness. We establish similar differences for the computational properties of compactness and Pincherle's theorem. We establish the same differences for other local-to-global principles, even going back to Weierstrass. We also greatly sharpen the known computational power of compactness, for the most shared with Pincherle's theorem however. Finally, countable choice plays an important role in the previous, we therefore study this axiom together with the intimately related Lindelöf lemma.     

On the torus automorphisms: analytic solution, computability and quantization

The exact solution of the classical torus automorphism, which partial case is Arnold Cat map is obtained and compared with the numerical solution. The torus, considered as the classical phase space admits the quantization in terms of the Weyl pair. The remarkable fact is that quantum map, as the evolution with respect to the discrete time, preserves the Weyl commutation relation. We have obtained also the operator solution of this quantum torus automorphism.