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.     

Terminating general recursion

In Martin-Löf's type theory, general recursion is not available. The only iterating constructs are primitive recursion over natural numbers and other inductive sets. The paper describes a way to allow a general recursion operator in type theory (extended with propositions). A proof rule for the new operator is presented. The addition of the new operator will not destroy the property that all well-typed programs terminate. An advantage of the new program construct is that it is possible to separate the termination proof of the program from the proof of other properties.Dedicated to Peter Naur on the occasion of his 60:th birthday.     

Linear homeomorphisms of non-classical Hilbert spaces

Let K be a complete infinite rank valued field. In [4] we studied Norm Hilbert Spaces (NHS) over K i.e. K-Banach spaces for which closed subspaces admit projections of norm ≤ 1. In this paper we prove the following striking properties of continuous linear operators on NHS. Surjective endomorphisms are bijective, no NHS is linearly homeomorphic to a proper subspace (Theorem 3.7), each operator can be approximated, uniformly on bounded sets, by finite rank operators (Theorem 3.8). These properties together — in real or complex theory shared only by finite-dimensional spaces — show that NHS are more ‘rigid’ than classical Hilbert spaces.     

On the Relations Between Discrete and Continuous Complexity Theory

Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over the integers.     

An Intuitionistic Axiomatisation of Real Closed Fields

We give an intuitionistic axiomatisation of real closed fields which has the constructive reals as a model. The main result is that this axiomatisation together with just the decidability of the order relation gives the classical theory of real closed fields. To establish this we rely on the quantifier elimination theorem for real closed fields due to Tarski, and a conservation theorem of classical logic over intuitionistic logic for geometric theories.     

Selective ultrafilters and homogeneity

We develop a game-theoretic approach to partition theorems, like those of Mathias, Taylor, and Louveau, involving ultrafilters. Using this approach, we extend these theorems to contexts involving several ultrafilters. We also develop an analog of Mathias forcing for such contexts and use it to show that the proposition (considered by Laver and Prikry) “every non-trivial c.c.c. forcing adjoins Cohen-generic reals or random reals” implies the non-existence of P-points. We show that, in the model obtained by Lévy collapsing to ω all cardinals below a Mahlo cardinal ;, any countably many selective ultrafilters are mutually generic over the Solovay (Lebesgue measure) submodel. Finally, we show that a certain natural group of self-homeomorphisms of βω-ω, chosen so as to preserve selectivity of ultrafilters, in fact preserves isomorphism types.     

Variant of the variable-modulus theory of elasticity

A variant of the variable-modulus theory — a generalization of the ideas of the classical theory of elasticity in which the observed difference in the moduli of elasticity in uniaxial tension and compression and homogeneous shear is taken into account — is considered. Quasilinear expressions are proposed for the stresses in terms of the strains and the strains in terms of the stresses.Tula Polytechnic Institute. Translated from Mekhanika Polimerov, Vol. 5, No. 2, pp. 363–365, March–April, 1969.     

Quantum object as a system with memory

A quantum theory model is suggested in which non-Markovian processes play an important part. It is assumed that any quantum object is formed of local nuclei, or carriers of particle properties, and a nonlocal wave field—the memory carrier. Within the framework of this model, the solution of the problem of quantum measurements is presented. The Einstein-Podolsky-Rosen paradox and the Bell inequality are also considered.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 106, No. 2, pp. 264–272, February, 1996.Translated by V. M. Volosov.     

Fenchel duality, Fitzpatrick functions and the Kirszbraun-Valentine extension theorem

We present a new proof of the classical Kirszbraun-Valentine extension theorem. Our proof is based on the Fenchel duality theorem from convex analysis and an analog for nonexpansive mappings of the Fitzpatrick function from monotone operator theory.

     

Transformations of Feynman integrals under nonlinear transformations of the phase space

The Feynman measure is defined as a linear continuous functional on a test-function space (introduced in the paper). The functional is given by means of its Fourier transform. Not only a positive-definite correlation operator but also one without fixed sign is considered (the latter case corresponds to the so-called symplectic, or Hamiltonian, Feynman measure). The Feynman integral is the value of the Feynman measure on a function (in the test-function space). The effect on the Feynman measure of nonlinear transformations of the phase space in the form of shifts along vector fields or along integral curves of vector fields is described. Analogs of the well-known Cameron—Martin, Girsanov—Maruyama, and Ramer formulas in the theory of Gaussian measures are obtained. The results of the paper can be regarded as formulas for a change of variable in Feynman integrals.Moscow State University. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 100, No. 1, pp. 3–13, July, 1994.     

Symmetry study of the coupled Burgers system

