可计算分析是一门新兴的理论计算机学科,它研究连续型计算的客观规律,如实数、实数集和实函数的可计算性。第二型能行性理论是研究可计算分析的一种合理模型。本文在第二型能行性理论的框架下研究一般拓扑空间上的可计算性问题。可计算分析中的流派。经典数学,一旦遇上计算机,便会焕发出强大的生机。可计算分析正是这样一门青春的、充满活力的交叉学科。它短短七十年的发展史,就是各种流派争奇斗艳的历史。A.Turing在[Tur36]中首次给出了可计算实数的精确定义,随后他注意到,实数的二进制和十进制表示不足以恰当地定义可计算实函数[Tur37]。于是人们开始尝试,用各种理论模型和方法来研究分析学的能行性。与经典可计算性理论[Rog67,Soa87,Cut80]不同,这里众多流派关于可计算实函数的定义并不完全等价。S.Banach和S.Mazur用所谓的序列可计算性定义了实函数的可计算性概念[Maz63]。A.Grzegorczyk[Grz55]和D.Lacombe[Lac55a]建议用快速收敛的有理数列作为实数的“名字”,并且定义一个实函数f是可计算的,如果有一台机器(图灵机或数字计算机)可以从每个实数x的每一个名字出发,计算出它的像f(x)的名字。在A.Grzegorczyk和D.Lacombe的工作基础上,M.Pour-El与J.Richards以公理化方法定义了Banach空间上的可计算性概念[PER89,PE99]。K.Weirauch与C.Kreitz在A.Grzegorczyk和D.Lacombe的工作基础上创立了以表示理论和第二型图灵机为基础的第二型能行性理论(简称TTE)[KW85,Wei00]。葛可一(Ko,Ker-I)应用NP-完全性理论证明了一些基本数值运算(如求极大值、积分)的计算复杂性的下界[Ko91,Ko98]。自上个世纪八九十年代以来,以A.Edlat为代表的许多学者利用域理论(domain theory)研究实函数的可计算性[WD80,WS81,SHT95,DG96,Eda95a,Eda96,Eda97,Esc97,ES99,SHT99,Bla99]。俄罗斯Markov的构造性数学流派则以Markov算法来定义可计算实数和实函数[Ku(s)84,Ku(s)99]。美国的L.Blum,F.Cucker,M.Schub和S.Smale用real-RAM模型研究实数计算理论[BCSS96,BCSS98]。此外,与可计算分析紧密相关的还有Brouwer的直觉主义分析[Bro75,Bro75a]和Bishop-Bridge的构造性分析[BB85],他们借助比经典逻辑更弱的逻辑基础(如直觉主义逻辑[NS97,DXWJ07])来研究分析学中的定理证明及其能行性。　　 由于可计算分析发端于可计算实数(实函数)的研究,所以该领域的工作自然地集中在了欧氏空间范围内,一个典型的例子就是,V.Brattka和K.Weihrauch考察了欧氏空间中闭集和紧集上的可计算性[BW99]。近几年来相关研究的范围有所扩大,比如V.Brattka和G.Presser把关于欧氏空间的研究推广到度量空间[BP03]。总的来说,人们从能行化的观点出发,考察经典分析学[Wei01,WW06,LW07]、代数学[ZB00,ZB04]、泛函分析[ZW03,Wei03,GSW07,WZ07,Bra08]、数值分析[WZ99,WZ01,WZ01a,WZ02,WZ05]以及测度论[Mue99,Wei99,HW03,WD05,WD06]等数学分支,取得了丰硕成果。遗憾的是,对于在数学中同样占有重要地位,并且与现实生活联系更加紧密的拓扑学,能行化工作并未充分展开。我们已知的研究成果有:M.Schr(o)der研究了正则空间的能行度量化问题[sch98];K.Weihrauch定义了可计算T0空间[Wei00],之后他又和T.Grubba在能行化Dini定理时修订了这一定义,引入了“可计算交”的概念[GW05];N.Zhong和K.Weihrauch在研究扩张函数的能行理论时考察了不可度量空间上的可计算性[ZW03];P.Collins在研究可达集(reachable sets)的可计算性时提出了可计算Hausdorff空间的概念[Co105]。此外值得一提的是,V.Brattka独辟蹊径,概述并揭示了表示与拓扑结构之间的本质关系[Bra03a]。我们注意到,以上涉及拓扑尤其是拓扑空间的研究是零散的,随意的,用到什么定义什么,没有系统地考察过某一类特定拓扑空间上的可计算性。针对某一类特定空间的研究,从欧氏空间开始[BW99],到度量空间[BP03],再到伪度量空间[Bra03b],然后就止步了。为什么不继续一般拓扑空间的研究呢?也许下面的分析能够部分地解释这一困难:在能行理论中,集合的递归性质通常由相应的特征函数(距离或度量函数)来刻画,人们不自觉地使用着“度量”,一旦失去这个工具(从度量空间到一般拓扑空间),就像踩踏在棉花堆上,变得无所适从了。有困难,也就有努力的方向。我们希望填补这一空白,给拓扑学的能行化奠定一个坚实基础。本文旨在系统地研究特定拓扑空间上的可计算性。研究结果分为两大块(五个部分):理论和应用。理论部分系统地研究了三类特定拓扑空间上的表示,在此基础上,我们证明了两个经典数学定理的可计算版本。具体贡献如下：　　 ⑴局部紧Hausdorff空间上的可计算性。定义并刻画了可计算局部紧Hausdoff空间。对于该类空间中的闭集,我们从不同的角度出发,给出了七种表示。更进一步,我们讨论了这些表示之间的关系:Ψfibe≡Ψdom≡Ψsie≡Ψun≡Ψ＞,Ψrange≤Ψ＜。对于该类空间中的紧集,我们利用“收敛网”这个拓扑工具,定义了一种全新表示κnet,并证明:κnet≡κun≡κc。　　 ⑵T0空间上的可计算性。Weihrauch定义了可计算T0空间[Wei00],之后又通过引入“可计算交”修订了这一定义[GW05]。本文的工作是从后者出发的。可计算局部紧Hausdorff空间上关于闭集的表示,大部分都能推广到T0空间上:比如Ψun,Ψ＜,Ψ＞,Ψdom,Ψfibe和Ψsie。特别需要注意的是,这种推广并非理所当然。某些推广后的表示不再保持好的性质(比如稳定性和合理性)。我们构造了一个简洁有力的反例,指出Ψ＞在可计算T0空间上不是合理(well-defined)的。上述各种表示之间的关系如下:Ψsie≡Ψdom≡Ψun,Ψfibe≤Ψdom,Ψrange≤Ψ＜.后两条结果的逆向归约并不成立,我们同样给出了反例。对于紧集,我们重点讨论了两种覆盖表示:κmcκc,并证明了:κmc≤κc。　　 ⑶连续函数空间上的可计算性。令Fωω表示某些部分连续函数组成的集合,这些部分连续函数的定义域都能表示成开集的可数交。ηωω是Fωω的一种标准表示[Wei00]。这种表示的缺点是过于抽象,不利于应用到定理证明当中。我们给出三种与之等价的表示(ηωω≡(η)≡(η)≡(η)),重新刻画Fωω。令C(X,Y)和Cp(X,Y)分别表示从X到Y所有全连续函数和所有部分连续函数组成的集合。对于X,Y都是可计算T0空间的Cp(X,Y),我们用三种办法来刻画它:开开多值表示(open-open multi-representation)δoo,基于实现的多值表示(multi-representation via realization)δ→,基于点列连续性的多值表示(multi-representation via pointwise continuity)(δ)→。更进一步,我们证明了:(δ)→≡δoo,δ→≡δoo。若X是可计算局部紧Hausdorff空间,Y是可计算T0空间,除了以上三种办法,我们还可以通过紧开拓扑(compact-open topology)来表示C(X,Y),记作δco。本章最后,我们证明δco≡δoo≡δ→.　　 ⑷可计算的不变度量问题。给定一个线性度量空间X(度量记为d),存在一个不变度量d1,使得d1≡d。从可计算分析的观点出发,问这样一个问题是合乎情理的,即:给定一个可计算的度量d,是否总能找到一个可计算的与之等价的不变度量d1?在TTE的框架下我们论证了一个半可计算的结果,即:对于可计算的d,能够找到一个半可计算的d1满足指定条件。　　 ⑸可计算的Stone-Weierstrass定理。证明了紧Hausdorff空间下Stone-Weierstrass定理的一个可计算版本。经典的Stone-Weierstrass定理说,对紧Hausdorff空间X,如果A是由X上的连续实值函数构成的一个代数,且A能够分离X中的点,则A在空间C(X)中稠密。这里C(X)是X上所有连续实值函数构成的空间,度量d(f,g)=maxx∈x|f(x)-g(x)|。对于该定理的可计算版本,我们考察函数空间C(K),这里紧集K(C)X可计算。令Dk为C(K)中的一个稠密集,我们能够找到Dk的一种表示vk,使得Mk:=(C(K),dk,DK,vk)是(半)可计算度量空间。(最终结果可计算还是半可计算,与紧集K的可计算性强弱有关。若K是κc-可计算,则Mk半可计算:若K是κmc-可计算,则MK可计算。)