可计算分析是一门新兴的数学和理论计算机学科.它研究实数，实数集和实函数等连续型对象的可计算性和计算复杂性．第二型能行性理论(简称TTE)是研究可计算分析的一种合理模型．Co-regular集是工程数学中常用的一类集合．本文在TTE框架下，研究拓扑空间中Co-regular集的可计算性问题及其可计算算子问题。本摘要分三个部分：首先介绍可计算分析和TTE理论，然后引出研究现状和本文动机，最后是主题内容：叙述本文的主要贡献以及意义.　　 §0.1可计算分析和TTE介绍　　 可计算性图灵机是一个理论计算模型，图灵机将函数严格分为图灵可计算和图灵不可计算两种.一个对象是图灵可计算的，是指有一个能在图灵机上运行的程序．除了图灵机，被公认的其它理论计算模型还有若干个．这几个被认可的计算模型，计算能力是完全一致的．丘奇-图灵论题指出：直观意义上的可计算函数，就是图灵机可计算函数[Odi89],　　 作为现代计算机的理论基础．图灵机是现实可行的，任何图灵可计算函数一定能使用某种计算机语言（比如C语言）编写成可在计算机上运行的程序．　　 可计算分析和数值分析数值分析是研究如何用计算机求解数学问题的一门学科.比如利用计算机求函数的零点、积分，矩阵的特征值，求解微分方程等.数值分析通过设计合理的算法，节省计算机的运算次数和存储空间，来达到减少计算时间，减少误差累积以达到提高计算精确度的目的．但数值分析对计算过程中误差的累积有时无能为力．这个缺陷暴露了目前数字计算机的不足．　　 计算机是以图灵机为原型设计出来的．图灵机的构造决定了现代的计算机不能处理连续性问题.尽管数值分析在过去的几个世纪取得了辉煌的成就，但在连续系统中出现的许多算法问题无法得到令人满意的解决．例如算法几何中关于连续性模型中的讯号或图像的数字处理、连续（或混合）系统中的数字式控制等问题．对于这些数字计算和分析中的问题，在理论上仍是一个缺口．数值分析未来的发展需要建立在一个坚实的可计算理论基础之上，这是可计算分析的任务和意义所在.　　 可计算分析的目标是系统地表述计算规律．它研究的不是一个具体问题的算法，也不是试图设计制作高性能的数字计算机，而是试图解释科学计算的规律.为数值计算、可计算性及计算复杂性建立可靠的数学基础，从而为计算机的软件理论建立可靠且能行的数学准备．填补经典数学与计算机科学之间的鸿沟.　　 可计算分析的发展可计算分析的起源，是七十多年前以A. Turing首次给出可计算实数的精确定义为标志的Tur36]．不久以后，他发现实数的十进制和二进制不足以恰当地定义可计算实函数[Tur37].于是人们开始尝试用各种理论模型研究分析学的可能性．与经典的可计算性理论[Rog67, Soa87, Cut80]不同，这些不同流派关于可计算实函数的定义并不完全等价．S. Banach和S. Mazur所用的序列可计算性定义了实函数的可计算性概念[Maz63].A. Grzegorczyk和D. Lacombe建议用快速收敛的有理数列作为实数的表示，并且定义了可计算实函数的概念。在A. Grzegorczyk和D. Lacombe的工作基础上，M. Pour-EI与J. Richards以公理化的方法定义了Banach空间上的可计算概念[PER89, PE99]. K.Weirauch与C. Kreitz在A. Grzegorczyk和D. Lacombe的工作基础上创立了以表示式理论和第二型图灵机为基础的TTE理论[KW85, Wei00]．葛可一应用NP-完全性理论证明了一些基本数值运算，如求极值，积分等的计算复杂性下界[Ko91, Ko98].自从上个世纪八十年代以来，以A. Edlat为代表的许多学者利用域论研究实函数的可计算性，取得了丰富的成果[WD80, WS81, SHT95, DG96, Eda95, Eda97, ES99,SHT99, Bla99]. Markov的构造主义数学流派则以Markov算法来定义可计算实数和可计算实函数[Kus84, Kus99]. L.Blum, F. Cucker, M. Schub和S. Smale用Real-RAM模型研究实数计算理论[BCSS96, BCSS98]。还有人用直觉主义逻辑来分析分析学中的定理证明及可计算性[NS97, DXWJ07].　　 在这些不同的流派当中，TTE有着独特的优势：　　 简单灵活 TTE理论是经典可计算理论的自然推广.它以第二型图灵机为工具，继承了经典图灵可计算理论的简单和灵活．经典可计算理论研究自然数集以及数论函数的可计算性.也就是说，它只能处理有限长符号串．TTE是为了研究实数，连续函数的可计算性，对经典的图灵可计算理论进行改进，TTE的许多概念都可以在经典可计算理论中的找到原型.　　 现实可行性 TTE是现实中可行的．TTE是TT机来处理无限长符号串，凡是在TT机上可行的算法，都可以在普通的数字计算机上用常用语言通过编写程序来运行.有一个研究方向叫exact arithmetic，其中心思想是把（可计算）实数而不是其有理逼近直接在计算机运算。其中的关键思想之一就是第二型图灵机和表示论原理．　　 包容性除TTE之外，可计算分析的每一种流派都定义了它们独有的表示方法和可计算性，各有其独到之处．但是这些理论存在一个共同的缺陷，对计算对象的表示比较单一，这使得函数的可计算性研究不灵活．TTE则具有很强的包容性，TTE允许对同一个研究对象有不同的命名系统，从而导致不同的可计算性.其它模型定义的可计算性仅仅成了TTE命名系统的某个特殊性．TTE对同一个对象进行多个等价和不等价的命名系统，这使得TTE灵活而强大.不等价的命名系统诱导的可计算性可能是不同的，而等价的命名系统其计算复杂性可能是不同的.　　 TTE理论的两个构成要素：　　 命名系统在TTE中，运算对象总是由有限个字符（比如0和1）表示成有限长符号串或无限长符号串的形式。函数的计算过程就是第二型图灵机机将输入串转化成输出串的过程.用符号串来表示计算对象，这种对应关系被称为命名系统．TTE有两种命名系统，以有限长字符串表示计算对象的叫记号；用以无限长字符串表示计算对象的叫表示式.记号和表示式统称为命名系统。同一个计算对象可以有不同的命名系统.不同的命名系统可以比较强弱关系．比如实数就可以用十进制ρb,10，快速收敛的有理数序列表示式等ρc.　　 第二型图灵机第二型图灵机是经典图灵机改进后的计算模型．它有一条单向的、可以无限长的只读输入带，一条单向不允许擦除的、可以无限长的只写输出带、若干条工作带、若干读写头和控制装置．输出带上的符号串长度可以是无限长的．输出的任意有限长部分，都是通过输入的有限长部分决定的．这一性质使得每一个可计算函数都是连续函数．　　 §0.2本文动机　　 由于可计算分析的研究起源于实数的可计算性研究，所以在可计算分析理论发展的早期，研究成果主要集中在欧氏空间Rn的范围内.例如Rn上的极限、实数、连续、微分、零点、闭集、开集、紧集及加、减、乘、除、交、并、补等．最近人们把可计算性研究延伸到数学的多个分支，代数学[ZB00, ZB04]，泛函分析[ZW03, Wei03, GSW07, WZ07, Bra08]、数值分析[W299, WZ01, WZ02, WZ05]、测度论[Mue99, Wei99, YMT99, HW03, WD05, WD06]和积分变换等方面，取得了丰硕成果．　　 Weirauch、Tanja、徐亚涛等人在前人零散工作的基础上，定义并刻画了可计算度量空间和可计算局部紧豪斯道夫空间[XG07, XG08].对这些空间的闭集和紧集定义了若干表示式并比较了它们之间的强弱关系.随后将这些结论推广到了可计算的T0空间上[XGW08].和任何空间可计算性研究的初期一样，拓扑空间各种函数可计算性研究、重要定理的“可计算版本”还是空白．　　 Co-regular集（也就是满足(?)=P的集合）是工程数学中应用十分广泛的一类集合．Ziegler等对欧氏空间上Regular集的可计算性和可计算算子进行研究[Zie02． Zie04, Zie05]. Co-regular集与Regular集的可计算性结论可以互相利用。本文选题的目的是希望系统地进行Co-regular集的可计算性研究，然后尝试把一些结果推广到度量空间和局部紧豪斯道夫空间上[QZ07, QZ07a, QZ08, QZ08a].　　 §0.3主要结论　　 本文结论主要分四部分：第一部分从不同角度提出了欧氏空间Co-regular集的若干表示式；比较了不同表示式之间的强弱关系；第二部分是Co-regular集上可计算算子的情况；第三部分是运用第一部分结论对可计算分析其它学派可以用来表示Co-regular集的命名系统进行强弱比较．最后一部分是度量空间和拓扑空间上Co-regular集的可计算性．　　 结论的意义:　　 根据TTE理论，一个函数f：(?)X→Z是(α,δ)-可计算的，是指存在一个TT机M，输入x∈X的任意一个α表示式，可以输出f(x)∈Y的一个δ表示式.但是如果一个函数是(α，δ)-不可计算的，使f变成可计算函数的方法有两个：一种方法是输入比α更强的表示式；另一种办法就是输出比δ表示式弱的表示式.比如：映射RE：A→A°是((?),θ＜)-不可计算的，而对于任何闭集来讲，A°是Co-regular集，用比θ＜更弱的θ(?)表示式来替换，得到映射RE:A→A°是(?)-可计算的．Co-regular集定义的不同的命名系统，使得函数能行性的讨论变得更加灵活，层次更分明，　　 第二部分是对P上常见算子的可计算性研究，包括常见的算子交、并、内部运算以及可计算的连续开函数的情况．这些结论可以产生一些连续开函数经典定理的可计算版本．它表明了可以用通用的数字计算机来证明抽象的数学定理．即在一定程度上实现定理证明的自动化．　　 第三部分充分体现了TTE理论具有很好的包容性．对可计算分析其它学派用来刻画Co-regular集的表示式，只是我们定义的十种表示式的一个组合特例，我们还对这些学派所提出表示式的强弱还进行了排序，这些不同背景的表示式之间的是否等价、孰强孰弱或者彼此不可以互相转化，都是十分明确的[QZ08a].　　 在欧氏空间Rn上，关于闭集的表示就有很多种，但是它们大多是彼此等价的．但是这些表示式在度量空间上，并不完全等价（比如(?)）．这就使得拓扑空间上Co-regular集的可计算研究，绝不只是Rn的可计算性平移．　　 研究表明，(?)仅仅在完备空间上成立，这使得度量空间和欧氏空间上关于闭集的命名系统转化关系存在较大差异.度量空间和局部紧豪斯道夫空间上Co-regular集的可计算性研究可以夯实函数连续性及可计算性研究的基础.