Computing Schrödinger propagators on Type-2 Turing machines

We study Turing computability of the solution operators of the initial-value problems for the linear Schrödinger equation u_t=iΔu+φ and the nonlinear Schrödinger equation of the form iu_t=-Δu+mu+|u|²u. We prove that the solution operators are computable if the initial data are Sobolev functions but noncomputable in the linear case if the initial data are L^p-functions and p≠2. The computations are performed on Type-2 Turing machines.     

A hierarchy of Turing degrees of divergence bounded computable real numbers

A real number x is f-bounded computable (f-bc, for short) for a function f if there is a computable sequence (x_s) of rational numbers which converges to x f-bounded effectively in the sense that, for any natural number n, the sequence (x_s) has at most f(n) non-overlapping jumps of size larger than 2^-n. f-bc reals are called divergence bounded computable if f is computable. In this paper we give a hierarchy theorem for Turing degrees of different classes of f-bc reals. More precisely, we will show that, for any computable functions f and g, if there exists a constant γ>1 such that, for any constant c, f(nγ)+n+cg(n) holds for almost all n, then the classes of Turing degrees given by f-bc and g-bc reals are different. As a corollary this implies immediately the result of [R. Rettinger, X. Zheng, On the Turing degrees of the divergence bounded computable reals, in: CiE 2005, June 8–15, Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 3526, 2005, Springer, Berlin, pp. 418–428.] that the classes of Turing degrees of d-c.e. reals and divergence bounded computable reals are different.     

Ordinal machines and admissible recursion theory

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory.     

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.     

Spaces of orders and their Turing degree spectra

We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s (2004) [28] investigation of orders on groups in topology and Solomon’s (2002) [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group F_n of rank n>1 has a bi-order in every Turing degree.     

Infinite Time Turing Machines With Only One Tape

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi‐tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one‐tape computable, and so the two models of infinitary computation are not equivalent. Surprisingly, the class of one‐tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one‐tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.     

Feasible Real Random Access Machines

We present a modified real RAM model which is equipped with the usual discrete and real-valued arithmetic operations and with a finite precision test <_kwhich allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). Furthermore, ourfeasible RAMhas an extended semantics which allows approximative computations. Using a logarithmic complexity measure we prove that all functions computable on a RAM in time (t) can be computed on a Turing machine in time (t²·log(t)·log log(t)). Vice versa all functions computable on a Turing machine in time (t) are computable on a RAM in time (t). Thus, our real RAM model does not only express exactly the computational power of Turing machines on real numbers (in the sense of Grzegorczyk), but it also yields a high-level tool for realistic time complexity estimations on real numbers.     

Computational bounds on polynomial differential equations

In this paper we study from a computational perspective some properties of the solutions of polynomial ordinary differential equations.We consider elementary (in the sense of Analysis) discrete-time dynamical systems satisfying certain criteria of robustness. We show that those systems can be simulated with elementary and robust continuous-time dynamical systems which can be expanded into fully polynomial ordinary differential equations in Q[π]. This sets a computational lower bound on polynomial ODEs since the former class is large enough to include the dynamics of arbitrary Turing machines.We also apply the previous methods to show that the problem of determining whether the maximal interval of definition of an initial-value problem defined with polynomial ODEs is bounded or not is in general undecidable, even if the parameters of the system are computable and comparable and if the degree of the corresponding polynomial is at most 56.Combined with earlier results on the computability of solutions of polynomial ODEs, one can conclude that there is from a computational point of view a close connection between these systems and Turing machines.     

Monotonicity and supermodularity results for the Erlang loss system

For the Erlang loss system with s servers and offered load a, we show that: (i) the load carried by the last server is strictly increasing in a; (ii) the carried load of the whole system is strictly supermodular on {(s,a)|s=0,1,… and a>0}.     

Globale klassische Lösungen des Cauchyproblems semilinearer parabolischer Differentialgleichungen

Es werden nichtlineare Differentialgleichungen der Form (∂u/∂t) + Au = f(u) in ⁿ × [0, ∞) betrachtet. Dabei ist A ein positiv definiter elliptischer Differentialoperator 2m-ter Ordnung und f eine nichtlineare glatte Funktion, die nicht schneller als ¦ u ¦^q wächst, wobei q < 1 + [4m/(n − 2m)] für n > 2m und q < ∞ für n 2m, und deren Ableitungen polynomials Wachstum besitzen. Auβerdem besitze f eine nichtpositive Stammfunktion. Unter diesen Voraussetzungen wird durch Betrachtung der zugehörigen Integralgleichung in L^{v n} und unter Benutzung der Sobolevräume gebrochener Ordnung die globale klassische Lösbarkeit des Cauchyproblems für glatte Anfangswerte gezeigt.     

