（应用数学专业论文）微分方程解算子和矩阵的图灵可计算性.pdf

江 苏 大 学 硕 士 学位论文 摘要 许多物理学家都认为：一个给定初值的物理方程，它所反映的某 一系统随时间的变化情况是可以被计算机以任意精度所描述的。因此， 研究偏微分方程解算子的可计算性有着重要的现实意义。 本文主要研究了组合k d v 方程以及四阶薛定谔方程解算子的可 计算性。首先，利用方程的守恒量或能量函数，研究其解的某些特殊 性质。然后，在s o b o l e v 空间上用傅立叶变换把微分方程转换成积分方 程。再利用解的性质、s c h w a r t z 函数的性质、压缩映象原理和t t e 理 论证明存在丁 0 ，使得相应的积分算子在0 f t 时是可计算的。最后， 通过构造可计算函数把解从区间 o ，t 延拓到整个实数空间上，从而 得到原微分方程的解算子有相同的可计算性。本文研究的结果为精确 计算组合k d v 方程以及四阶薛定谔方程的解提供了理论依据，推广了 数字计算机求解微分方程的应用领域。 本文还研究了实矩阵的图灵可计算性，给出了实矩阵的可计算性 定义和二种表示，并运用拓扑空间上的可计算性理论证明了这二种表 示是等价的。运用二型有效论作为可计算模型，证明了可计算实矩阵 的一系列运算结果仍是可计算的实矩阵。以此为基础可以进一步研究 矩阵函数的可计算性，建立矩阵空间的可计算性理论。 关键词：微分方程解算子，实矩阵，图灵机，可计算函数，二型有效 论，s o b o l e v 空间 江 苏 大 学 硕士 学 位论文 a b s t r a c t m a n yp h y s i c i s t sb e l i e v et h a t ：g i v e na ni n i t i a lv a l u ef o rt h ep h y s i c a l e q u a t i o n ，ac h a n g ei tr e f l e c t si nt h es y s t e mo v e rt i m ec a nb ed e s c r i b e dw i t h a n yp r e c i s i o nb yc o m p u t e r s t h e r e f o r e ，f i n d i n gt h ec o m p u t a b i l i t y o f s o l u t i o no p e r a t o r so fs o m ep a r t i a ld i f f e r e n t i a le q u a t i o n si sv e r yi m p o r t a n t a n dp r a c t i c a ls i g n i f i c a n t 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 ec o m b i n e dk d ve q u a t i o na n dt h ef o u r t h o r d e rs c h r s d i n g e re q u a t i o n f i r s t l y , w es t u d yt h ec e r t a i np o s i t i o no f t h e i rs o l u t i o n sb yt h ec o n s e r v a t i o n e q u a t i o n so rt h ee n e r g yf u n c t i o n s e c o n d l y , w ec h a n g et h ee q u a t i o n si n t o t h ee q u i v a l e n ti n t e g r a le q u a t i o n so ns o b o l e vs p a c eb yf o u r i e rt r a n s f o r m t h i r d l y , w ep r o v et h a tt h ei n t e g r a lo p e r a t o r sa r ec o m p u t a b l eb yu s eo ft h e c e r t a i np o s i t i o no ft h es o l u t i o n ，t h es c h w a r t zf u n c t i o n s ，c o n t r a c t i o n p r i n c i p l ea n dt t e f i n a l y , b yt h ec o m p u t a b l ef u n c t i o n sc o n s t r u c t e d ，w e e x t e n dt h es o l u t i o nf r o mt h ei n t e r n a lt ot h ee n t i r es p a c e t h e s er e s u l t sl a y t h et h e o r e t i c a lf o u n d a t i o nf o rc o m p u t i n gt h es o l u t i o no ft h ec o m b i n e dk d v e q u a t i o na n dt h ef o u r t h - o r d e rs c h r s d i n g e re q u a t i o ne x a c t l y a n de x t e n dt h e a p p l i c a t i o no fd i g i t a lc o m p u t e r s t os o l v ed i f f e r e n t i a le q u a t i o n s i na d d i t i o n ，t h et u r i n gc o m p u t a b i l i t yo ft h er e a lm a t r i xi ss t u d i e da n d t h ec o m p u t a b l ed e f i n i t i o no ft h er e a lm a t r i xa n dt w or e p r e s e n t a t i o n sa r e g i v e n ，a n dt h e np r o v et h e ya r ee q u i v a l e n t i ti sp r o v e dt h a ts o m ec a l c u l a t i o n r e s u l t so ft h ec o m p u t a b l er e a lm a t r i xr e m a i nc o m p u t a b l er e a lm a t r i xb y v i r t u eo ft y p e - 2t h e o r yo fe f f e c t i v i t y k e y w o r d s ：t u r i n gm a c h i n e ，r r e ，s o b o l e vs p a c e ，s o l u t i o n o p e r a t o ro f d 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 ef u n c t i o n ，r e a lm a t r i x 江苏大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 学位论文作者签名： 2 0 0 8 年1 2 月 保密口，在 年解密后适用本授权书。 不保密团。 趸，旆 i 1 日 指导教师签 2 0 0 8 年1 2 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： q 口出 爰r 岬 日期：2 0 0 8 年1 2 月1 7 日 江 苏 大 学 硕士 学位论 文 第一章绪论 1 1可计算理论的发展历史 自从2 0 世纪3 0 年代以来，图灵机、计算这些重要的概念在科学的天空中就 一直闪烁着无限的光彩。尤其是近年来量子计算机、生物计算机、d a n 计算等 领域的创新工作引起了世人的广泛关注。这一切的源头都来源于可计算性理论。 可计算性理论是计算机科学的理论基础之一，它是通过建立计算的数学模型( 例 如抽象计算机) ，精确区分哪些是可计算的，哪些是不可计算的。计算的过程就 是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确 化。算法概念精确化的途径很多，其中之是通过定义抽象计算机，把算法看作 抽象计算机的程序。通常把那些存在算法计算其值的函数叫作可计算函数。因此， 可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样 就可以讨论哪些函数是可计算的，哪些函数是不可计算的。 可计算性理论起源于对数学基础问题的研究。二十世纪3 0 年代初，k g o d e l 率先提出“原始递归函数”就是可计算函数。不久人们就发现了一个用多重递归 定义的函数不是原始递归函数。于是，数理逻辑学家又在原始递归函数的定义中 加了一个“极小 算子，由此定义了广义递归函数的概念。1 9 3 6 年，a t u r i n g 在著名文章 1 中提出要用可计算无穷二进n d , 数来表示可计算实数，并且把一 个问题的可计算性描述为在具有严格定义的理想计算机( 后人称之为图灵机) 上 的可解性。1 9 3 7 年，他又在 2 中指出可计算实数也可以等价地用具有有理端点 的区间套来表示。于是，产生了c h u r c h 论断：一个部分函数，c 一( 其中 是一个充分大的字母表，是由其生成的所有有限字符序列构成的集合) 在直 观意义上是可计算的当且仅当它能够为图灵机所计算。1 9 5 5 年，波兰逻辑学家 a g r z e g o r c z y k 在文章 3 中提出了可计算实函数的概念。它主要包括两个基本 特征( 1 ) 厂：【o ，l 】专瓜是可计算的当且仅当厂具有一致连续的模函数并且它把一 个可计算的序列映射为另一个可计算的序列，这已经由p o u r - e 1 和r i c h a r d s 推 广到了可计算b a n a c h 空间 4 。( 2 ) 单调可计算函数把有理区间映射为另一个有 江 苏 大 学硕 士 学 位论文 理区间，这成为区间分析 5 ，6 的可计算背景( 区间分析主要研究一些空间，例 如：实数空间上的可计算性 7 ，8 ，9 ，1 0 ，1 l ，1 2 ) 。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 i n ，i m u n r o ，l b l u m ，m s h u l ，s s m a l e ， f p p r e p a r a t a ，m i s h a m o s ，j f t r a u b ，g w w a s i l k o w s k i ，h w o z n i a k o w s k i ， e n o v a k 等人在文献 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 0 用无限近似来表示。a s t r o e l s t r a d v a nd a l e n 2 1 ， b i s h o p 2 2 ，c e i t i n 2 3 ，h a u c k 2 4 ，k o 2 5 等人也建立了一些可计算模型， 但是看似直观的定义却彼此不等价，因此这些工作并没有得到大多数数学家的承 认。 1 9 8 5 年至今，l ( w e i h r a u c h 总结了a g r z e g o r c z y k 的思想，以二型图灵机为 计算模型，建立了二型有效论( 英文简称t t e ) 2 6 ，4 2 ，4 3 。在t t e 中，用定 义在有限字母表上的无限字来表示抽象空间中的元素。用这种方法可以研究 h i l b e r t 和b a n a c h 空间中非线性演化算子的可计算性。kw e i h r a u c h 和n i n g z h o n g 在r 】陋的框架下建立了索伯列夫空间上的可计算性理论，并证明了波动 方程和k d v 方程的解算子是图灵可计算的，开创了研究非线性发展方程解算子 可计算性的先河。 1 2 图灵机和t t e 简介 图灵机是英国数学家a t u r i n g 提出的一种抽象计算模型，用来精确定义可 计算函数。图灵机由一个控制器、一条可无限延伸的带子和一个在带子上左右移 动的读写头组成。可用一个图灵机来计算其值的函数是可计算函数，找不到图灵 机来计算其值的函数是不可计算函数。这个在概念上如此简单的机器，理论上却 可以计算任何直观可计算的函数。图灵机作为计算机的理论模型，在有关计算理 论和计算复杂性的研究方面得到广泛的应用。 2 江 苏 大 学 硕士 学位论 文 人们还研究了图灵机的各种变形，如非确定的图灵机、多道图灵机、多带图 灵机、多维图灵机、多头图灵机和带外部信息源的图灵机等。除极个别情形外， 这些变形并未扩展图灵机的计算能力，它们计算的函数类与基本图灵机是相同 的，但对研究不同类型的问题提供了方便的理论模型。例如，多带图灵机是研究 计算复杂性理论的重要计算模型。人们还在图灵机的基础上提出了不同程度地近 似于现代计算机的抽象机器，如具有随机访问存储器的程序机器等。二型图灵机 也是图灵机的一种变形，它有几个条件给出： y o 带。 b k 州 输出带0 ( 一种方式) 图灵机计算y o = f m ( y b - - 9 y o ( 1 ) 输入输出字母表中存在曰萑，工作字母表r b ) u e ，有后个输入 ( 2 ) 机器在输出带0 ，输入带1 ，k ，工作带k + 1 ，上进行操作。 ( 3 ) 存在如下的一些命令： 命令“h a l t ”表示：停机。 命令“i ：l e f t 表示：纸带i 的头指针向左移动一格。 命令“i ：r i g h t 表示：纸带i 的头指针向右移动一格。 命妒i ：w r i t e ( a ) 表示：在纸带i 的头指针所指的格子内写入字母a ef 。 命令“i ：i f ( a ) 表示：检测纸带i 的头指针所指的字母是否为a 。 ( 4 ) 存在下面的限制： 3 江 苏大 学 硕 士 学 位论 文 “i ：l e f t 和“i ：w r i t e ( a ) ”不允许在输入带中进行；在输出带中只有命令 “0 ：w r i t e ( a ) ”和“o ：r i g h t ”被允许。这种限制保证了输入带为只读输入带， 而输出带为只写输出带。 下面介绍t t e 。它是以 3 中可计算实函数概念和二型图灵机为基础而建立 的可计算模型。t t e 的提出是为了研究能被物理设备所计算的实函数，但是它 却面临两个困难：其一，实数集合是不可数的，而且实数不能被自然数和有限词 编码，所以只能把它当作无限体来考虑。其二，由物理定律得知，一个设备在任 何时刻只能储存有限多的信息，同样在任何有限长的时间内也只能转化有限多的 输入和输出信息。t t e 是通过用有限体序列来逼近这一无限体来解决的。粗略地 说，t t e 首先定义了。集合( 它是由生成的所有无限序列构成的集合) 以及。 上的可计算性，然后定义集合m 的一个满射万：。一m ，最后通过。上的可计 算性来定义m 的可计算性。 1 3 本课题研究的主要内容和意义 可计算性理论中的基本思想、概念和方法，被广泛应用于计算机科学的各个 领域。建立数学模型的方法在计算机科学中被广泛采用。递归的思想被用于程序 设计，产生了递归过程和递归数据结构，也影响了计算机的体系结构。 i cw e i h r a u c h 和n z h o n g 研究了k d v 方程解和二阶薛定谔方程解算子的可 计算性 3 6 ，3 8 ，4 0 ，5 0 ，5 1 。本文推广了他们的结果，得到了组合k d v 方程和 带有高阶色散项的薛定谔方程的解算子也是可计算的。许多物理学家都认为：一 个给定初值的物理方程，它所反映的某一系统随时间的变化情况是可以被计算机 以任意精度所描述的。因此，这些结论不仅支持了物理学家的观点，而且还为机 器求解偏微分方程扩充了应用范围。 本文还研究了实矩阵的图灵可计算性，运用二型有效论作为可计算模型，证 明了可计算实矩阵的一系列运算结果仍是可计算的实矩阵。这是对建立矩阵空间 的可计算性理论的一种尝试。 4 江 苏 大 学硕 士 学位论 文 2 1 基本概念 第二章预备知识 弟一早 珙亩刘状 定义2 1 1 令表示充分大的有限字母表，幸表示上具有离散拓扑的所 有有限兀素的集合，。表不上具有c a n t o r 拓扑的所有无限兀素的集合， + ： 五 ，其中兄为空字符。 表示各种关于自然数，有限及无限序列作用 的函数。 引理2 1 2 复合运算 设七，刀n ，五，也，v l ，艺，z ，。) ，令：c x l x 。j l ；= ，厂： x k 专z ( 扛1 ，n ) ，它们均是可计算的函数。则函数的复合f 。( g l ，g 。) ：冬z l x ljz 是可计算的，当且仅当z = 。或者对所有的f ，成立= 。 定义2 1 3 前缀和子词 设u ，v ，w + 和p 。o o = 果x = u v we ，q = “馏。，则甜分别为x 和q 的 前缀，记为甜c _ x ，甜q ；1 ，为x 和g 的子词，记为，qx ，v iq ；儿：= p ( o ) p ( n 一1 ) ；a s ：= u p lu 彳，p b ，其中a + ，b + 或b 。 定义2 1 4 包函数t ：e j 为l ( a l 口2 a n ) ：= l l o a l o a ，0 a n 0 1 1 ，对任意 玎n ，a l , 口2 ，a 。对于x ，x o ，而，p ，p o ，a ，。，i ，j ，k nr k 1 ， 定义 ( _ ，) ：= z ( _ ) z ( 诈) ( p ，x ) = ( x ，p ) ：= z ( x ) p 。 ( p t ，仇) - p l ( 0 ) 仇( o ) a ( 1 ) 仇( 1 ) 缈 ( x o ，x t ，) _ z ( ) z ( 而) 。 定义2 1 5 和m 上的标准拓扑结构 5 江 苏 大 学 硕士 学 位论文 ( 1 ) l ：= 2 = 么l 彳) 称为+ 上的离散拓扑。 ( 2 ) ：= 彳。lac _ z ) 称为。上的康托拓扑。 引理2 1 6 每一个可计算函数厂：q 专嘞都是拓扑连续的，其 中呸 宰，国) 。 定义2 1 7 和。中的可计算元 ( 1 ) 每个缈都是可计算。 ( 2 ) p 。是可计算的，当且仅当存在一个可计算串函数厂：j 。，满足 p = ，( 力。 ( 3 ) 元组( 乃，儿，此) 是可计算的，当且仅当每一个元素m 都是可计算的。 其中，y i + 或者y ，。 定义2 1 8 记号，表示 4 2 , 4 3 1 和表示空间 ( 1 ) 集合m 上的记号定义为一个满射u ：冬_ m 。 ( 2 ) 集合m 上的表示定义为一个满射万c 一m 。称( 正肘) 为表示空间。 定义2 1 9 一般集合m 中的可计算元 ( 1 ) 设d c + 一m ，则任何x m 均称为d 一可计算。 ( 2 ) 设万：。一m ，则x m 称为万一可计算的，当且仅当8 ( p ) = x ，其中 p 是。中的可计算元。 引理2 1 1 0 任何一个可计算函数都把一个集合中的可计算元映射为另一 个集合中的可计算元。 定义2 1 1 1 ( 万，万。) 一实现 设艿：。一m 和万：。_ m 是两个表示。函数矽：。专。称为 m 斗m 的( 万，艿) 一实现，如f o 万( p ) = 艿。4 ( p ) ，其中p 面历( 万) 且 8 ( p ) d o m ( f ) 。 6 江 苏 大 学 硕 士 学位论 文 定义2 1 1 2 ( 8 , 8 ) 一连续和( 万，8 。) 一可计算 设万：。j m 和万：口一m 。是两个表示。函数，是( 万，万7 ) 连续的，当 且仅当厂存在连续的( 万，万) 实现。如果存在一个机器当输入给定的万码时，能计 算出厂的万码。函数厂：mj m 7 是( 万，8 ) 可计算的。 注：函数厂：m 。m 。jm 。的( 乃，段，) 一可计算( 连续) 可以相应的 定义，其中形c 嘶_ m ( q ，缈) ) 。 定义2 1 1 3 表示的连续( 可计算) 等价 设万c 搿一m 和万c 。一m 是两个任意给定的表示。如果是连续( 可 计算) ，则记为万 d 是d 上容许记号，且 ( “， ，嵋砷1 ( w ) o ，i ，n ) ，其中r 嗍= ， c ( r ) if b ( a ，) 一- - - ( c l ，q + 2 一) ( 乞，乞+ 2 7 ) ) ；( r ) 是( r ) 的容许记号；拓扑 乇( r ) 以( r ) 作为子基的。记既是由该可计算拓扑空间诱导的表示。 ( 3 ) 根据定义2 1 1 3 可以得到c ( r ) 上的又一个表示 p j 。 ( 4 ) 通过定义( 岛) 。一c ( r ) g ：( v 尼 o ) ( 1 i 岛一g 岫。专取0 ，可以证明 江 苏大学硕 士 学 位论文 p 哼 兰名( r ) 量屯，而且此三种表示都是容许的。 ( 5 ) c ( r ) 空间的可计算性质： 函数口j 六，正( x ) _ 玎是( p ，良( r ) ) 一可计算的，其中口r 。 函数( g ) 专厂+ g ，( 厂，g ) j 厂g ，( f ，g ) - - m a x ( f ，g ) ，( f ，g ) j m i n ( f ，g ) ，( 厂，g ) - - f 。g 都是( s c ( r ) ，名( r ) ，露( r ) ) 一可计算的，其中, g c ( r ) a 函数( y ，) 一乃( 厂) 是( p ，龟( r ) ，& ( r ) ) 一可计算的，其中勺( 厂) ( x ) ：= f ( x y ) ，y r ，f c ( r ) 。 2 2 6 可计算r ( r ) 空间m ( 1 ) 设o p ，则( r ) - 厂i 传复可测的，r ifl ，出 o 。 ，规定模为 厂k = ri 厂r 出) ，当然可以诱导出距离( g ) = i l 厂一g k 。 ( 2 ) ( r ( r ) ，毋) 是一个可计算度量空间， 其 仃= 厂i 厂= 6 1 7 q 岛，k n ，q 为有理复数，q 、勿为有理数，a j 岛) ( 当嘭 z 岛 时柏= 1 ，否则兀柏= 0 ) ，呦为仃上的容许记号。该可计算度量空间的柯西表 示记为。 ( 3 ) r ( r ) 空间的可计算性质： ( 厂，g ) 一厂+ g 是( ，屯，如) 一可计算的，其中, g r ( 瓞) 。 ( ，g ，k ) - - 争f g 是( j 2 ，岛) 一可计算的，其中ke r ， 厂c ( r ，c ) n s u pf ( x ) l k ，g r ( 1 r ) 。 一 ( 口，6 ，f ) - - , r 厂( f ) d f 是( 岛仍 p 专 ，) 一可计算的，其中口，b r f e c ( i r ，r ( r ) ) 。 1 0 生茎垄堂堡主堂堡垒墨一 - _ _ _ _ _ _ - _ _ _ - _ _ - _ _ _ - _ _ _ _ l - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ i _ _ _ _ _ 一。 2 2 7 可计算日5 ( r ) 空间 ( 1 ) 设s o ，则定义日5 ( r ) 一 厂i 厂r ( r ) 且t ( 厂) r ( r ) ) ，其中t ( 厂) ：= ( 1 + l 孝1 2 y 彪f ( 厂) ( 孝) ，f ( 厂) 椭傅立叶变换。规定模为 i l o l h ，：“i 【：( ( + i 乡1 2 ) “2 夕( 孝) 2 d 孝 l 坦。 ( 2 ) 当s o 且为整数时，s o b o l e v 空间h 5 ( r ) 可以用另一种形式定义： h 3 ( r ) _ 厂r ( r ) i 厂) r ( r ) 对所有的o k s 成立) 。 规定模为i i 厂i l ：( 1 1 f 1 1 , + i i f i e + + i i f j i e ) l 坨。( 注：易证厂i e 三i ifi i , ) ( 3 ) 定义h 5 ( r ) 上的表示露，：。专日5 ( r ) 如下： 露，( 口) ：= 巧1 。( g ) ，q d o m ( 3 n ，) ，则露，是容许的表示，而且露，如。 ( 4 ) 定义h 5 ( r ) 上的表示筇：。一日5 ( r ) 如下：蓐( p ) = 厂，其中p = p f 面m ( 壤) 且i i 坑( p ，) 一s 1 1 日， 1 2 ，其中壤为2 2 1 1 可计算 s ( r ) 空间上的一个表示。 ( 5 ) p _ 露， 三巧1 。 p 专露 ，。三乐。 2 2 8 可i h - l i c 。( r ) 空间 ( 1 ) 设c 。( r ) ：= 厂if ：r - - * c ，其中f 是无穷次可微分的复值函数) ， 嘶，g ) 净。砉。等戋州k m c 。( r ) 定义如下： 瓯 - 厂( w ) 眨( r ) ( 乃) = f 。 ( 3 ) 可计算拓扑空间( c 。( r ) ，气，吒，旷) 定义如下：亿是由d 。生成的拓扑， 1 1 江 苏 大 学 硕士 学位论文 吒：= a ( j a b c d ) j n ，口，be q ，c ，deq 2a b ，c d ) ，( 当c l 面，c 2 c 。( r ) 是一个函数，则下面三个 命题是等价的： ( a ) f 是( 艿，瓯) 一可计算的。 ( b ) 函数( 口，x ) 哼( f ( 口) ) u ( x ) 是( 蠡，岛p 2 ) 一可计算的。 ( c ) ( 口，j ) j ( f ( 口) ) 7 是( 占，瓦) 一可计算的。 2 2 9 可计算c f ( r ) 空间 ( 1 ) 凹( r ) ：= 厂c 。( r ) is u p p ( 厂) 【- k ，后】) ( k 1 ) 江 苏 大 学 硕士 学 位论文 ( 2 ) 可计算度量空间( c ( r ) ，喀，矿，睇) 定义如下：首先定义函数y ( x ) 如下： 当h 1 时，( x ) = 口e x p ( f ；否则厂( x ) = 。( 其中口满足r i r ( x ) a x = 1 ) 。令 以( x ) - - 3 2 肿1 y ( 3 2 肿1 x ) 。记p 。= 圪幸( p 薪) l 刀n ，p p ) ， 其中z 为 一岔+ ，忌一 爿上的特征函数。令睇( 秒1 w ) 靠卑( 。p ( w ) z ) ，则它是矿上 的一个记号。这个空间上的柯西表示记为掣。 2 2 10 可计算d ( 酞) 空间 ( 1 ) 记d ( r ) = u 捌g ( r ) ；定义磊：毋jd ( r ) 如下：如( o l p ) ：- - 8 。( p ) ， 其中面聊( 如) _ o l p l k n ，允( p ) g ( r ) ；f g 义- - + 。如下：( 唬) 。专。痧存 在七n 使得矽，庇，c f ( r ) ，而且( 破lj 。矽。则( d ( r ) ，专d ) 是一个极限空 间，如为其上的容许表示。 ( 2 ) d ( r ) 空间的可计算性质： 函数( f ，g ) jf + g ，( 厂，g ) jf - g ，( f ，g ) - - - ) m a x ( f ，g ) 都是( 如， 如) 一可计算的，其中，g d ( 砷。 m 娄j l ；( y ，厂) 专乃( 厂) ，o ( 厂) ( x ) - 厂( x y ) 是( 岛如，如) 一可计算的，其中 y r ，d ( i r ) 。 ( 矽，歹) 斗痧是( 如，易) 一可计算的，其中矽ed ( 哟，j n 。 ( 六g ) 斗f g 是( 瓦，磊) 一可计算的，其中，c ”( 酞) ，g d ( r ) 。 足：寸r ( 矽) 是( 如，) 一可计算的，其中r ( 矽) ( x ) _ 矿( 一x ) ，痧d ( 酞) 。 一要矽( 功出是( 如，矿) 一可计算的，其中d ( r ) 。 江 苏大 学 硕 士 学 位论文 2 2 1 1 可计算s ( r ) 空间 ( 1 ) s ( r ) 一扯c ”( r ) f ( 眠n ) 哿桫f o o ) 硼纠一 蠢。2 加嚣皂其中| 例l 广翟p 矿k ) l 州s ( 叫为 完备的度量空间。 ( 2 ) 表示点。一s ( 酞) 定义如下：嗔( ) = 黔瓯( p ) = 矽， 9 2 孝舞，其中q 面所( ) ，当h 昧( 畋“胪) 时，有p 矽0 z ) 1 - 0 有 妒( ，f ) 忙q ( “) ，( o f 丁) ( 3 3 ) 其中“是初值问题( 1 ) 的解。 证明：由引理3 1 1 可知：不等式( 3 3 ) 对s = 1 成立。 不妨设x , j - 任意整数s s 不等式( 3 3 ) 仍成立。对方程( 3 1 ) 关于x 求导，可得 f “；力+ “二= 叫 叱) 一叫( h 2 u ，) l“o ( x , o ) = 缈o ( x ) 由于 磁c “。，= 言( ；) u “) h 。一。= 霎( ；) u “) 甜。一。+ c s + d 比。) “，+ ”。“) “ 联( 甜2 虬) = 窆( ；) ( “2 ) 门甜( 州+ 1 ) ：si ，s ，j ( 伽甜( 川 ( 叫+ 1 ) = ( ；) 窆( ? p o 扰d 叫却p + 1 + ( ；o ”p 一畋+ 材2 “o “+ 2 ( s + 1 ) “畋甜o + s 甜( 川) u x ? d x + 2 s “甜“。+ s s - 2 ( ，u ( 州 1 7 江苏大 学 硕 士 学 位论 文 瓦d ( “) 2 出= _ 2 工“竺甜出一2 工联( 甜蚝) “出一2 工联( “2 畋) “出 = 2 k “z 比( - k ( s ) 西一2 芝f ： p u + 1 v 一。扩k 一2 ( s + 1 ) 如2 u x 出 j = l j - - 2f u ( s + i ) u u ( s ) d x - 4 ( s + 1 ) p 叱 s ) 2d x 一2 s p p 1 虬“曲d x 4 s p u ( s - 1 ) u x 。u ( s ) 出一2 莩( ； p 扩一k 扩) 出 一2 蓑( ；) 考( ? ) p ( i ) u ( j - i ) u ( s - j + 1 ) u ( s ) 出一2 s 著s - 2 ( ；一1 ) p 一) 出 = a + b + c 其中 a = 一2 丘u 2 u ( s + i ) u ( s ) 出一2 , - 2 i f s fl p ( j + i ) u ( t - j ) u ( s ) 出一2 0 + 1 ) 如s ) 2 u x 出一2 p 州) 绷。出 j = l j b ：_ 4 ( s + 1 ) 甜以u ) 2 出一2 sl “( “) u x u x u 。) d x 一4 s 【，“( 州”。) d x c = 一2 善s - 2 ( ；) 上w 卅蚝依一2 鬈( ；) 喜( ? ) p ( 0 u ( - o u ( , - j + o u ( , ) 出 _ 2 s 量( ；一一) p “( 州_ 1 ) “出 又 么( 2 s + ) i i 甜，i i 。0 “( j 1 2 0 材( 5 一i i 。0 甜( j + l 0i i “( s 0 b 2 ( 2 s + 1 ) 伸州妒，+ 4 s ( + i l u x l l ) i l u 。1 1 ，1 1 2 + 2 s u x + u x x ) 2 0 “o 。1 0 l i 甜o 0 + 4 s ( 0 甜i i + i u x ) i i “。0 l i “p d 0 l i 甜o l i 由于 舟忙 ld 2 ”| l - d t( ”) l | ) 2 = 1d 2 ”j j - d t耻恤钎 翻 2 ( 删嘶卅咖| i i ) i 舭o + s q 。( 0 缈札一：) l l 缈札一。q ( 0 缈0 。) 0 缈l i ： 江 苏大 学 硕 士 学位论 文 翻 2 ( 4 川咖i i + c , ( 1 l d ) 慨i ii i 删伊i i ) m z ) 2 i i i i 同理可得 c + 3 j ( + c l ( ) 。+ c 2 ( 。) ：2q 一1 ( 恻l ) 1 1 缈1 1 “ 2 0 ，一2 i = 1( ：) ( 口1 ( 1 i d 加忆+ c ；( 1 i d h ) l l 伊l i ，) ( c , ( 1 l 1 1 ) l l d 。+ c ：( 1 l p l l 。) 1 1 1 1 ：) g 一忉i i 州一。) 物i i 纠+ 芝j = 2 ( ；) 圭t = o ( 州q 刊( 物i i 川) 忪 j - i + l 1 - 呼l 缈i i 一，) 忪i i 一) ( 譬1 ( ，) m + q ( “) 1 缈1 1 ，) 簟川( 1 1 缈1 1 叫) 1 1 伊1 叫+ 。 j 一2 + 2 s y j 一 1 = 1( ( 1 ( f ) l + 。+ q ( h ) ，) c ：( 1 l 伊l l 。) ：【笮扣1 ( 1 1 缈1 1 州一：) 州一。+ q ( 1 1 缈1 1 州一。) 1 缈1 1 州】 用g r o n w a l l 不等式0 f t b ) p o 妒) ( ，0 ) l i + 踹券 其中 p 州l p _ e a ( i m l - , ) r1 + b ( 1 l 缈l l “) ) ， a ( r ) = 2 ( s + 1 ) 【c l ( ，) ，+ c 2 ( r ) ，】+ ( 4 s + 1 ) 【，+ c l ( r ) ，+ c 2 ( r ) r 1 2 + 1 s - 2 6 ( r ) = s q 。1 ( r ) ，c ；( r ) + + s - 2 j = 2( ；p 砸) 厂+ 掣+ l ( ，) r 麟l ( r ) ( 凹1 ( ，) + q ( ，) ) ( c l ( r ) + c 2 ( ，) ) g 一( ，) ，3 j 一2 + s i = 1 ( ，) + 群一( r ) ) ( 辞1 ( ，) + q ( ，) ) 算川( ，) ，3 ( ，s - 1 ) ( 凹1 ( ，) + q ( ，) ) ( c 2 ( ，) + 辞( 厂) ) g 一一( ，) ，3 + 3 s ，+ q ( ，- ) r + 吃( r ) ，】2 露一1 ( ，) ，- 令g ( ，) ：= p 小丁( 1 + 6 ( ，) ) ， 则l i u o ) ( ，) 忙g ( 恻l ) 恻l 。 1 9 d +一 q v 八v ，枷 、l，卜u m m + 江 苏 大 学 硕 士 学位论 文 由于辞，碍q 。1 是可计算函数，容易推得q 也是可计算函数。口 定理3 1 3 存在一个可计算函数e ：n xrxr r ，满足 s u p i l u ( x ，t ) 峪e y 3 ( 1 1 ) ( 3 4 ) 其中：s o 为整数；恻i ，为缈在日5 ( r ) 上的模；u ( x ，t ) 为初值问题( 3 1 ) 的解。 证明：设= 1 + 辞+ 辞+ + q s ，易证d ( s ，t ，) ：= 叫s ，( ，) 是可计算的，由 于( ，) 叱 ( 1 + 辞( 缈) + + c ；( 1 l 缈l l 一。) ) 2 】l 2i i 伊i l 群( | i 伊l l ) l l 妒m 若 薛( y ) ：= 群( j ，) y ，由引理3 1 2 可得，当缈s ( r ) 时不等式( 3 3 ) 成立。下面 证伊日s ( r ) ，命题也成立。由于s ( r ) 在日s ( 酞) 空间中是稠的，不妨设 纯】函 是s c h w a r t z 空间的函数列，且以日s ( r ) 空间上的范数收敛到缈。如果将初值问 题( 3 1 ) 中缈换为绲时，对应的解为( ，t ) ，ni l ( ，r ) i i - 露( | | 缈1 1 ) 对所有的 0 r t 和所有k n 成立，又因为饩h s ( r ) ，且! 咖s u pi l 依一缈他一o ，所以 ”o 盈r l 。i m ，。s