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

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