Some characteristic functions of unimodal distributions

A sufficient condition of Pólya type is given for a function to be the Fourier transform of a unimodal distribution. This condition is used to show that exp(− ¦ x ¦³ − 3 ¦ x ¦) is the Fourier transform of a unimodal distribution.     

Algebras, Projective Geometry, Mathematical Logic, and Constructing the World: Intersections in the Philosophy of Mathematics of A. N. Whitehead

A. N. Whitehead (1861–1947) contributed notably to the foundations of pure and applied mathematics, especially from the late 1890s to the mid 1920s. An algebraist by mathematical tendency, he surveyed several algebras in his book Universal Algebra (1898). Then in the 1900s he joined Bertrand Russell in an attempt to ground many parts of mathematics in the newly developing mathematical logic. In this connection he published in 1906 a long paper on geometry, space and time, and matter. The main outcome of the collaboration was a three-volume work, Principia Mathematica (1910–1913): he was supposed to write a fourth volume on parts of geometries, but he abandoned it after much of it was done. By then his interests had switched to educational issues, and especially to space and time and relativity theory, where his earlier dependence upon logic was extended to an ontology of events and to a general notion of “process,” especially in human experience. These innovations led to somewhat revised conceptions of logic and of the philosophy of mathematics. © 2002 Elsevier Science (USA).A. N. Whitehead (1861–1947) contribuiu de forma marcante para os Fundamentos da Matemática Pura e Aplicada, especialmente entre o fim da década de 1890 e meados da década de 1920. Sendo um algebrista na sua vertente matemática, fez um levantamento de diversas álgebras no seu livro Universal Algebra (1898). Pouco depois de 1900 juntou-se a Bertrand Russell numa tentativa para basear várias partes da matemática sobre a lógica matemática, que se começava então a desenvolver. Nesse âmbito publicou em 1906 um longo artigo sobre geometria, espaço e tempo, e matéria. O principal resultado da colaboração foi um trabalho em três volumes, Principia Mathematica (1910–1913): estava previsto que Whitehead escrevesse um quarto volume sobre aspectos das geometrias, mas abandonou-o depois de uma boa parte já estar escrita. Por essa altura os seus interesses tinham-se voltado para questões educacionais; especialmente para o espaço e o tempo e para a teoria da relatividade, onde a sua anterior dependência da lógica se estendeu a uma ontologia de acontecimentos e a uma noção geral de “processo” especialmente na experiência humana. Estas inovações levaram a concepções um pouco revistas da lógica e da filosofia da matemática. © 2002 Elsevier Science (USA).MSC 1991 subject classifications: 00A30; 01A60; 03-03; 03A05.     

Horn clause computability

It is proved that a Turing computable functionf is computable in binary Horn clauses, which are a subset of first order logic. Moreover, it is proved that the binary Horn clauses do not need more than one function symbol. The proofs comprise computable relations that can be run efficiently as logic programs on a computer.     

Is wave propagation computable or can wave computers beat the turing machine?

According to the Church-Turing Thesis a number function is computableby the mathematically defined Turing machine if and only ifit is computable by a physical machine. In 1983 Pour-El andRichards defined a three-dimensional wave u(t,x) such that theamplitude u(0,x) at time 0 is computable and the amplitude u(1,x)at time 1 is continuous but not computable. Therefore, theremight be some kind of wave computer beating the Turing machine.By applying the framework of Type 2 Theory of Effectivity (TTE),in this paper we analyze computability of wave propagation.In particular, we prove that the wave propagator is computableon continuously differentiable waves, where one derivative islost, and on waves from Sobolev spaces. Finally, we explainwhy the Pour-El-Richards result probably does not help to designa wave computer which beats the Turing machine. 2000 Mathematical Subject Classification: 03D80, 03F60, 35L05,68Q05.     

Infinite time extensions of Kleene’s $${\mathcal{O}}$$

