本文从可计算分析的观点研究测度论中函数的可计算性问题。 作为一门新兴的理论计算机学科，可计算分析研究连续型计算的客观规律，如实数、实数集、实函数的可计算性，等等。在［Tur86］中，A. Turing给出了可计算实数概念的精确定义。在［Tur37］中，他还注意到了实数的二进制和十进制表示不足以定义恰当的可计算实函数的概念。此后，人们尝试用不同的理论模型和方法研究分析学的能行性。与发生在经典可计算性理论那里的情形不同的是，在这些众多的理论流派中，它们关于可计算实函数的定义并不完全等价。Banach和s. Mazur用所谓的序列可计算性定义了实函数的可计算性概念［Maz63］。A. Grzegorczyk［Grz55］和D. Lacombe［Lac55a］建议用快速收敛的有理数列作为实数的“名字”，并且定义：一个实函数f是可计算的是指有某个机器（数字计算机，图灵机）可以从每个实数x的每一个名字计算出它的像f（x）的名字。在A. Grzegorczyk和D. Lacombe的工作基础上，M. Pour-El与J. Richards以公理化方法定义了Banach空间上的可计算性概念［PER，89，PE99］。K. Weirauch与C. Kreitz在A. Grzegorczyk和D. Lacombe的工作基础上创立了以表示理论和第二型图灵机为基础的第二型能行性理论（简称-TTE）［KW85，Weioo］。葛可一（Ko，Ker-I）应用NP-完全性理论证明了一些基本的数值运算（如求极大值、积分）的计算复杂性的下界［Ko91，Ko98］。自上个世纪的八、九十年代以来，以A. Edlat为代表的许多学者应用域理论（domain theory）研究实函数的可计算性［WD80，WS81，SHT95，DG96，Eda95a，Eda96，Eda97，Esc97，ES99b，SHT99，Bla99］。俄罗斯Markov的构造性数学流派则以Markov算法来定义可计算实数和实函数［Kus84，Kus99］。美国的L. Blum，F. Cucker，M. Schub和S. Smale以real-RAM模型研究实数计算理论［BCSS96，BCSS98］。此外，与可计算分析紧密相关的有Brouwer的直觉主义分析［Bro75，Bro75a］，和Bishop-Bridge的构造性分析［BB85］，他们借助于比经典逻辑更弱的逻辑基础（如直觉主义逻辑）来研究分析学中的定理证明及其能行性。 数值分析研究函数的计算方法，如求零点的牛顿方法和解线性方程组的高斯消去法，但它不是一门研究可计算性规律的学科。它所面向的是人的思维而不是机器的“思维”。它如牛顿当初所作的那样，将实数都视为一个个独立的个体，就像自然数那样天然存在、不言自明［BCSS98］。然而数字计算机在本质上是离散的。事实上，实数在计算机中通常是以浮点数的形式近似表示的。这导致根据数值计算方法设计的科学计算软件具有不稳定性；在有些情形下所给出的计算结果远远偏离正确结果。例如［Sch03］，应用高斯消去法求解线性方程组？用双精度的浮点数的计算结果是？而正确的结果分别是上述计算结果的两倍，即X=224294254，Y=-134217729这样的误差很难控制并导致计算结果不可靠［DR75］。因此，尽管数值分析在过去几个世纪里曾取得了巨大的成就，它的未来发展需要建立在一个坚实的可计算性理论基础之上。 在众多的研究可计算分析的理论模型当中，我们发现TTE理论是研究可计算分析的较为合理的一种。与其他理论模型相比，它具有三个突出的优点：（一）它是经典可计算性理论的自然推广。经典理论研究自然数，自然数集以及数论函数的可计算性，实质上就是研究图灵机对于有限长的符号串的处理、计算的能力。第二型理论，为处理连续型计算，将经典理论的概念和结果推广到研究图灵机对无限长的符号串的处理、计算的能力。（二）它是现实可行的。它以一类特殊的图灵机来定义可计算性概念。因而其算法是现实可行的，即可以用通常的计算机语言设计程序，在数字计算机E执行。（三）它具有理论包容性。它所定义的可计算性总是相对于计算对象的具体表示而言的。不同的表示导致不同的可计算性，这是TTE理论的一个重要的发现和关键思想。其他学派关于可计算性的定义，则没有体现这一观点。例如，它们关于实数的可计算性往往只有一种，而在TTE那里允许多种不同的定义［ZW99］。其他学派关于可计算性的定义也往往或者是等价于TTE理论中所定义的某个特殊的可计算性概念，或者可以用TTE的方法加以重新定义的。 TTE理论可以称之为基于表示的可计算性理论。在图灵机或者计算机中，运算对象，如实数，总是表示成0-1串的形式。函数的计算过程就是机器将输入串转换成输出串的过程。这种用符号串来表示计算对象所形成的对应关系称为命名系统（naming system）。在TTE理论中，有两类命名系统：以有限长的符号串表示计算对象的称为标记（notation）；以无限长的符号串表示计算对象的称为表示（representation）。同一个计算对象集可以有不同的命名系统。例如，实数的表示有十进制和二进制，等等。TTE以一类特殊的图灵机，第二型图灵机（简称TT-机），作为其计算模型。第二型图灵机有一个单向的只读输入带，一个单向的只写输出带（不允许擦除，一个可以更改的输出是没有什么意义的）和若干工作带。这意味着第二型图灵机的输出的任何有限长部分，总是由输入的某个有限长部分所决定的。这一性质称为第二型图灵机的有限性，它将函数的连续性与可计算性自然地联系在一起。可计算性概念由具体的命名系统和第二型图灵机来定义。例如，称一个实数是二进制可计算的如果有一个TT-机可以自动生成该数的二进制形式。又如，称一个函数，是（二进制，二进制）－可计算的，是指有一个TT－机，对于输入f的定义域中任何一个数x的二进制表示，输出像发f（x）的二进制表示。不同的命名系统往往诱导出不同的可计算性。例如，函数，f（x）=3x对于二进制或十进制都是不可计算的，但对于实数的标号数字表示（或标号二进制）（signed-digit representation）则是可计算的［Wei00，Avi61］。 尽管可计算分析，包括TTE理论，在近些年来取得了长足进步并初具规模，它仍然处于发展的初级阶段。有许多基础性的问题尚未解决，分析学中还没有一个分支的可计算性问题得到彻底的研究。这一状况对于测度论尤其如此。作为现代分析学的一个重要分支，测度论肇始于勒贝格（Lebesgue）。他在1902年将长度和面积的概念推广为一般的Borel集上的勒贝格测度，将黎曼积分推广为勒贝格积分。在二十世纪三十年代，测度论已趋成熟，并在概率论、泛函分析和调和分析中得到广泛的应用。五十年代以后发展起来的无穷维空间中的测度和泛函积分成为研究量子物理的重要工具［Yan04］1．在计算机科学中，许多领域都与测度论紧密相关，如数值积分，概率的计算和推理，应用随机过程，等等［Jay03，Che99］1．正如在数值分析那里一样，这些学科普遍缺乏关于其可计算性研究的理论基础。可计算测度论的研究无疑将有助于改变这种尴尬局面，并推动经典数学在计算机科学中的应用［Cheng］。 本文旨在为可计算测度论的发展做一些基础性的工作，例如，如何表示可测集、可测函数？在可测集、可测函数上的基本运算（如，集合运算、四则运算）的可计算性如何？这些问题，除［WDW04，WD04，WW04］之外，目前尚无人涉足。我们的研究结果分为五个部分。 第一部分 定义了可计算测度空间的概念（定义3．3．1。具体而言，可计算测度空间就是一个五元组（Ω，A，μ，R，α），其中Ω是一个非空集，A是由Ω的子集构成的σ-代数，其中的元素称为可测集，μ是定义在A上的测度，它们构成一个可测空间（Ω, A. μ）．可计算性条件体现在R与α上。R是由可列多个有限可测的集合构成的环，使得A是由R生成的σ-代数。而α是R的一个标记。 第二部分 我们研究可计算无穷测度空间（Ω, A, μ, R, α）中可测集的表示和基于这些表示的司计算性。 首先，我们论证了关于可测集的一些不可判定性问题，如可测集的几乎处处相等关系是不可判定的，可测集的几乎处处真包含关系也是不可判定的，两个无穷可测集的交是否还是无穷可测的是不可判定的，两个无穷可测集的差是否还是无穷可测的是不可判定的。 其次，我们通过不同的方式给出了可测集的几种表示，定义可测集的表示的困难在于无穷可测集的表示，即如何用可计算测度空间定义中的基本集来逼近无穷可测集．我们要在可测集上定义一个合适的收敛性． 第三部分 我们研究可计算无穷测度空间（Ω，A，μ，R，α）中可测数值函数的一些基本运算如四则运算的可计算性。这里数值函数的值可以是正负无穷大。 第四部分 我们论证了在可测集的表示和可测数值函数的表示之间存在着一种共轭关系（定义6．0．15）。 第五部分 我们证明了一个可计算的Daniell-Stone定理（定理8.1.5）。经典的Daniell-Stone定理表明从一个抽象的Daniell积分可以得到一个测度使得该测度所定义的积分等同于那个抽象的Daniell积分。