On Computability Theoretic Properties of Structures and Their Cartesian Products

In this paper we show that for any set X ⊆ ω there exists a structure 𝒜 that has no presentation computable in X such that 𝒜² has a computable presentation. We also show that there exists a structure 𝒜 with infinitely many computable isomorphism types such that 𝒜² has exactly one computable isomorphism type.     

The Arithmetical Hierarchy of Real Numbers

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left (right) computable iff it is the supremum (infimum) of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable (multiple) sequences of rational numbers we introduce a non‐collapsing hierarchy {Σ_n, Π_n, Δ_n : n ∈ ℕ} of real numbers. We characterize the classes Σ₂, Π₂ and Δ₂ in various ways and give several interesting examples.     

A sequentially computable function that is not effectively continuous at any point

P. Hertling [Lecture Notes in Computer Science, vol. 2380, Springer, Berlin, 2002, pp. 962–972; Ann. Pure Appl. Logic 132 (2005) 227–246] showed that there exists a sequentially computable function mapping all computable real numbers to computable real numbers that is not effectively continuous. Here, that result is strengthened: a sequentially computable function on the computable real numbers is constructed that is not effectively continuous at any point.     

Morse Theory And Invariant Concepts of Convexity

In optimization, the literature on invariant definitions of convexity has largely centered on the notion of invexity. However, the connection with Morse theory and related geometric trends has not been recognized and results do not appear to be as impressive as those in topology. Our purpose is to improve the situation in optimization, and to clarify the relationship between these two trends. The main result is that the problem can be reduced to the case of functions of one variable.     

图灵机计算实数函数的稳定性

定义在全体实数上的可计算函数是一个很重要的概念．在这以前定义可计算的实数函数有两个途径．第一个途径是首先要定义可计算实数的指标．想要确定实数函数y=f（x）是不是可以计算就要看是否存在一个自然数的（部分）递归函数将可计算实数x的指标对应到可计算实数y的指标．这样一来对实数函数的研究依赖于对自然数函数的研究．第二个定义可计算的实数函数的途径是以逼近为基础的．一个实数函数是可以计算的如果它既是序列可计算的同时也是一致连续的．用这个途径来定义可计算实数函数使用的条件过强以至于很多有用的实数函数成为不可计算的实数函数．例如“〈”和“=”的命题函数就是不可以计算的因为它们是不连续的命题函数．本文讨论了图灵机的稳定性并且给出了一个基于稳定图灵机的可计算实数函数的定义．我们的定义不需要用到自然数的（部分）递归函数．根据我们的定义很多常用实数函数特别是一些不连续的常用实数函数都是可以计算的．用我们的定义来讨论可计算实数函数的性质比原来的定义要方便得多．     

On the convexity for the expected total cost per unit time of the EPQ model with scrap,rework and stochastic machine breakdown

This study explores the economic production quantity model with scrap, rework and stochastic machine breakdown. The main purpose of this paper is twofold:(P1) This paper will adopt the rigorous methods of mathematics to demonstrate that the expected total cost per unit time is convex on all positive numbers to improve the conditional convexity in Theorem 1 of Chiu et al. (2010) [7].(P2) This paper gives the concrete proof to provide bounds for the optimal production run time to remove the logical shortcomings of mathematics presented in proof of Theorem 2 of Chiu et al. (2010) [7].     

确界原理的一个修正证明

分析了华东师大版《数学分析》（第四版）教材中关于确界原理证明的不足之处,给出更为细致的修正证明.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Convexity properties of gradient maps

We consider the action of a real reductive group G on a Kähler manifold Z which is the restriction of a holomorphic action of a complex reductive group H. We assume that the action of a maximal compact subgroup U of H is Hamiltonian and that G is compatible with a Cartan decomposition of H. We have an associated gradient map μp:Z→p where g=k⊕p is the Cartan decomposition of g. For a G-stable subset Y of Z we consider convexity properties of the intersection of μp(Y) with a closed Weyl chamber in a maximal abelian subspace a of p. Our main result is a Convexity Theorem for real semi-algebraic subsets Y of Z=P(V) where V is a unitary representation of U.     

Convex games with an infinite number of players and sequencing situations

In this paper we study convex games with an infinite countable set of agents and provide characterizations of this class of games. To do so, and in order to overcome some shortcomings related to the difficulty of dealing with infinite orderings, we need to use a continuity property. Infinite sequencing situations where the number of jobs is infinite countable can be related to convex cooperative TU games. It is shown that some allocations turn out to be extreme points of the core of an infinite sequencing game.     

Unexpected distribution phenomenon resulting from Cantor series expansions

We explore in depth the number theoretic and statistical properties of certain sets of numbers arising from their Cantor series expansions. As a direct consequence of our main theorem we deduce numerous new results as well as strengthen the known ones.     

Towards computability of elliptic boundary value problems in variational formulation

We present computable versions of the Fréchet–Riesz Representation Theorem and the Lax–Milgram Theorem. The classical versions of these theorems play important roles in various problems of mathematical analysis, including boundary value problems of elliptic equations. We demonstrate how their computable versions yield computable solutions of the Neumann and Dirichlet boundary value problems for a simple non-symmetric elliptic differential equation in the one-dimensional case. For the discussion of these elementary boundary value problems, we also provide a computable version of the Theorem of Schauder, which shows that the adjoint of a computably compact operator on Hilbert spaces is computably compact again.     

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.     

Corank 1 Singularities of Stable Smooth Maps and Special Tangent Hyperplanes to a Space Curve

Let γ be a smooth generic curve in ?P ₃. Denote by C the number of its flattening points, and by T the number of planes tangent to γ at three distinct points. Consider the osculating planes to γ at the flattening points. Let N denote the total number of points where γ intersects these osculating plane transversally. Then T ≡ [N + θ(γ)C]/2 (mod 2), where θ(γ) is the number of noncontractible components of γ. This congruence generalizes the well-known Freedman theorem, which states that if a smooth connected closed generic curve in ?³ has no flattening points, then the number of its triple tangent planes is even. We also give multidimensional analogs of this formula and show that these results follow from certain general facts about the topology of codimension 1 singularities of stable maps between manifolds having the same dimension.     

Approaches to Effective Semi-Continuity of Real Functions

For semi-continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi-computable of type one, if its open hypograph hypo(f) is recursively enumerably open in dom(f) × ?; we call f lower semi-computable of type two, if its closed epigraph Epi(f) is recursively enumerably closed in dom(f) × ?; we call f lower semi-computable of type three, if Epi(f) is recursively closed in dom(f) × ?. We show that type one and type two semi-computability are independent and that type three semi-computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi-computable real function on a computable interval is not necessarily computable.     

Copositive optimization - Recent developments and applications

Due to its versatility, copositive optimization receives increasing interest in the Operational Research community, and is a rapidly expanding and fertile field of research. It is a special case of conic optimization, which consists of minimizing a linear function over a cone subject to linear constraints. The diversity of copositive formulations in different domains of optimization is impressive, since problem classes both in the continuous and discrete world, as well as both deterministic and stochastic models are covered. Copositivity appears in local and global optimality conditions for quadratic optimization, but can also yield tighter bounds for NP-hard combinatorial optimization problems. Here some of the recent success stories are told, along with principles, algorithms and applications.