The inverse of the recursion operator of a coupled Burgers equation is given explicitly. Three sets of infinitely many symmetries of the considered model are obtained by acting the recursion operator and it’s inverse on the trivial symmetries, space translation, identity transformation and the scaling transformation respectively. These symmetries constitute an infinite dimensional Lie algebra.     

On the triangular factorization of positive operators

An operator integral, referred to as the amplitude integral (AI) and used in the BC-method (based on boundarycontrol theory) for solving inverse problems, is systematically studied. For a continuous operator and two families of increasing subspaces, the continual analog of the matrix diagonal in the form of an AI is introduced. The convergence of the AI is discussed. An example of an operator with no diagonal is provided. The role of the diagonal in the problem of triangular factorization is elucidated. The well-known result of matrix theory stating the uniqueness of triangular factorization with a prescribed diagonal is extended. It is shown that the corresponding factor can be represented in the AI form. The correspondence between the AI and the classical representation of the triangular factor of an operator that is a sum of the identity and a compact operator is established.Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 239, 1997, pp. 45–60.This work was supported by INTAS under grant INTAS 93-1815 and by the Russian Foundation for Basic Research under grant 96-01-00666. The authors are grateful to Prof. S. N. Naboko for fruitful discussions and consultations.     

Remarks on Martin-Löf's partial type theory

In this paper we discuss Martin-Löf's partial type theory, that is type theory with general recursion, and in particular the consequences of the presence of a fixed point operator. We model Martin-Löf's logical framework domain-theoretically in the category of conditional upper semi lattices and parametrizations thereof. An interpretation of a type of sets in the logical framework, which defines partial type theory with one universe, is finally described.During the preparation of this paper, the first author was supported by the Swedish Natural Science Research Council as a PhD-student in mathematical logic.     

An estimation of reliability of unidirectional composites by catastrophe theory

In the present work, interest is centered on the theory of fracture and practical approaches to reliability estimation of unidirectional composite materials which are based on it. Fracture mechanics is considered not as a theory of macrocracks but as mechanics of fracture mechanisms of the composites with allowance made for probability estimation. A model of composite material with fibers eliminated from the carrying scheme and parameters specific to the stress-strain-damage state (SSDS) was considered. According to the model, during loading, self-accelerated energy rise is accounted for by structural damages growth — the catastrophe takes place. The model allows us to calculate the critical stress. The composites redistribute forces from overloading zones to neighboring ones by microstructural deformations and damages. It is the effect of reservation of carrying ability. Due to this effect, low-value probability of fracture is sufficiently less for the composite than for homogeneous materials. The approach allows us to evaluate the reliability function for both static loading and fatigue.Presented at the Ninth International Conference on the Mechanics of Composite Materials, Riga, October, 1995.Computing Center of the Russian Academy of Sciences, Krasnoyarsk, Russia. Published in Mekhanika Kompozitnykh Materialov, Vol. 32, No. 4, pp. 539–548, July–August, 1996.     

Quantum mechanics in Riemannian spacetime. II. Operators of observables

The formulation of the generally covariant analog of standard (nonrelativistic) quantum mechanics in a general Riemannian spacetime begun in earlier studies of the author is continued with the introduction of asymptotic (with respect toc ^–2) operators of the spatial position of a spinless particle and of the projection of its momentum onto an arbitrary spacetime direction. The connection between the position operator and the generalization of theV _1,3 Newton—Wigner operator is established. It is shown that the projection of the momentum onto the 4-velocity of the frame of reference (the energy operator) is unitarily equivalent to the Hamiltonian in the Schrödinger equation.Joint Institute for Nuclear Research, Dubna. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 90, No. 3, pp. 412–423, March, 1992.     

Schnorr trivial reals: a construction

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}A real is Martin-L?f (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. This material is based upon work supported under a National Science Foundation Graduate Research Fellowship and appears in the author’s Ph.D. thesis. A preliminary version of this paper appeared in Electronic Notes in Theoretical Computer Science     

On some issues related to the moment problem for the band matrices with operator elements

The connection between the classical moment problem and the spectral theory of second order difference operators (or Jacobi matrices) is a thoroughly studied topic. Here we examine a similar connection in the case of the second order operator replaced by an operator generated by an infinite band matrix with operator elements. For such operators, we obtain an analog of the Stone theorem and consider the inverse spectral problem which amounts to restoring the operator from the moment sequence of its Weyl matrix. We establish the solvability criterion for such problems, find the conditions ensuring that the elements of the moment sequence admit an integral representation with respect to an operator valued measure and discuss an algorithm for the recovery of the operator. We also indicate a connection between the inverse problem method and the Hermite-Padé approximations.