用ω-Turing机计算实数函数
罗里波
（石家庄经济学院信息工程学院, 050031；
北京师范大学数学科学学院, 100875）
摘要：实数的可计算函数是一个非常重要的概念，定义可计算实数函数有两个途径，第一个途径是先定义可计算实数的指标。一个可计算实数的指标是一个计算该实数的Turing 机的Gödel数。一个定义在全体可计算实数上的函数y=f(x)是可计算的，当且仅当存在一个在全体可计算实数的指标上的(部分)递归函数将x的指标对应到y的指标，这样对实数函数的研究依赖于自然函数的性质。第二个定义可计算实数的途径是基于逼近。一个实数函数是可计算的，当且仅当它既是序列可计算的也是有效地一致连续的，这个条件太强使得很多非常有用的实数函数不能成为可计算函数。根据这个定义“<” 和 “=”都是不可计算的，因为它们的特征函数是不连续的。
在这篇文章里我们讨论ω-Turing机的稳定性并且定义了在一个有限字母表的全体无限序列上的ω-可计算函数，我们也证明了ω-可计算函数的复合函数也是ω-可计算的。我们的定义没有用到Gödel 数或者递归函数。根据我们的定义很多常用函数特别是一些有用的不连续函数是ω-可计算函数。一个函数是否ω-可计算的验证较为容易，根据我们的定义普通Turing机的停机命题是ω-可计算的。
关键词：ω-Turing机的稳定性；ω-可计算函数
中图分类号：O174 文献标识码：A
责编：前沿科学
