（逻辑学专业论文）Coregular集可计算性研究.pdf

论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：研饥羡 日期：2 。d 孑年仁月5 一日 1 ， 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 保密的学位论文在解密后使用本规定。 学位论文作者签名：柙砒文导师签名： 蟛k 1 日期：2 口。踔l2 ，月厂日 日期：功”g 年幢月歹日 ifif- 一 论文题目： c o - r e g u l a r 集可计算性研究 专业：数理逻辑 博士生：邱玉文 指导教师：赵希顺 摘要： 可计算分析是一门新兴的数学和理论计算机学科它研究实数， 实数集和实函数等连续型对象的可计算性和计算复杂性第二型能行性理论( 简 称t t e ) 是研究可计算分析的一种合理模型c o - r e g u l a r 集是工程数学中常用的 一类集合本文在t t e 框架下，研究拓扑空间中c o - r e g u l a r 集的可计算性问题 及其可计算算子问题本摘要分三个部分：首先介绍可计算分析和t t e 理论，然 后引出研究现状和本文动机，最后是主题内容：叙述本文的主要贡献以及意义 0 1可计算分析和t t e 介绍 可计算性图灵机是一个理论计算模型，图灵机将函数严格分为图灵可计算 和图灵不可计算两种一个对象是图灵可计算的，是指有一个能在图灵机上运行 的程序除了图灵机，被公认的其它理论计算模型还有若干个这几个被认可的 计算模型，计算能力是完全一致的丘奇一图灵论题指出：直观意义上的可计算函 数，就是图灵机可计算函数f o d i 8 9 作为现代计算机的理论基础图灵机是现实可行的，任何图灵可计算函数一 定能使用某种计算机语言( 比如c 语言) 编写成可在计算机上运行的程序 可计算分析和数值分析数值分析是研究如何用计算机求解数学问题的一门 学科比如利用计算机求函数的零点、积分，矩阵的特征值，求解微分方程等数 值分析通过设计合理的算法，节省计算机的运算次数和存储空间，来达到减少计 算时间，减少误差累积以达到提高计算精确度的目的但数值分析对计算过程中 误差的累积有时无能为力这个缺陷暴露了目前数字计算机的不足 计算机是以图灵机为原型设计出来的图灵机的构造决定了现代的计算机不 能处理连续性问题尽管数值分析在过去的几个世纪取得了辉煌的成就，但在连 续系统中出现的许多算法问题无法得到令人满意的解决例如算法几何中关于连 2 中山大学博士学位论文 续性模型中的讯号或图像的数字处理、连续( 或混合) 系统中的数字式控制等问 题对于这些数字计算和分析中的问题，在理论上仍是一个缺口数值分析未来 的发展需要建立在一个坚实的可计算理论基础之上，这是可计算分析的任务和意 义所在 可计算分析的目标是系统地表述计算规律它研究的不是一个具体问题的算 法，也不是试图设计制作高性能的数字计算机，而是试图解释科学计算的规律为 数值计算、可计算性及计算复杂性建立可靠的数学基础，从而为计算机的软件理 论建立可靠且能行的数学准备填补经典数学与计算机科学之间的鸿沟 可计算分析的发展可计算分析的起源，是七十多年前以a t u r i n g 首次给出 可计算实数的精确定义为标志的【t u r 3 6 】不久以后，他发现实数的十进制和二进 制不足以恰当地定义可计算实函数 t u r 3 7 于是人们开始尝试用各种理论模型研 究分析学的可能性与经典的可计算性理论f r 0 9 6 7 ，s o a 8 7 ，c u t s 0 】不同，这些不同 流派关于可计算实函数的定义并不完全等价s b a n a c h 和s m a z u r 所用的序列 可计算性定义了实函数的可计算性概念【m a z 6 3 a g r z e g o r c z y k 和d l a c o m b e 建议用快速收敛的有理数列作为实数的表示，并且定义了可计算实函数的概念。 在a g r z e g o r c z y k 和d l a c o m b e 的工作基础上，m p o u r e l 与j r i c h a r d s 以公 理化的方法定义了b a n a c h 空间上的可计算概念f p e r 8 9 ，p e 9 9 1 k w e i r a u c h 与 c k r e i t z 在a g r z e g o r c z y k 和d l a c o m b e 的工作基础上创立了以表示式理论和 第二型图灵机为基础的t t e 理论【k w 8 5 ，w e i 0 0 葛可一应用n p 一完全性理论证 明了一些基本数值运算，如求极值，积分等的计算复杂性下界 k 0 9 1 ，k 0 9 8 自从 上个世纪八十年代以来，以a e d l a t 为代表的许多学者利用域论研究实函数的可 计算性，取得了丰富的成果f w d 8 0 ，w s 8 1 ，s h t 9 5 ，d g 9 6 ，e d a 9 5 ，e d a 9 7 ，e s 9 9 ， s h t 9 9 ，b l a 9 9 1 m a r k o v 的构造主义数学流派则以m a r k o v 算法来定义可计算实 数和可计算实函数f k u s 8 4 ，k u s 9 9 l b l u m ，f c u c k e r ，m s c h u b 和s s m a l e 用 r e a l r a m 模型研究实数计算理论【b c s s 9 6 ，b c s s 9 8 还有人用直觉主义逻辑来 分析分析学中的定理证明及可计算性【n s 9 7 ，d x w j 0 7 在这些不同的流派当中，t t e 有着独特的优势： 简单灵活t t e 理论是经典可计算理论的自然推广它以第二型图灵机为工 摘要3 具，继承了经典图灵可计算理论的简单和灵活经典可计算理论研究自然数集以 及数论函数的可计算性也就是说，它只能处理有限长符号串t t e 是为了研究 实数，连续函数的可计算性，对经典的图灵可计算理论进行改进，t t e 的许多概 念都可以在经典可计算理论中的找到原型 现实可行性t t e 是现实中可行的t t e 是t t 机来处理无限长符号串，凡 是在t t 机上可行的算法，都可以在普通的数字计算机上用常用语言通过编写程 序来运行有一个研究方向叫e x a c ta r i t h m e t i c ，其中心思想是把( 可计算) 实数 而不是其有理逼近直接在计算机运算其中的关键思想之一就是第二型图灵机和 表示论原理 包容性除t t e 之外，可计算分析的每一种流派都定义了它们独有的表示 方法和可计算性，各有其独到之处但是这些理论存在一个共同的缺陷，对计算对 象的表示比较单一，这使得函数的可计算性研究不灵活t t e 则具有很强的包容 性，t t e 允许对同一个研究对象有不同的命名系统，从而导致不同的可计算性 其它模型定义的可计算性仅仅成了t t e 命名系统的某个特殊性t t e 对同一个 对象进行多个等价和不等价的命名系统，这使得t t e 灵活而强大不等价的命名 系统诱导的可计算性可能是不同的，而等价的命名系统其计算复杂性可能是不同 的 t t e 理论的两个构成要素： 命名系统在t t e 中，运算对象总是由有限个字符( 比如0 和1 ) 表示成 有限长符号串或无限长符号串的形式函数的计算过程就是第二型图灵机机将输 入串转化成输出串的过程用符号串来表示计算对象，这种对应关系被称为命名 系统t t e 有两种命名系统，以有限长字符串表示计算对象的叫记号；用以无限 长字符串表示计算对象的叫表示式记号和表示式统称为命名系统同一个计算 对象可以有不同的命名系统不同的命名系统可以比较强弱关系比如实数就可 以用十进制m , 1 0 ，快速收敛的有理数序列表示式等风 第二型图灵机 第二型图灵机是经典图灵机改进后的计算模型它有一条单 向的、可以无限长的只读输入带，一条单向不允许擦除的、可以无限长的只写输 4中山大学博士学位论文 出带，若干条工作带、若干读写头和控制装置输出带上的符号串长度可以是无 限长的输出的任意有限长部分，都是通过输入的有限长部分决定的这一性质 使得每一个可计算函数都是连续函数 0 2本文动机 由于可计算分析的研究起源于实数的可计算性研究，所以在可计算分析理论 发展的早期，研究成果主要集中在欧氏空间r ”的范围内例如酞n 上的极限、实 数、连续、微分、零点、闭集、开集、紧集及加、减、乘、除、交、并、补等最 近人们把可计算性研究延伸到数学的多个分支，代数学【z b 0 0 ，z b 0 4 ，泛函分析 【z w 0 3 ，w e i 0 3 ，g s w 0 7 ，w z 0 7 ，b r a 0 8 】、数值分析 w z 9 9 ，w z 0 1 ，w z 0 2 ，w z 0 5 、 测度论【m u e 9 9 ，w e i 9 9 ，y m t 9 9 ，h w 0 3 ，w d 0 5 ，w d 0 6 】和积分变换等方面，取得 了丰硕成果 w e i r a u c h 、t a n j a 、徐亚涛等人在前人零散工作的基础上，定义并刻画了可计 算度量空间和可计算局部紧豪斯道夫空间 x g 0 7 ，x g 0 8 】对这些空间的闭集和紧 集定义了若干表示式并比较了它们之间的强弱关系随后将这些结论推广到了可 计算的死空间上【x g w 0 8 】和任何空间可计算性研究的初期一样，拓扑空间各 种函数可计算性研究、重要定理的“可计算版本”还是空白 c o - r e g u l a r 集( 也就是满足p = p 的集合) 是工程数学中应用十分广泛的 一类集合z i e g l e r 等对欧氏空间上r e g u l a r 集的可计算性和可计算算子进行研究 【z i e 0 2 ，z i e 0 4 ，z i e 0 5 】c o - r e g u l a r 集与r e g u l a r 集的可计算性结论可以互相利用 本文选题的目的是希望系统地进行c o - r e g u l a r 集的可计算性研究，然后尝试把一 些结果推广到度量空间和局部紧豪斯道夫空间上【q z 0 7 ，q z 0 7 a ，q z 0 8 ，q z o s a 0 3 主要结论 本文结论主要分四部分：第一部分从不同角度提出了欧氏空间c o - r e g u l a r 集 的若干表示式；比较了不同表示式之间的强弱关系；第二部分是c o - r e g u l a r 集上 可计算算子的情况；第三部分是运用第一部分结论对可计算分析其它学派可以用 摘 要 5 来表示c o - r e g u l a r 集的命名系统进行强弱比较最后一部分是度量空间和拓扑空 间上c o - r e g u l a r 集的可计算性具体结论如下： ( 一)欧氏空间上c o - r e g u l a r 集的可计算性 在欧氏空间上，从不同的角度出发，给出了c o - r e g u l a r 集的1 0 种不同表示式 在这些表示式中，硒 、毋 、口 、砂。 和瓦表示p 的外部信息我们讨论了这些表示式之间的关系，得到了重要结论 【q z 0 7 ，q z o s a 口 万 妒三 秽 笺 o ( 二)c o - r e g u l a r 集上的可计算算子 集合p 上的常用算子有交、并、i n t 等，这些算子关于我们定义的表示式可计 算性如下： o p 上的交运算r - ：( p l ，p 2 ) hp lnb 是关于 ( 6 ，6 ：瓦) 一可计算的；( 如，如，如) 一可计算的；( 如如：如) 一 可计算的；( 瓦，瓦，瓦) 一可计算的； ( 螺，蠼，掣，；) 一可计算的 p 上的并运算u ：( ，) l ，尼) h ，) lur 是关于 ( 6 i ，氏，1 5 ) 一可计算的；( 瓦，瓦，瓦) 一可计算的；( 蠼蠼，蠼) 一可计 算的； ( 万 ，万 ，万 ) 一可计算的；( 一 ， ，秽 ) 一 可计算的； ( 娉，蠼，妒；) 一可计算的 o 对于可计算函数和开映射，：r d r d ，算子ph 厂1 【p 】是： ( 9 ) 一可计算的；( 砣，瓦) 一可计算的；( 砂呈，蠼) 一 可计算的算子关于没有提到的那些命名系统是不可计算的 6 中山大学博士学位论文 。 对于可计算函数和开映射g ：r d _ 彩，映射phg p 】是 ( 万 ) 一可计算的；( 蠼，砂兰) 一可计算的；( 螺，蠼) 可计算的算子关于没有提到的那些命名系统是不可计算的 o内部算子i n t ：ah a 。是( 砂 ，吠) 一可计算的和( 如，蠼) 一可计算的， 算子关于没有提到的那些命名系统是不可计算的 ( 三)c o - r e g u l a r 集常用的表示式强弱比较 m g r o t s c h e l ，l l o v a s z 和a s c h r i j v e r 利用w m o 方法对集合元素进行测 试，根据测试信息定义了表示式w g l s 9 4 1 ，m k u m m e r 和m s c h i i f e r 定义了可以 用来表示c o - r e g u l a r 集的表示式7 ，p 和x k s 9 5 】，p h e r t l i n g 和k w e i h r a u c h 定 义了可以用来表示c o - r e g u l a r 集的表示式6 h e r 9 9 ，h w 0 3 ，a e d a l a t ，a l i e u t i e r 和e k a s h e f i 提出了表示式7 r e l k 0 2 这些可以用来表示c o - r e g u l a r 集的表示 式散落于不同的研究文献之中，彼此关系是未知的利用c o - r e g u l a r 集的不同表 示式的定义及其强弱关系，结论如下： u 兰妒 ； p 三口 ； 6 三口 1 1 儿； 妒三砂 ； t 三妒 i - 1 以 x 兰一 丌三瓦n 螅 三6 i - - z - o ( n 记 根据c o - r e g u l a r 集命名系统的转化关系：在这些文献提到的八个表示式当中， ( 1 )弘三6 x u 三7 - ； ( 2 )，l 兰6 7 r u 三7 ； ( 3 )p 三6 一 砂 u 兰7 - ； 也就是说，p 和6 是最强的，u 和7 - 是最弱的 ( 四)度量空间和拓扑空间上c o - r e g u l a r 集的可计算性 喊 - _ 摘要7 在度量空间上，我们提出了c o - r e g u l a r 集的如下2 0 个命名系统，其中1 0 个 是反映p 的内部信息，分别是： p 、西 、k 、嗫、吩- 2 o 、藓。 我们也得出了上述命名系统转化关系的初步结论 瓦 ( 1 ) 口 6 6 芝； 砖。叼。 ( 2 ) 口 p 面。； ( 3 ) 百三； 岛。9 。 ( 6 ) 6 秽 6 d 。媚k ； ” ( 7 ) 如目，。叼。0 ； ( 8 ) 啡。_ 9 。6 i - - ：- 09 。- - 0 对于可计算局部紧豪斯道夫空间，定义了描述c o - r e g u l a r 集的命名系统共1 2 个，其中6 个是反映p 的内部信息，分别是： p 、万 、够、如、砖。 8 中山大学博士学位论文 我们也得出了上述命名系统转化关系的初步结论 ( 1 ) 口 瓦可 s 妒芝； ( 2 ) 口 - - 日o ； ( 5 ) 妒 毋 a ； ( 6 ) 目_ - - 2 ，0 。叼。醒 上述结论的意义何在? 根据t t e 理论，一个函数，：x z 是( q ，6 ) 可计算的，是指存在一个 t t 机m ，输入z x 的任意个q 表示式，可以输出，( z ) y 的个6 表示式 但是如果一个函数是( 口，6 ) 一不可计算的，使，变成可计算函数的方法有两个：一 种方法是输入比q 更强的表示式；另一种办法就是输出比6 表示式弱的表示式 比如：映射r e ：aha 。是( 妒 ，秽 ) 一不可计算的而对于任何闭集来讲，4 。 是c o - r e g u l a r 集，用比p 更弱的咒表示式来替换，得到映射r e ：ah 月。是 ( 妒 ，砂三) 一可计算的c o - r e g u l a r 集定义的不同的命名系统，使得函数能行性的讨 论变得更加灵活，层次更分明 第二部分是对p 上常见算子的可计算性研究，包括常见的算子交、并、内部 运算以及可计算的连续开函数的情况这些结论可以产生一些连续开函数经典定 理的可计算版本它表明了可以用通用的数字计算机来证明抽象的数学定理即 在一定程度上实现定理证明的自动化 第三部分充分体现了t t e 理论具有很好的包容性对可计算分析其它学派 用来刻画c o - r e g u l a r 集的表示式，只是我们定义的十种表示式的一个组合特例 我们还对这些学派所提出表示式的强弱还进行了排序这些不同背景的表示式之 间的是否等价、孰强孰弱或者彼此不可以互相转化，都是十分明确的f q z o s a 摘要9 在欧氏空间r “上，关于闭集的表示就有很多种，但是它们大多是彼此等价 的但是这些表示式在度量宅问上，并不完全等价( 比如矽 菇讧。，。) 这就使得 拓扑空间上c o - r e g u l a r 集的可计算研究，绝不只是舻的可计算性平移 研究表明，砂 仉。仅仅在完备空间上成立，这使得度量空间和欧氏空间 上关于闭集的命名系统转化关系存在较大差异度量空间和局部紧豪斯道夫空间 上c o - r e g u l a r 集的可计算性研究可以夯实函数连续性及可计算性研究的基础 关键词：可计算分析；第二型能行性理论；表示式；转化；c o - r e g u l a r 集；拓 扑空间 t i tl e ： s t u d yo fc o m p u t a b i l i t yo nc o - r e g u l a rs u b s e t m a j o r ： m a t h e m a t i c a ll o g i c n a m e ：q i uy u w e n s u p e r v i s o r ：z h a ox i s h u n a b s t r a c t ： c o m p u t a b l ea n a l y s i si sab r a n c ho fc o m p u t a b i l i t yt h e o r ys t u d y - i n gc o m p u t a b l ef u n c t i o n sa n ds u b s e t so fe u c l i d e a ns p a c e sa n do t h e rt o p o l o g i c a l s p a c e s t y p e - 2t h e o r yo fe f f e c t i v i t y , f o rs h o r t ，c a l l e dt t e ，i sat h e o r yo fc o n t i - n u i t ya n dc o m p u t a b i l i t yv i an a m i n gs y s t e m i te x t e n d sc l a s s i c a lr e c u r s i o nt h e o r y w h i c hs t u d i e sc o m p u t a b i l i t ya n dc o m p l e xt h e o r yo nt h en a t u r a ln u m b e r sa n df i - n i t ew o r d s i nt t e ，i n f i n i t es t r i n g so fs y m b o l sa r eu s e da sn a m eo fc o n t i n u o u s o b j e c t s t h e r ea r et w om a i nt o o l sa p p l i e di nt t e ：n a m i n gs y s t e m sa n dt y p e - 2 t u r i n gm a c h i n e t h ef o r m e rc o n s i s t so fn o t a t i o n sa n dr e p r e s e n t a t i o n s t h el a t t e r i sak i n do fg e n e r a l i z e dt u r i n gm a c h i n e ，w h i c hc a nt r a n s f o r mi n f i n i t es t r i n g st o i n f i n i t es e q u e n c e s t o p o l o g yi sa ni m p o r t a n ta n db a s i cb r a n c ho fm a t h e m a t i c s ，w h i c hs t u d i e st h e c o n t i n u i t ya b s t r a c t e df r o mn a t u r a lp h e n o m e n a a s ag e n e r a l i z a t i o no fc o m p u t a b i l o i t yo nt h er e a l s ，c o m p u t a b l et o p o l o g yh a sb e e np a i dm o r ea n dm o r ea t t e n t i o n si n r e c e n ty e a r s p ，t h es e to fa l ls u b s e t ss u c ht h a tp 。= p ，i sas o r to fi m p o r t a n t s u b s e t so ne u c l i d e a ns p a c e s c o - r e g u l a rs u b s e t sa r eu s e f u li ne n g i n e e r i n g i nt h i s t h e s i sw ei n t e n dt os y s t e m a t i c a l l yi n v e s t i g a t ec o m p u t a b i l i t yo fc o - r e g u l a rs u b - s e t s ，a n dg e n e r a l i z et h ec o m p u t a b i l i t yo nm e t r i ca n dl o c a l l yc o i n p a c th a u s d o r f f t o p o l o g i c a ls p a c e s t h ec o n c l u s i o nw i l lc o n s o l i d a t et h ef o u n d a t i o no fc o m p u t a b l e t o p o l o g i c a ls p a c e s t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ed i v i d e di n t of o u r p a r t s r e p r e s e n t a t i o n so fc o - r e g u l a rs u b s e t so nr ” w ed e f i n ea n dc h a r a c t e r i z et e nr e p r e s e n t a t i o n so fc o - r e g u l a rs u b s e t so nr “ i b 、- a b s t r a c t 1 1 f r o md i f f e l e n tp o i n t so fv i e w i nt h e s et e nr e p r e s e n t a t i o n s ，万 ，一 ，p ，t v a n d - - ：- 0a r ed e s c r i b e d b yo u t e ri n f o r m a t i o n w ea l s od i s c u s st h e i rr e l a t i o n s h i p sv i ac o m p u t a b l er e d u c i b l e f u n c t i o n t h ef o l l o w i n ga r et h e s er e p r e s e n t a t i o n sa n dt h e i rr e d u c i b l eo r d e r s 咒 一 p 。、 一 砂 _ 妒三 秽 蠼_ 如_ 瓦 以 t h ec o m p u t a b l eo p e r a t o r so i lp i nt h i ss e c t i o nw ed i s c u s sc o m p u t a b l eo p e r a t o r so np t h e s eo p e r a t o r si n c l u d e i n t e r s e c t i o n ，u n i o n ，i n n e ro p e r a t o ra n dt h r e eo p e r a t o r si n d u c e db yc o n t i n u o u sa n d 前 o p e nf u n c t i o n s ot h ei n t e r s e c t i o no p e r a t o rn ：( r p 2 ) h 只np 2o ns e tp a r e ( 正6 ，6 ) c o m p u t a b l e t h e s ec o m p u t a b l er e p r e s e n t a t i o n s6i n c l u d e ： 护 蝣如以瓦 ot h eu n i o no p e r a t o ru ：( p l ，p 2 ) hp 1u 局o ns e tp a r e ( 6 ，6 ，6 ) 一 c o m p u t a b l e t h e s ec o m p u t a b l er e p r e s e n t a t i o n s6i n c l u d e ： 6 i 瓦妒：万 1 5 i 妒呈 i na d d i t i o n ，w ep r o v es o m ec o n t i n u o u sa n d o p e nf u n c t i o n sa r e ( 6 ，6 ) c o m p u t a b l e a b o u ts e v e r a lc e r t a i nr e p r e s e n t a t i o n s6 t h e s ef u n c t i o n si n c l u d e ： o c o m p u t a b l ea n do p e nf u n c t i o n ： o c o m p u t a b l ea n do p e nf u n c t i o n9 ： oi n n e ro p e r a t o r ：i n t ：aha o p h 厂1 p 】； ph 9 fp 】； 1 2 中山大学博士学位论文 t h er e l a t i o n s h i p sb e t w e e nr e p r e s e n t a t i o n sf r o mo t h e rb r a n c h e s v a r i o u ss i m i l a rb u tn o te x a c t l ye q u i v a l e n tr e p r e s e n t a t i o n so fc o - r e g u l a rs u b - s e t sh a v eb e e np r o p o s e db ys e v e r a ls c h o l a r si nr e c e n ty e a r s g l s 9 4 ，k s 9 5 ，h e r 9 9 ， h w 0 3 ，e l k 0 2 t h er e p r e s e n t a t i o n sp r o p o s e di nt h e s ep a p e r si n c l u d e ： p ，6 ，x ，7 r ， u7 - 妒 t h er e l a t i o n s h i p si n d u c e db yr e d u c i b i l i t ya r et h ef o l l o w i n g ： o p 兰6 x u 兰7 i ； o p 三6 _ 7 r u 三- r ； o p 兰6 _ 砂 u 三7 ； i nt h ef r a m e w o r ko ft t e ，w es h o wt h a tpa n d6a r et h es t r o n g e s ta m o n gt h e a b o v es i xr e p r e s e n t a t i o n s w h i l eua n d7 a r et h ew e a k e s tr e p r e s e n t a t i o n s r e p r e s e n t a t i o n so fc o - r e g u l a rs u b s e t so nm e t r i ca n dl o c a l l yc o r n - p a c th a u s d o r f fs p a c e s w ed i s c u s sd i f f e r e n tr e p r e s e n t a t i o n so fc o - r e g u l a rs u b s e t so nm e t r i cs p a c e s f r o md i f f e r e n tp o i n t so fv i e w i nt h e s ed i f f e r e n tr e p r e s e n t a t i o n s ， 口 、西 、否 、万x 否d 。m 、姆、口；、甥。、瓦a n d6 i _ - - ：o 。姐。a r e d e s c r i b e db y o u t e ri n f o r m a t i o n i nl o c a l l yc o m p a c th a u s d o r f fs p a c e s ，w ed i s c u s s1 2r e p r e s e n t a t i o n so fc o - r e g u l a rs u b s e t sa sf o l l o w s ： o 口 、石 、玩。n g e 、妒三、蛇。g 。a n d - - 6 o ； 易、瓦、玩、蠼、如、配。9 。 w ea l s od i s c u s st h e i rr e l a t i o n s h i p sv i ar e d u c i b i l i t y t h e s ec o n c l u s i o n sa r e n e c e s s a r yf o u n d a t i o no fc o m p u t a b l eo p e r a t o r so nm e t r i ca n dt o p o l o g i c a ls p a c e 1 k 目录1 3 k e y w o r d s ：c o m p u t a b l ea n a l y s i s ；t y p e - 2e f f e c t i v et h e o r y ；r e p r e s e n t a t i o n ： r e d u c t i o n ；c o - r e g u l a rs u b s e t ；t o p o l o g i c a ls p a c e ， c 目录 中文摘要( i ) a b s t r a c t ( i i ) 论文原创性声明 ( i i i ) 论文术语( 1 ) 第一章前言( 3 ) 1 1 选题背景( 3 ) 1 2研究动态和选题动机( 8 ) 1 3主要结论( 1 0 ) 1 4论文结构( 1 4 ) 第二章预备知识( 1 5 ) 2 1第二型能行性理论( 1 5 ) 2 2 拓扑空间( 2 9 ) 第三章c o - r e g u l a r 集的可计算性( 3 3 ) 3 1引言( 3 3 ) 3 2r d 上c o - r e g u l a r 集的可计算性( 3 3 ) 3 3 关系式之间的转化关系( 3 7 ) 3 4小结( 4 3 ) 第四章其它流派提出的c o - r e g u l a r 集表示式( 4 5 ) 4 1引言( 4 5 ) 4 2其它流派提出的c o - r e g u l a r 集表示式( 4 5 ) 第五章 c o - r e g u l a r 集上的可计算算子( 5 3 ) 目录 1 5 5 1 几个引理( 5 3 ) 5 2 c o - r e g u l a r 集上的可计算算子( 5 6 ) 第六章度量空间上c o - r e g u l a r 集的可计算性( 6 5 ) 6 1 背景介绍( 6 5 ) 6 2 度量空间上c o - r e g u l a r 集的可计算性( 7 2 ) 第七章拓扑空间上c o - r e g u l a r 集的可计算性( 7 7 ) 7 1 引言( 7 7 ) 7 2 可计算的局部紧豪斯道夫空间( 7 7 ) 7 3 局部紧豪斯道夫空间上c o - r e g u l a r 集的可计算性( 8 6 ) 7 4 小结( 8 6 ) 第八章研究结论和未来工作( 8 9 ) 后记( 9 0 ) 专业术语的中英文对照( 9 1 ) 参考文献( 9 3 ) + “ ( t ，) qp k w ) ep c 6 ( n ) 株 z ，：尸一q ，：p = q 论文术语 建立在有限字符集上的所有有限长字符串的集合，在本论文中 无特别声明，通常指= o ，1 ) 建立在有限字符集上的所有无穷长字符串的集合 存在有限长的串u 和无限长的串q ，使p = c ( t ，) ( 叫) 口 伽是串p 的前缀 所有n 维有理( 中心和直径) 开立方体所组成的集合 自然数集n 的标准记号 有理数集q 的标准记号 可数集合c b 的标准记号 ，是建立在集合p 到q 上的部分单值函数 f 是建立在集合p 到q 上的部分多值函数，p 的某子集合是定义 域而q 是函数，的值域 将无穷串p 和q 组合变成的新串 建立在r 上的标准表示式 所有建立在集合a 到b 的全函数i ：a b 的集合 建立在集合r ”上的所有连续函数的集合 所有闭集所组成的集合 所有开集所组成的集合 所有紧集所组成的集合 所有c o - r e g u l a r 集所组成的集合 所有r e g u l a r 集所组成的集合 从x 到y 的所有连续全函数所组成的集合 从x 到y 的所有连续部分函数所组成的集合 d 鼢 x似、 p舻咿4 d 足p 冗啾叫 2 中山大学博士学位论文 所有定义域是g 6 的连续函数所组成的集合 p 。的标准记号 存在一个可计算函数，把命名系统q 转化为p 存在一个连续函数，把命名系统n 转化为p 集合a 的内部 集合a 的闭包 集合a 集合b 的差集 扩展的实数集，即r u 一。，+ 。o ) i d 严俨晒!a，r ， 色 0 第一章引言 本论文是在第二型能行性理论( t t e ) 框架下研究可计算分析方面的问题可 计算分析是数理逻辑中递归论的一个分支，以实数、实数集合和连续函数的可计 算性为研究对象，是近几十年逻辑学、数学和理论计算机专家都十分关注的一个 热门领域t t e 是可计算分析的一个流派，因其灵活和包容性强而被广泛接受 本论文选择工程数学中常用的c o - r e g u l a r 集作为研究内容，探讨c o - r e g u l a r 集的 可计算性以及c o - r e g u l a r 集上的算子可计算性问题。 这一章包括四部分内容第一部分是选题背景，介绍可计算性理论、可计算 分析和t t e 理论的发展情况；第二部分介绍可计算分析研究现状和选题动机，包 括与论文研究相关的研究最新情况，以及这些研究的意义第三部分简介论文的 主要结论，这部分包括研究的主要结论是什么，结论还有什么不足及下一步研究 的方向等在本章的最后部分，介绍论文的篇章结构 1 1选题背景 这一节从图灵可计算理论出发，介绍可计算分析的产生、流派以及t t e 理论 的基本思想 1 可计算性 可计算性及可计算性理论，起源于上世纪初对数学基础问题的研究1 9 3 0 年 哥德尔不完全性定理发表之前，数学家们总认为一个数学问题理论上总有一个确 定的答案一个数学命题，要么是真的，要么是假的，总可以在有限步之内给出证 明而哥德尔不完全定理指出：在一个稍微复杂一点的数学公理系统中，总存在 那样的命题，我们既不能证明它是真的，也不能证明它是假的 g o d 6 5 】 数学家们大吃一惊，被大家认为绝对严密的数学中，原来有令人不安的不确 定性逻辑学家也在苦苦思索，试图为陷入了困境的数学找到一条出路这些逻 4 中山大学博士学位论文 辑学家包括罗素、怀特海、维特斯根坦和图灵等对于一个数学命题，一般的研究 工作者只想到用公式去推导结论是否成立图灵不愿意暴守成规，他把每步复杂 的运算( 推导) 分解成若干步简单的操作：如移位、识别、个位数加法乘法等他 试图设计一个“会计算和证明的机器”按这样的思路，1 9 3 6 年图灵发表了他的著 名论文 论可计算数在判定问题中的应用【t u r 3 6 】，在文中设计了一种现在被称 为图灵机的计算模型 图灵机的出现解决了可计算理论最重要的一个难题图灵机这种计算模型能 将算法这一直观概念精确化一个函数是图灵可计算的，是指有一个可计算这个 函数的图灵机图灵机的不同在于计算函数的指令集的区别函数因此可以严格 区分为图灵可计算函数和图灵不可计算函数当然数学家和逻辑学家们早已发现， 计算和证明本质上是一回事 在图灵发表他的论文后不久，丘奇和波斯特等人也提出了可计算性的概念：丘 奇在美国数学评论上发表文章。一个不可解的初等数论问题”文中提到了两 个可计算性概念：入可定义函数和一般递归函数这两个种函数很快被证明是等 价的图灵很快发现a 可计算函数与他定义的图灵可计算函数也是等价的波斯 特提出了产生式系统，而产生式系统导出的函数恰恰就是图灵可计算函数【s i p 0 2 于是人们接受了被称为“丘奇一图灵论题”的断言【p e 9 9 ，s i p 0 2 】：