（应用数学专业论文）一类非线性偏微分方程初边值问题的可计算性分析.pdf

江 苏 大 学硕 士 学位论丈 摘要 研究微分方程解的数值算法足数值分析的核心用来解微分方程的数值技术 主要包括有限差分法和有限元法，目标是通过这种数值技术找到稳定的算法来快 速收敛到正确的解但是这些方法还不能够适用于每一个微分方程可计算分析 主要研究：如何来计算微分方程所描述的物理过程可计算分析是以图灵机为基 础研究连续性问题的可计算性和可计算复杂性在可计算分析当中，如果存在着 一个图灵机能够从给定参数的近似值计算出收敛到微分方程解的近似值，那么， 这个微分方程的解就是叮计算的，存在着收敛算法的数值解也就得到了保证 本文对变系数k d v b u r g e r s 方程和薛定谔方程解算子的可计算性进行研究 全文共分五章：首先，对可计算理论的研究历史和现状进行了综述第二章介绍 了图灵机和t t e 理论框架，给出了多种可计算空间的定义及其相应空间上的可计 算性质第三章应用t t e 理论，算子半群理论，证明了索伯列夫空间上的变系数 k d v b u r g e r s 方程的解算子在b o u r g a i n t y p e 空间上是图灵可计算的第四章对带 有初边界值条件的线性薛定谔方程，通过作关于t 的l a p l a c e 变换得到等价的积 分方程，证明了方程的解算子是图灵可计算的第五章对带有初始条件的非线性 薛定谔方程，在索伯列夫空间上证明该方程的解算子是图灵可计算的 可计算性的证明过程通常会产生图灵算法，这些图灵算法可能会被转化为数 值算法本文所得到的研究结果拓展了数字计算机解微分方程的应用领域 关键词：图灵机，索伯列夫空间，可计算函数，微分方程解算子 江苏大 学 硕 士 学 位论文 a b s t r a c t t h es t u d yo fn u m e r i c a la l g o r i t h m sf o rs o l u t i o n so fd i f f e r e n t i a l e q u a t i o n si sc e n t r a li nn u m e r i c a la n a l y s i s t h en u m e r i c a lt e c h n o l o g yf o r s o l v i n g d i f f e r e n t i a l e q u a t i o n s i n c l u d e sf i n i t e d i f f e r e n c em e t h o d sa n d f i n i t e - e l e m e n t sm e t h o d s t h ea i mi st of i n dn u m e r i c a l l ys t a b l ea l g o r i t h m s t h a tr a p i d l yc o n v e r g et ot h ec o r r e c ts o l u t i o n b u tt h e s ea l g o r i t h m sc a nn o t b es u i t a b l et oe v e r yd i f f e r e n t i a le q u a t i o n c o m p u t a b l ea n a l y s i si ss t u d y i n g h o wt oc o m p u t ep h y s i c a lp r o c e s s e sm o d e l e db yd i f f e r e n t i a le q u a t i o n s i ti s t h es t u d yo fc o m p u t a b i l i t ya n dc o m p l e x i t yo fc o n t i n u o u sp r o b l e m sb a s e d o nt u r i n gm a c h i n e s i nt h ec o n t e x to fc o m p u t a b l ea n a l y s i s ，t h es o l u t i o no f ad i f f e r e n t i a le q u a t i o ni sc o m p u t a b l ei ft h e r ei sat u r i n gm a c h i n et h a t c o m p u t e sa p p r o x i m a t i o n sc o n v e r g i n gt ot h es o l u t i o nf r o ma p p r o x i m a t i o n s t og i v e n p a r a m e t e r s s o t h ee x i s t e n c eo fc o n v e r g e n ta l g o r i t h m sf o r n u m e r i c a ls o l u t i o ni sg u a r a n t e e d i nt h i sp a p e r , w es t u d yt h ec o m p u t a b i l i t yo ft h es o l u t i o no p e r a t o r so f t h ev a r i a b l e - c o e f f i c i e n t k d v - b u r g e r se q u a t i o n ，a n dt h es c h r 6 d i n g e r e q u a t i o n t h i sw h o l ew o r ki sp r e s e n t e di n5c h a p t e r s f i r s t l y , a no v e r v i e w i s g i v e no nt h eh i s t o r i c a la n dp r e s e n ts t u d i e so fc o m p u t a b i l i t yt h e o r y c h a p t e r 2i n t r o d u c e s t u r i n gm a c h i n e ，t h e f r a m e w o r ko fr r e ，a n d p r o p o s e s s e v e r a lb a s i c c o n c e p t s a n d c o m p u t a b i l i t yp r o p e r t i e s o n c o m p u t a b i l i t ys p a c e c h a p t e r 3d i s c u s s e s t h e v a r i a b l ec o e f f i c i e n t k d v - b u r g e r se q u a t i o ni nb o u r g a i n t y p es p a c e s ，w ep r o v ei t s s o l u t i o n o p e r a t o ri st u r i n gc o m p u t a b l eb ym a k i n gu s eo ft t ef r a m e w o r ka n d s e m i - g r o u pt h e o r i e s c h a p t e r4s t u d i e st h e l i n e a rs c h r 6 d i n g e re q u a t i o n s w i t hi n i t i a l b o u n d a r yv a l u ec o n d i t i o n s ，w eg e t i t s e q u i v a l e n ti n t e g r a l e q u a t i o nb yt a k i n gt h el a p l a c et r a n s f o r mw i t hr e s p e c tt ot h ev a r i a b l et ， t h e nw ep r o v et h a ti t ss o l u t i o ni st u r i n gc o m p u t a b l e c h a p t e r5s t u d i e st h e 1 1 江 苏大 学 硕 士 学 位论 文 n o n l i n e a rs c h r 6 d i n g e re q u a t i o nw i t hi n i t i a lc o n d i t i o n ，w ep r o v et h a ti t s s o l u t i o ni st u r i n gc o m p u t a b l ei ns o b o l e vs p a c e t h ep r o o f so fc o m p u t a b i l i t yg i v er i s et ot u r i n ga l g o r i t h m s ，w h i c h m a yp o s s i b l yb et r a n s l a t e di n t on u m e r i c a la l g o r i t h m s t h e s e r e s u l t se x t e n d t h ea p p l i c a t i o no f d i g i t a lc o m p u t e r st os o l v ed i f f e r e n t i a le q u a t i o n s k e y w o r d s ：t u r i n gm a c h i n e ，s o b o l e vs p a c e ，c o m p u t a b l ef u n c t i o n ， s o l u t i o no p e r a t o ro fd i f f e r e n t i a le q u a t i o n 1 1 1 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文 本学位论文属于 学位论文作者签名： 卅年，月列日 保密口，在 年解密后适用本授权书 不保密圈 呼彳 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果除文中已注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果对本文的 研究做出重要贡献的个人和集体，均己在文中以明确方式标明本人完 全意识到本声明的法律结果由本人承担 学位论文作者签名： 譬修砰 1 日期：沙7 年， 月2 1 日 江苏大 学 硕士 学位论 文 第一章绪论 1 1 可计算理论的发展历史 无论在r 常生活中，还是在工程没计和科学研究中，都需要计算因此，人们 一直在广泛地进行计算但是，直到最近几十年以来，人们才对计算本身进行深入 的研究所谓计算包括数的加减乘除，也包括函数的微分、积分，微分方程的求 解等还包括定理的证明推导抽象地说，所谓计算就是从一个符号行乡得出另一 个符号行7 7 譬如说符号行f 是h ，而符号行刁是x 2 + c ，( c 是常数) ，从孝到r 的 计算就是积分从这个角度来看，定理的证明也是计算令f 表示一组公理及推理 规则，令，7 是一个定理，那末从孝得出7 7 就是定理7 7 的证明 计算和算法应该足具体的，这就需要通过建立计算模型的方法来加以确定计 算的共同点t u r i n g 机就是一个合适的计算模型所谓计算，是指t u d n g 机所进行 的工作就是计算，在t u d n g 机中可以进行的就是可计算为了精确地定义算法， 从2 0 世纪3 0 年代开始提出了多种形式不同的计算模型它们是五转换演算 溶c h u r c h ，1 9 3 5 年) ，t u r i n g 机( a m t u f i n g ，1 9 3 6 年) ，递归函数( k g b d e l ， j h e a n d 和s c k l e e n e ，1 9 3 6 年) ，正规算法( a a m a r k o v ，1 9 5 1 年) 以及无限寄存 器机器( j c s h e p h e r d s o n ，1 9 6 3 年) 等c h u r c h 提出：可以用旯转换演算定义的函数 与直观可计算函数类相同而t u r i n g 提出：可以用t u r i n g 机计算的函数类与直观 可计算的函数类相同实际上，可以用力转换演算定义的函数类与可以用t u r i n g 机计算的函数类是同一个函数类因此，他们两人说的是一回事，现在通称为 c h u r c h - t u r i n g 论题 c h u r c h t u r i n g 论题：直观可计算的函数类就是t u r i n g 机以及任何与t u r i n g 机等价的计算模型可计算( 可定义) 的函数类 上述提到的模型都是等价的两个模型等价的意思是它们能够相互模拟，即 一个模型中的操作都能在另一个模型中实现，从而它们具有相同的计算能力直 观可计算性不是一个数学概念，没有严格的形式定义，无法对它进行严格的形式 论证提出计算模型正是为了给出可计算性的严格的形式定义 计算机及计算科学的发展推动了对计算的研究但是可计算性理论的形成与 电子计算机无关，它是在数理逻辑的研究中产生的是数理逻辑学家在研究定理 江 苏 大 学 硕 士 学 位论文 的证明及推导这种类型的特殊计算中，建立了可计算性理论关于可计算性概念 是在1 9 3 6 年前后建立起来的，这是数理逻辑学家在研究数理逻辑的基本问题时 得到的结果，为四十年代研制电子计算机提供了计算理论模型正是t u f i n g 机的理 论推动了计算机的研制，使得电子计算机能够顺利产生可计算性理论不仅是数 学的一个分支，而且是整个计算机科学的基础理论 经典的可计算理论代表人物是英国的科学家图灵图灵( a m t u r i n g ， 1 9 1 2 1 9 5 4 年) 出身于英国伦敦西部的p a d d i n g t o n 区图灵的重要贡献在于建立了 图灵机模型，奠定了可计算理论的基础，简单地说，图灵机就是一个逻辑机的通 用模型图灵证明，只有图灵机能解决的计算问题，实际计算机才能解决；如果某 计算问题图灵机不能解决，则实际计算机也无法解决图灵机的能力概括了数字计 算机的实际计算能力 计算的对象大致可以分为两类：一类是数；一类是符号行利用g 6 d e l 编号 可以把符号行的计算化为自然数的计算，实现算术化通过g 6 d e l 编号把数理逻 辑符号的运算转化为自然数的计算，可计算理论的研究是从自然数的函数开始的 在计算模型中，t u d n g 机摆脱了自然数的限制，它完全可以直接处理符号计算 k g 6 d e l 率先提出“原始递归函数 就是可计算函数不久人们就发现了一个 用多重递归定义的函数不是原始递归函数于是，数理逻辑学家又在原始递归函 数的定义中加了一个“极小”算子，由此定义了广义递归函数的概念1 9 3 6 年， a t u r i n g 在著名文章 1 中提出要用可计算无穷二进制小数来表示可计算实数，并 且把一个问题的可计算性描述为在具有严格定义的理想计算机( 后人称之为图灵 机) 上的可解性1 9 3 7 年，他又在 2 中指出可计算实数也可以等价地用具有有理 端点的区间套来表示于是，产生了c h u r c h 论断：一个部分函数厂：一+ ( 其 中是一个充分大的字母表，+ 是由其生成的所有有限字符序列构成的集合) 在 直观意义上是可计算的当且仅当它能够为图灵机所计算 1 9 5 5 年，波兰逻辑学家a g r z e g o r c z y k 在文章 3 中提出了可计算实函数的概 念它主要包括两个基本特征( 1 ) 厂：f o ，1 1j 碾是可计算的当且仅当厂具有一致连 续的模函数，并且它把一个可计算的序列映射为另一个可计算的序列，这已经由 p o u r - e 1 和r i c h a r d s 推广到了可计算b a n a c h 空间h 1 ( 2 ) 单调可计算函数把有理区 间映射为另一个有理区间，这成为区间分析的可计算背景旧，印( 区间分析主要研究 2 江 苏 大 学 硕 士 学 位论文 一些空间，例如：实数空间上的可计算性n 8 9 m j 2 1 ) 1 9 5 7 年，a g r z e g o r c z y k 又 在 1 3 中给出了 3 的几个等价定义可计算实函数概念暴露了c h u r c h 论断的局 限性( 它对实数集合上的函数均无效) ，所以一些科学家试图对其进行推广1 9 7 5 年1 9 9 5 年，a b o r o d in ，i m u n r o ，l b l u m ，m s h u l ，s s m a l e ，等人在文献 1 4 ，1 5 ，1 6 ，1 7 ，1 8 中提出了“r e a lr a m 模型，但是几乎所有的“r e a lr a m 函 数都不是连续的，例如最基本的正弦函数和指数函数都不是r e a lr a m 可计算的 1 9 9 6 年，p h e r d i n g ，p h e r t l i n g v b r a t t k a 在文献 1 9 ，2 0 中对“r e a lr a m 模型进行修改，使其能够在数字计算机中实现，其中判别函数“x o 用无限近 似来表示a s t r o e l s t r a d v a nd a l e n 胁1 ，b i s h o p 胁1 ，c e i t i n 3 ，h a u c k 幽1 ，k o 瞄3 等人也建立了一些可计算模型，但是看似直观的定义却彼此不等价，因此这些工 作并没有得到大多数数学家的承认但是，这种建立数学模型的方法在计算机科 学当中得到了广泛的应用 可计算性分析是研究实数集上的函数的可计算性理论的一个分支，这些函数 能够被数字计算机计算在科学计算和工程学中需要可靠的软件不断增加，这就 要求有一个既属于分析的、数值计算的也属于实数计算的可计算性方面的稳定的 基础。只有少数的数学家和计算机科学家知道可计算实函数的定义，然而，可计 算分析却呈现出几个相互独立的方法的并立，这些方法或多或少得到了一些发展 因为没有一个被广泛接受的基本定义，k l a u sw e i h r a u c h 建立了一套关于可计算 分析的连贯的基础h 引 计算复杂性的研究始于2 0 世纪6 0 年代初，当时在美国有两个研究中心，一 个是通用电器公司设立在纽约州克内克塔迪的研究实验室，研究人员j h a r t m a i s 和r s t e a r n s 于1 9 6 4 年在普林斯顿举行的第五届开关电路理论和逻辑设计学术 年会上发表了题为“c o m p u t a t i o n a lc o m p l e x i t yo fr e c u r s i v es e q u e n c e s 的 论文，论文中首次使用了计算复杂性这一术语，开创了计算机科学的一个新领域。 另一个中心是麻省理工学院，布卢姆研究了递归函数复杂性的机器独立证明。作 为可计算理论一个分支的计算复杂性理论，是以前者的复杂程度为其研究对象； 而作为计算机科学的一个领域的复杂性理论，则是以后者的复杂程度为其研究对 象。 目前世界上大量的计算机被用来做实数的计算这不仅是指实函数的求值计 3 江 苏 大 学 硕 士 学位论 文 算，寻找函数的零点，确定特征值和积分，以及解微分方程它们在实数集r 、 实数的开子集、r “的紧支集或是从单位区间到实数酞上的连续函数集( 用c 0 , 1 1 表示) 上执行计算 k w e i h m u c h 总结了a g r z e g o r c z y k 的思想，建立了二型有效性理论( t y p e 2 t h e o r yo fe f f e c t n i t y 简称t t e ) 在t t e 中，用定义在有限字母表上的无限字来表示 抽象空间中的元素用这种方法可以研究h il b e r t 和b a n a c h 空间中非线性演化算 子的可计算性并且，k w e i h r a u c h 和n i n gz h o n g 在r r 】限的框架下建立了索伯列 夫空间上的可计算性理论，并证明了波动方程，k d v 方程和薛定谔方程的解算子 是图灵可计算的，开创了研究非线性发展方程解算子可计算性的新的领域 1 2 本课题研究的基本内容和意义 非线性偏微分方程反映的是对自然规律的近似描述，求其解析近似解有重要 的实际意义变系数k d v b u r g e r s 方程描述的数学模型在研究水槽中产生的水波 问题中有很好的应用薛定谔方程是由奥地利物理学家薛定谔提出的量子力学中 的一个基本方程含时薛定谔方程是用来计算一个量子系统的波函数，怎样随着 时间演变薛定谔方程的解答，清楚地描述量子系统罩，量子尺寸立子的统计性量 子行为 物理学家认为：一个给定初值的物理方程，它所反映的某一系统随时间的变 化情况是可以被计算机以任意精度所描述的本文证明了变系数k d v - b u r g e r s 方 程的解算子和受迫非线性薛定谔方程的解算子是图灵可计算的因此，这些结论 不仅支持了物理学家的观点，而且还为机器求解偏微分方程扩充了应用范围迸 一步丰富和发展了微分方程解算子的可计算理论 4 江 苏大 学 硕 士 学位论 文 第二章预备知识 2 】图灵机和t t e 简介 图灵机是一种在理论计算机科学中广泛采用的抽象计算机，它是图灵在1 9 3 6 年提出的，用于精确描述算法的特征可用一个图灵机来计算其值的函数是可计 算函数，找不到图灵机来计算其值的函数是不可计算函数可以证明，存在一个 图灵机u ，它可以模拟任何其他的图灵机这样的图灵机u 称为通用图灵机通用图 灵机正是后来出现的存储指令的通用数字计算机的理论原型如下图所示，通用 图灵机通过下面几个条件给出： y 1 y k 图灵机计算y o = f m ( y l ，y k ) 作带k + l ，n 输出带0 ( 一种方式) ( 1 ) 输入输出字母表中存在b 芒，工作字母表r2 口) u ，有k 个输入带 ( 2 ) 机器在输出带0 ，输入带1 ，k ，工作带k + 1 ，上进行操作 ( 3 ) 存在如下的一些命令： 命令“h a l t ”表示：停机 命令“i ：l e f t ”表示：纸带i 的头指针向左移动一格 命令“i ：r i g h t 表示：纸带i 的头指针向右移动一格 5 江 苏 大 学 硕士 学 位论文 命令“i ：w r i t e ( a ) 表示：在纸带i 的头指针所指的格子内写入字母a ef 命令“i ：i f ( a ) ”表示：检测纸带i 的头指针所指的字母是否为a ( 4 ) 存在下面的限制： “i ：l e f t 和“i ：w f i t e ( a ) 不允许在输入带中进行；在输出带中只有命令 “0 ：w r i t e ( a ) ”和“0 ：r i g h t ”被允许这种限制保证了输入带为只读输入带，而输出 带为只写输出带 1 9 8 5 年，k w e i h r a u c h 提出了t t e 模型它是以 3 中可计算实函数概念和二型 图灵机为基础而建立的可计算模型，并且对它做了扩展： ( 1 ) 连续算子也可以加以考虑，不过这种连续被解释为一种基本的结构 ( 2 ) 通过表示，不仅可以在实数上，还可以在其它很多空间上研究有效性 ( 3 ) 有效容许表示的概念源于一些基本原理 ( 4 ) t t e 中也包含了计算复杂度的理论 t t e 的提出是为了研究能被物理设备所计算的实函数，但是它却面临两个困 难：其一，实数集合是不可数的，而且实数不能被自然数和有限词编码，所以只 能把它当作无限体来考虑其二，由物理定律得知，一个设备在任何时刻只能储 存有限多的信息，同样在任何有限长的时间内也只能转化有限多的输入和输出信 息t t e 是通过用有限体序列来逼近这一无限体来解决的粗略地说，t t e 首先定 义了。集合( 它是由生成的所有无限序列构成的集合) 以及。上的可计算性， 然后定义集合m 的一个满射j ：。专m ，最后通过。上的可计算性来定义m 的可计算性图灵可计算性是建立在”集上，下面我们将着重介绍表示空间上的 可计算函数和相关知识 2 2 基本概念 定义2 2 1 令表示充分大的有限字母表，表示上具有离散拓扑的所有 有限元素的集合，。表示上具有c a n t o r 拓扑的所有无限元素的集合， + ：= 以，其中五为空字符 表示各种关于自然数，有限及无限序列作用的函 数 定义2 2 2 和。上的标准拓扑结构 ( 1 ) 瓦：= 2 f = a 陋 称为上的离散拓扑 6 江 苏 大 学 硕士 学位论 文 ( 2 ) 乞：= a 。i ac _ e ) 称为。上的康托拓扑 定义2 2 3 表示空间 设是包括0 和1 的有限字母表，集合x 的表示是满射万：。斗工，如果 万( p ) = x ，那么，称p 是x 的万一名，( x ，万) 称为表示空问 定义2 2 4 可计算函数 设( x ，万) ，( y ，万) 是表示空间函数厂：x 专y 被称为( 万，万) - 可计算的，当且 仅当存在一个可计算函数伊：。一。使得f 。8 0 , ) = j 。缈( p ) 对所有 p d o m ( f 。万1 都成立 注：函数厂：m 。m 。一m o 的( 乃，圪，) 一可计算可以相应的定义，其 中形：啦一m ( a i 宰，缈) ) 引理2 2 5 每一个可计算函数厂：d lx l 靠一钿都是拓扑连续的，其中 a i 奉，国) 引理2 2 6 复合运算 设七，甩n ，墨，以，k ，艺，z ，e 。) ，令：墨鼍j ，厂： x k 专z ( i = l ，咒) ，它们均是可计算的函数则函数的复合 厂。( ，g 。) ：x 1 邑一z 是可计算的，当且仅当z = e o , 或者对所有的i ， i = e + 成立 定义2 2 7 前缀和子词 设比， ，w 和p 。如果x = “w + ，q = u v w 。，则u 分别为x 和g 的 前缀，记为u x ，甜g ；v 为x 和g 的子词，记为v x ，v g ：p 如_ p ( 0 ) 厶印 一1 ) ： a b ：= u pu 彳，p b ) ，其中a ，b e 或曰e 。 定义2 2 8 包函数z ：专为z ( q 口2 口。) ：= 1 1 0 a 1 0 a ，0 口。0 1 1 ，对任意的 咒e a r ，q ，口2 ，口。对于z ，x o ，x a ，p ，p o ，a ，。，i ，j 五且七1 ，定 s t ( x , ，x t ) _ z ( 五) z ( ) ，( p ，x ) = ( x ，p ) ：= t ( x ) p 功，( a ，见) ：= a ( 0 ) p 。( 0 ) a ( 1 ) a ( 1 ) 。，( x o ，而，) ：= z ( ) z ( 五) 出 7 江 苏 大 学 硕 士 学位论文 定义2 2 9 和o 中的可计算元 ( 1 ) 每个c o 都是可计算 ( 2 ) p e o , 是可计算的，当且仅当存在一个可计算串函数，：。一m ，满足 p = f ( 五) ( 3 ) 元组( m ，y ：，l ，儿) 是可计算的，当且仅当每一个元素y i 都是可计算的其 中，m 或者咒。 定义2 2 1 0 一般集合肘中的可计算元 ( 1 ) 设v ：寸m ，则任何z m 均称为v 一可计算 ( 2 ) i 发6 ：c 。一m ，贝l j x e m 称为万一可计算的，当且仅当万( p ) = x ，其 中p 是中的可计算元 引理2 2 1 1 任何一个可计算函数都把一个集合中的可计算元映射为另一个 集合中的可计算元 定义2 2 1 2 ( 万，万) 一实现 设万：。专m 和j ：。j m 是两个表示函数缈：。专m 称为 厂：m m 的( 万，艿) 一实现，如fo 占( p ) = 万。f p ( p ) ，其中pd o m ( 6 ) 且 6 ( p ) d o m ( f ) 定义2 2 1 3 ( 万，万) 一连续 设万：“专m 和j ：。一m 是两个表示函数厂是( 坑万7 ) 一连续的，当且 仅当厂存在连续的( 万，万) 一实现 定义2 2 1 4 坻：n 专。为自然数n 的表示，d q ：q 专。为有理数q 的表示 和p ：r 。为实数r 的表示 引理2 2 1 5 求值函数和类型转换 ( 1 ) 求值函数( ，x ) h 厂( x ) 是( 万一艿 ，万，万) 一可计算的 ( 2 ) 设( 谚，置) 是表示空间，其中0 i 七令f ：置五jk ，定义 f ( 五，以一。) ( ) ：= 厂( _ ，x k ) ，则厂是( 磊，哦，磊) 一可计算的，当且仅当f 是 8 江苏大 学 硕 士 学 位论文 ( 4 ，反小【反。磊】) 一可计算的 引理2 2 1 6 原始递归 设厂：y m 和y ：l ，专m 为两个表示，是n 的容许表示则有下面几 个命题成立： ( 1 ) 设，：m 寸m 足( 厂，y ) 一可计算的，无：+ x m x mj m 是( 以，厂， 厂，7 ) 一可计算的，其中i d v ：= + 专为恒等映射；定义g ：。x m 专m 如下： g ( 五，x ) = f ( x ) ，g ( a w ，x ) = 无( mg ( w ，x ) ，x ) ，其中x m ，a ，w e 则函数g 是( 谢，厂，y ) 一可计算的 ( 2 ) 设厂：m m 是( 厂，y ) 一可计算的，厂cn x m x mj m 是( ，y ， 厂，y ) 一可计算的定义g ：n x m m 如下：g ( o ，x ) = f ( x ) ，g ( n + l , x ) = 厂。( 刀，g n ，x ) ，x ) ，其d p x e m ，厅n 则函数g 是( ，7 , 7 ) 一可计算的 ( 3 ) 设h ：互m m 是( 厂，厂) 可计算的，定义函数h ：nx mj m 如下： m ( o ，x ) = x ，h ( n + l ，x ) = 乃。h ( ，z ，x ) ，( 也就是说日( ，z ，x ) ：= 矿( x ) ) ，则函数日是 ( o n ，y ，r ) - 可计算的 定义2 2 1 7 递归可枚举 设xcz c _ y ：= y l 匕x x y k ，其中七1 ，i ，m ) x 称为z 中的递归可 枚举的开集，如果x = d o m ( f ) oz ，其中厂：c yj 是一个可计算函数 定义2 2 1 8 光滑截断有理多项式 光滑截断有理多项式集p = p 。l p 是有理多项式，r ，七n ) ，展= 吆宰y ( x ) = 上( x y 沙( y ) 砂，z r ，这里五是区间 一云1 ，七+ 爿的特征函数，且满足 瓜厂( x ) 出= 1 2 3 常见空间的可计算结构 2 3 1 可计算度量空间 m = ( m ，d ，d ，) 称为可计算度量空间，如果( m ，d ) 是度量空间，d 是其可数 9 江 苏 大 学硕 士 学位论 文 稠子集，：( 拌 ) + - + d 是d 上容许记号，且 ( “，嵋砷i ( w ) d ( o o ( “) ， ( v ) ) o ) ，可以定 义一个表示如下：p ”( p ) 2x p = 撑“，撑，其中( u i ) 为递缩收敛于x 的 区间套序列简记p ：= ( 2 ) m = ( r ，d r ，q ，) 是一个可计算度量空间，亿：。专r 是其柯西表示通过段可 以定义r ”上的表示如下： ：= ( 成( a ) ，成( 磊) ) 可以得出： p h 喜院 2 3 4 可计算s ( 风) 空间 ( 1 ) s ( r ) ：= 矽c 。( r ) i ( v 口，n ) s u px o 蚓 o 。 ，畋( 矽，缈) ：= 2 “炒 -， 一0 等氅驯硎郇：刊删( 孙则s ( 峨啪完备的度量蛳 ( 2 ) 表示嗔：”专s ( r ) 定义如下：正( ) = ：氏( p ) = 矽， 留= 群“。撑l l l ，其中心d o m ( o s ) ，当h ( _ 。，) 时，有p 矽o ( x ) i 2 一 ( 3 ) ( s ( r ) ，d s ，p ，叱) 是可计算的度量空间，其中p = u 。p ，噬为p 的容许表 1 0 江 苏 大 学硕 士 学位论文 示记屯为该可计算度量空间的柯西表示 ( 4 ) 屯三4 一( 5 ) s ( r ) 空间的可计算性质： 设a , t r 和，仍厂，g s ( r ) 则有下列性质成立：函数( 口，缈) 专1 2 缈是 ( 虏，4 ) 一可计算的；( 仍f ) ji 缈( f ) l 是( 睡，p , p ) - 可计算性；( 矽，缈) 专矽+ 缈是 ( 瓯，瓯，坑) 一可计算的；( f ，g ) 一m a x ( f ，g ) 是( 嗔，哦，嗔) 一可计算的；( 矽，缈) 专缈是 ( 瓯，4 ，瓯) 一可计算的 n 次方s ( r ) hj ( r ) ，g 叶g “是( 壤，正) 可计算的，( 咒n ) 函数( 矽，f ) j 已( f ) 矽是( 皖，p ，皖) 一可计算的，其中f ，聊r ，矽s ( r ) ， ( f ) ( 孝) ：= e x p ( 一f 孝2i m t ) 函数( 少，厂) 一o ( 厂) ，勺( 厂) ( x ) ：= s ( x y ) 是( d 瓯，正) 一可计算的，其中 y r ，s ( 瓞) ( ，矽) 专矽( ) 是( ，壤，嗔) 一可计算的，其中j n ，矽s ( r ) ( 少，厂) 专q ( 厂) 是( p ，嗔，睡) 一可计算的，其中y r ，厂s ( r ) ， q ( ) ( x ) ：= s ( y x ) 函数日：c ( 爬，s ( 爬) ) r r 。s ( r ) ，是( 【p 专正】，p ，岛嗔) 一可计算的， 其中日( 邺，6 ) = r “( f p 恒等映射厶：d ( i r ) 。s ( r ) 是( 如，嗔) 一可计算的 恒等映射1 2 ：s ( r ) j c 。( r ) 是( 壤，瓯) 一可计算的 设u s ( r ) ，则s ( r ) 上的傅立叶变换f 及逆变换f - 1 分别定义如下： 凡( 孝) ：= 毋( 乡) = ( 1 芴) e x p ( - i x # ) “ ) a x ，f - i ( 凡( f ) ) = 甜( x ) 傅立叶变换f 及 逆变换f - 1 都是( 嗔，睡) 一可计算的 2 3 5 可计算r ( r ) 空间 ( 1 ) 设o p o o ，则( r ) ：= i 厂是复可测的，上i 厂i p 出 ) ，规定模为 江 苏 大 学 硕 士 学 位论 文 s l b = rif l p 出) “p ，当然可以诱导出距离略( 厂，g ) = i i 一g 怯 七 ( 2 ) ( r ( 低) ，略，盯，咋) 是一个可计算度量空间，其盯= ，i ，= c f n 呐，k n ， i = o q 为有理复数，口l 、包为有理数，a i b d ( 当a l x 包时n 嘶趣= 1 ，否则1 - i 确= 0 ) ， 为仃上的容许记号该可计算度量空间的柯西表示记为0 ( 3 ) r ( r ) 空间的可计算性质： m ( s ，g ) j 厂+ g 是( ，) 一可计算的，其中厂，g r ( 昶) ( 厂，g ，k ) - - - ) , f g 是( p 一户2 ，p ，) 一可计算的，其中k r ， 厂c ( r ，c ) 且骝i 厂( x ) f k ，g r ( r ) ( 口，6 ，厂) 专f 厂( f ) d f 是( p , p ， p o ，o ) 一可计算的，其中口，6 r ， 厂c ( r ，亭( r ) ) 2 3 6 可计算h 5 ( 酞) 空间 ( 1 ) 设s o ，则定义日5 ( r ) ：= ff r ( 酞) 且z ( f ) r ( r ) ) ，其中巧( ) ：= ( 1 + 141 2 ) “2 f ( ) ( 善) ，( 厂) 黼傅立叶变换规定模为i i 刘h ，：= | i ，i 【= ( ( 1 + i 手1 2 ) “2 夕( 亭) 2d 善了胆 ( 2 ) 当s 0 且为整数时，s o b o l e v 空间h 5 ( r ) 可以用另一种形式定义： h 3 ( r ) ：= 厂r ( r ) j 厂体) r ( r ) 对