Using infinite time Turing machines we define two successive extensions of Kleene’s O{\mathcal{O}} and characterize both their height and their complexity. Specifically, we first prove that the one extension—which we will call O⁺{\mathcal{O}^{+}}—has height equal to the supremum of the writable ordinals, and that the other extension—which we will call O⁺⁺{\mathcal{O}}^{++}—has height equal to the supremum of the eventually writable ordinals. Next we prove that O⁺{\mathcal{O}^+} is Turing computably isomorphic to the halting problem of infinite time Turing computability, and that O⁺⁺{\mathcal{O}^{++}} is Turing computably isomorphic to the halting problem of eventual computability.     

Finite Interpolation with Minimum Uniform Norm in

Given a finite sequence a{a₁, …, a_N} in a domain Ω ⁿ, and complex scalars v{v₁, …, v_N}, consider the classical extremal problem of finding the smallest uniform norm of a holomorphic function verifying f(a_j)=v_j for all j. We show that the modulus of the solutions to this problem must approach its least upper bound along a subset of the boundary of the domain large enough so that its A(Ω)-hull contains a subset of the original a large enough to force the same minimum norm. Furthermore, all the solutions must agree on a variety which contains the hull (in an appropriate, weaker, sense) of a measure supported on the maximum modulus set. An example is given to show that the inclusions can be strict.     

Characterization of generalized convex functions by their best approximation in sign-monotone norms

Let {u₀, u₁,… u_{n − 1}} and {u₀, u₁,…, u_n} be Tchebycheff-systems of continuous functions on [a, b] and let f ε C[a, b] be generalized convex with respect to {u₀, u₁,…, u_{n − 1}}. In a series of papers ([1], [2], [3]) D. Amir and Z. Ziegler discuss some properties of elements of best approximation to f from the linear spans of {u₀, u₁,…, u_{n − 1}} and {u₀, u₁,…, u_n} in the L_p-norms, 1 p ∞, and show (under different conditions for different values of p) that these properties, when valid for all subintervals of [a, b], can characterize generalized convex functions. Their methods of proof rely on characterizations of elements of best approximation in the L_p-norms, specific for each value of p. This work extends the above results to approximation in a wider class of norms, called “sign-monotone,” [6], which can be defined by the property: ¦ f(x)¦ ¦ g(x)¦,f(x)g(x) 0, a x b, imply f g . For sign-monotone norms in general, there is neither uniqueness of an element of best approximation, nor theorems characterizing it. Nevertheless, it is possible to derive many common properties of best approximants to generalized convex functions in these norms, by means of the necessary condition proved in [6]. For {u₀, u₁,…, u_n} an Extended-Complete Tchebycheff-system and f ε C⁽ⁿ⁾[a, b] it is shown that the validity of any of these properties on all subintervals of [a, b], implies that f is generalized convex. In the special case of f monotone with respect to a positive function u₀(x), a converse theorem is proved under less restrictive assumptions.     

Extremal problems concerning Kneser graphs

Let and be two intersecting families of k-subsets of an n-element set. It is proven that | | ≤ (_k−1ⁿ⁻¹) + (_k−1ⁿ⁻¹) holds for , and equality holds only if there exist two points a, b such that {a, b} ∩ F ≠ for all F . For an example showing that in this case max | | = (1−o(1))(_kⁿ) is given. This disproves an old conjecture of Erdös [7]. In the second part we deal with several generalizations of Kneser's conjecture.     

Multivariate skewness and kurtosis measures with an application in ICA

In this paper skewness and kurtosis characteristics of a multivariate p-dimensional distribution are introduced. The skewness measure is defined as a p-vector while the kurtosis is characterized by a p×p-matrix. The introduced notions are extensions of the corresponding measures of Mardia [K.V. Mardia, Measures of multivariate skewness and kurtosis with applications, Biometrika 57 (1970) 519–530] and Móri, Rohatgi & Székely [T.F. Móri, V.K. Rohatgi, G.J. Székely, On multivariate skewness and kurtosis, Theory Probab. Appl. 38 (1993) 547–551]. Basic properties of the characteristics are examined and compared with both the above-mentioned results in the literature. Expressions for the measures of skewness and kurtosis are derived for the multivariate Laplace distribution. The kurtosis matrix is used in Independent Component Analysis (ICA) where the solution of an eigenvalue problem of the kurtosis matrix determines the transformation matrix of interest [A. Hyvärinen, J. Karhunen, E. Oja, Independent Component Analysis, Wiley, New York, 2001].