图灵机计算实数函数的稳定性(英文)

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

康托尔实数的局限性

康托尔为我们建立了集合论,并且证明了实数的不可数性,但是其中留下了很多疑点.1.一个实数能在每一个集合论模型中出现的充分必要条件是它是可以被集合论来定义的.那些在集合论模型中不出现的实数.我们可以把他们叫做看不见的实数.2.在实数的十进位无穷小数表示法中有些是我们能确切地知道它的第几位是什么,但是对另外的一些实数我们对它们就只能有模糊的认识,也就是说它的第几位是什么我们不可能全部知道.我们可以把他们叫做写不出的实数.3.由于Cantor关于实数是不可致的证明不是构造性的证明.而是用所谓的归谬证法.它们中有很多是看不见写不出的实数.因此说它们是虚拟的实数.4.虚拟实数就像银行中的虚拟货币.你可用它来买东西,它可从—个户头转拨到另—个户头,但是钱的实体是不存在的,这个现象也让我们对某些数学工具的合法性提出质疑.我们用对角线法来证明实数的基数比自然数的基数大,但是我们并没有真正有效的地构造出那么多的实数.因此我们没有办法来确切地定义它们.也可以说它们中的绝大多数是不可以定义的.在一般的情况下虚拟实数是不可以个别地使用的.

非良基集合论模型悖论

给出一个新的集合论悖论.用模型论方法证明了非良基性的集合论模型的存在性.这个模型中存在对∈关系下降的无限元素外序列.还证明可以存在集合论模型,其中ω,ω1等集合,ON和N等类的内部都存在对∈关系无限递降的元素外序列.这种对∈关系是无限递降的外序列还可以插入于一个没有可数共尾的对∈是上升的序列的后面,插入后成为同名集合的一部分.用这种模型第一次定义并给出了外集合不是内集合的例子.

无原子布氏代数理论的计算复杂性

研究无原子布氏代数的计算复杂性 .得到了下面的新定理 :定理 1 无原子布氏代数理论Δ具有完全的量词消去法 ,也就是说每一个式子都Δ等价于一个开式子 .定理 2 无原子布氏代数的初等型Γ (x1,… ,xn)是由型内的不含量词的全体开式子所唯一决定 .定理 3 无原子布氏代数的一个长度为 n的语句的判断过程所消耗的 Turing时间和空间都是属于 2 2 cn指数级 .

群的部分初等等价性(Ⅰ)

两个群当适合形式语言■={·,1}中完全相同的形状为(■x_1…x_n)Ψ(x_1…x_n)(ψ中无量词)的语句时,称为■_n-等价的。其他“部分初等等价性”可仿此定义。本文给出了两个群为■_n-等价的代数条件。讨论了一些常见的由二元生成的群,证明它们每一个都只与自身为■_2-等价,(其中包括dihedral群,dicyclic群,quaternion群等)。

模型的并、积与齐次模型

这是我们研究齐次模型的第二篇文章。在第一篇文章里我们证明了:(1)

多个一元关系上的VAUGHT猜想

我们对多个一元关系理论系统证明了Ｖａｎｇｈｔ猜想并对其作了一个完整的类．

计算机科学发展漫谈

计算机科学发展漫谈罗里波（北京师范大学数学系１００８７５）１ 历史的回顾．（手摇计算机和山本五十六事件的关系引起）很多计算机科学家把计算机的历史追朔到古希腊的亚里士多德，但我并不认为是这样的．直到１９４０年人们还只有极其简单的手摇计算机，这种计算机算...

完全二叉树的量词消去

量词消去法已经成为计算机科学和代数模型论中最有力的研究工具之一.本 文针对完全二叉树理论所独有的特性,给出了它的基本公式集,然后利用分布公式及 有限覆盖证明了完全二叉树的理论可以量词消去.

完全二叉树理论的计算复杂度

完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).

中国剩余定理在非标准数论中的推广

我们推广了中国剩余定理,用于研究数论模型,并在非标准数论模型中对比分析若干数论定理.

A CLASS OF EQUATIONS IN FREE GROUPS

We are discussing a class of equations with two unknowns in a free group, of which a particular instance has been studied by by K. I. Appel (ef. Proc. Amer. Math. Soc., 19 (1969), 179—181). And we have to discuss as well two related classes of equations with one unknown. The equations