关于Diophantine方程a~x+b~y=z~2

设a=2~r,b=p~s,其中p是给定的奇素数,r和s是给定的正整数.运用有关三项Diophantine方程和广义Ramanujan-Nagell方程的结果,将方程a~x+~y=z~2的所有正整数解(x,y,z)进行了分类,从而得出了这些解的可有效计算的上界.     

Isomorphisms,definable relations,and Scott families of class 2 nilpotent groups

The paper deals in questions on the complexity of isomorphisms and relations on universes of structures, on the number and properties of numberings in various hierarchies of sets, and on the existence of connections between semantic and syntactic properties of the structures and relations for the class of nilpotent groups of class two. Supported by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-4413.2006.1. __________ Translated from Algebra i Logika, Vol. 46, No. 4, pp. 514–524, July–August, 2007.     

Spectra of degrees of some structures

We argue for the existence of structures with the spectrum {x : x ≰ a} of degrees, where a is an arbitrary low degree. Also it is stated that there exist structures with the spectrum of degrees, {x : x ≰ a} ⋃ {x : x ≰ b}, for any low degrees a and b. Supported by RFBR grant No. 05-01-00605. __________ Translated from Algebra i Logika, Vol. 46, No. 6, pp. 729–744, November–December, 2007.     

Σ-Definability of countable structures over real numbers, complex numbers, and quaternions

We study Σ-definability of countable models over hereditarily finite {ie193-01} superstructures over the field ℝ of reals, the field ℂ of complex numbers, and over the skew field ℍ of quaternions. In particular, it is shown that each at most countable structure of a finite signature, which is Σ-definable over {ie193-02} with at most countable equivalence classes and without parameters, has a computable isomorphic copy. Moreover, if we lift the requirement on the cardinalities of the classes in a definition then such a model can have an arbitrary hyperarithmetical complexity, but it will be hyperarithmetical in any case. Also it is proved that any countable structure Σ-definable over {ie193-03}, possibly with parameters, has a computable isomorphic copy and that being Σ-definable over {ie193-04} is equivalent to being Σ-definable over {ie193-05}. Supported by RFBR-DFG, grant No. 06-01-04002 DFGa. __________ Translated from Algebra i Logika, Vol. 47, No. 3, pp. 335–363, May–June, 2008.     

h‐monotonically computable real numbers

Let h : ? → ? be a computable function. A real number x is called h‐monotonically computable (h‐mc, for short) if there is a computable sequence (x_s) of rational numbers which converges to x h‐monotonically in the sense that h(n)|x – x_n| ≥ |x – x_m| for all n andm > n. In this paper we investigate classes h‐ MC of h‐mc real numbers for different computable functions h. Especially, for computable functions h : ? → (0, 1)_?, we show that the class h‐ MC coincides with the classes of computable and semi‐computable real numbers if and only if Σ_i∈?(1 – h(i)) = ∞and the sum Σ_i∈?(1 – h(i)) is a computable real number, respectively. On the other hand, if h(n) ≥ 1 and h converges to 1, then h‐ MC = SC (the class of semi‐computable reals) no matter how fast h converges to 1. Furthermore, for any constant c > 1, if h is increasing and converges to c, then h‐ MC = c‐ MC . Finally, if h is monotone and unbounded, then h‐ MC contains all ω‐mc real numbers which are g‐mc for some computable function g. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Isomorphism of the Index Sets of Discrete Families of General Recursive Functions

We establish isomorphism between the index set of an arbitrary computable family of general recursive functions and the index set of a certain computable discrete family of general recursive functions.     

Using Dynamic Geometry Software to Simulate Physical Motion

In this paper we analyse to what extent the computational model of the geometry implemented in a dynamic geometry environment provides models for physical motion, focusing on the continuity issues related to motion. In particular, we go over the utility of dynamic geometry environments to simulate the motion of mechanical linkages, as this activity allows us to compare, by means of dynamic drawings, the computable representation of geometric properties with the real motion of a mechanism. Analysing a simple example, we provide theoretical foundations for particular behaviours observed in the motion of a picture on the screen, which require a subtle interpretation to be understood in a purely physical context. In this way, we reflect on some requirements imposed by the computable representation of knowledge. We consider this work to be a necessary step to determine didactic consequences related to students' perceptions of the moving displays; in particular those concerning the uses of the dragging mode as a tool not only for automatic drawing of many instances of a construction,but also to produce continuous motion. This revised version was published online in July 2006 with corrections to the Cover Date.     

欧氏空间上Co-regular集的表示式

For the computability of co-regular subsets in metric spaces, the properties of the co-regular subsets and several reasonable representations on co-regular sets have been suggested in this paper. As last, the 'weaker or stronger' relations of these representations have been revealed.     

Some remarks on completion of numberings

We present some examples and constructions in the theory of complete numberings and completions of numberings that partially answer a few questions of [1].     

Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.