实数空间上的可判定性

《实数空间上的可判定性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中山大学硕士学位论文实数空间上的可判定性姓名：胡伟豪申请学位级别：硕士专业：计算机软件与理论指导教师：周青2003.5.20中文摘要实数空间上的可判定性专业：计算机软件与理论硕士生：胡伟豪指导教师：周青摘要本文回顾了经典的可计算性和可判定性及它们间的联系，介绍了近年来对可计算性在欧几里德空间上的扩充及可计算的实数、递归开／闭集、实变元函数等概念，指出了在实数空间上的可计算性概念被提出来之后，经典的可判定性概念在实数空间上的局限。本文提出了一个全新的关于在欧几里德空间上实变元谓词的可判定性的概念——“几乎可判定”。这个概念结合了在自然数上的可判定谓词

2、的定义与可计算性分析的思想，给出了一种判定实变元的谓词的能行的方法。为了证明几乎可判定概念的合理性，文章给出了一些实数空间上的常用的谓词的几乎可判定性，例如在两个实数、实数集或实变元函数之间的“=”、实数和实数集之间的“∈”、两个实数集之间的“c”等关系，都是几乎可判定的。最后，文章把研究的重点放在对几乎可判定与可计算性的关系上。通过对一些定理的证明，文章给出了从某些可判定的谓词构造出可计算实数、可计算实数集的方法，迸一步证明了几乎可判定的概念的合理性，并且将几乎可判定和可计算性分析结合成一个有机的整体。关键字：可判定性、几乎可判定、可计算性、可计

3、算性分析ABSTRACTDecidabilityinSpacesofRealNumbersMajor：ComputerSoftwareandTheoryName：WeihaoHnSupervisor：QingZhouInthispapertheclassicaldefinitionsofcomputabilityanddecidabilityandtherelationbetweenthemarereviewed．TheexpandeddefinitionsofcomputabilityofrealnumbersinEuclideanspaces，

4、realnumbersetsandfunctionsonEuclideanspacesarediscussed．Thelimitationsofclassicaldecidabilityonrealspacesarepointedout．Andbasedonthat，thedefinitionofalmostdecidablepredicatesofrealvariablesisgiven．Thisnotioncomesfromtheconceptofdecidabilityofnumbertheoreticalpredicatestogether

5、witlltheideaofeffectiveconvergenceincomputableanalysis．AsthedecidabilityinEuclideanspacesisalmostuntoucheduptotoday，wecomeuptothisareaforthefirsttime．Itisprovedthatsomecommonlyusedpredicateson啜”suchas“=”，“∈”and“呈”betweencomputablerealsandrecursiveopen／closedsetsarealmostdecida

6、ble，whichjustifiesourdefinitionofdecidabilityinrealspaces．Andrelationsbetweenalmostdecidabilityandcomputabilityofrealsandrecursivenessofsubsetsof豫”areconsidered．whichprovideabridgetoincludeourworksheretotheearlierliteratureoncomputableanalysis。Keywords：Decidability,AlmostDecid

7、ability,Computability,ComputableAnalysis第一章概述蘑(A

8、gorisms)也Ⅱq能行方法(E赡ctiv拳methods)能行过程(EfB∞tiveprocedures)，是一个相当古老的概念，其历史可以上溯到古希腊时代。蒋名的阿蒸米德辗转相除法秘奥拉欺蚝散绒戆法就是轰{弋算法靛鼹个杰出范镪。算法的勰本特征熄：·骈肖动作都严格按照事先给鬣的(有穷多条)规则进行；●每一步究竟按哪一条规则行动也完全是确定的——或喾由规则斑接确定，或者由规则和上一步的瓣果确定；●整个过程在露穷步内缕束。如果用～旬更通俗的话来说，所谓

9、算法就是一种死办法。利用算法解题并不错要特别的聪疆才智，只簧严格逾照章办事就行，茏论是谁来骰，其过程和结果都完全相同。自古