可計(jì)算與可學(xué)習(xí)的實(shí)遞歸函數(shù).pdf

1、在數(shù)學(xué)與計(jì)算機(jī)科學(xué)領(lǐng)域中，離散可計(jì)算性和計(jì)算復(fù)雜性理論起著至關(guān)重要的角色．它引領(lǐng)人們?nèi)グl(fā)現(xiàn)，理解，分類各種各樣的可判定以及不可判定問題，開辟了現(xiàn)代計(jì)算機(jī)科學(xué)的新時(shí)代，深深地影響著人們世界觀．然而，物理和工程中提出的絕大多數(shù)數(shù)學(xué)模型，其基礎(chǔ)概念仍然是實(shí)數(shù)．因此，我們有必要在實(shí)數(shù)或者更一般的連續(xù)數(shù)據(jù)結(jié)構(gòu)上建立可計(jì)算性和計(jì)算復(fù)雜性理論．近年來，人們在這個(gè)領(lǐng)域取得了相當(dāng)大的進(jìn)步．遺憾的是，與離散情形相比較，連續(xù)計(jì)算理論還處于發(fā)展的初級階段．可以

2、說，在連續(xù)計(jì)算理論領(lǐng)域中，有許多重要基礎(chǔ)問題沒有解決，大量的難題等待著發(fā)現(xiàn)．當(dāng)前，基于生物和物理模型而提出的新計(jì)算方案．例如，DNA計(jì)算，量子計(jì)算．對效率問題提出了根本性的新思路，并向Turing屏障的假說提出挑戰(zhàn)． 突破Turing屏障，就要找到超圖靈機(jī)的數(shù)學(xué)模型．Gold提出的極限遞歸理論，就是一個(gè)成功的嘗試．拓廣了算法學(xué)習(xí)理論．極限遞歸理論中的判定問題本質(zhì)上是用一個(gè)算法，有限時(shí)間里已經(jīng)得到結(jié)果，但不能知道這個(gè)結(jié)果在何時(shí)取得

3、．因此我們認(rèn)為是無限長的時(shí)間后，最終獲得結(jié)果。這個(gè)過程類似于人類學(xué)習(xí)過程．計(jì)算學(xué)習(xí)理論廣泛應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域，例如，證明檢測，程序驗(yàn)證，算法學(xué)習(xí)理論等領(lǐng)域． 本文所論及的可學(xué)習(xí)概念主要指在計(jì)算的過程中，運(yùn)用了極限遞歸函數(shù)(或函子)． 另外，人們提出的連續(xù)計(jì)算模型，對時(shí)間而言，仍然是離散的．例如，BSS計(jì)算模型，遞歸分析中的可計(jì)算實(shí)函數(shù)的計(jì)算模型本質(zhì)上是帶外息的多帶圖靈機(jī)．C,Moore首次將自然數(shù)集合Ⅳ上的遞歸理論拓展

4、到實(shí)數(shù)集合R上．拓展的方法是，在遞歸函數(shù)的定義中，用連續(xù)的算子代替離散算子．也就是說，用微分遞歸算子代替離散的本原遞歸算子，用連續(xù)μ-遞歸算子代替離散的極小算子． 近年來，隨著超圖靈機(jī)計(jì)算模型的廣泛研究，模擬計(jì)算理論和計(jì)算學(xué)習(xí)理論再次引起了人們的極大興趣．刻畫各種計(jì)算模型之間的關(guān)系仍然是理論計(jì)算科學(xué)的研究熱點(diǎn)之一．本文作者在導(dǎo)師李祥教授和日本京都產(chǎn)業(yè)大學(xué)MarikoYasugi教授的指導(dǎo)和幫助下，從事此課題的研究工作，給出實(shí)遞歸

5、函數(shù)與可計(jì)算實(shí)函數(shù)和可學(xué)習(xí)實(shí)函數(shù)之間的關(guān)系． 具體的說，本文的研究工作主要在如下下幾個(gè)方面．·用圖靈計(jì)算復(fù)雜性理論刻畫實(shí)遞歸函數(shù)的一個(gè)子類一本原實(shí)遞歸函數(shù)的初等可計(jì)算性． 在實(shí)遞歸函數(shù)的可計(jì)算性方面，我們證明了本原實(shí)遞歸函數(shù)在緊區(qū)間上的初等可計(jì)算性，也就是說，該類函數(shù)的計(jì)算復(fù)雜性可以歸結(jié)到標(biāo)準(zhǔn)的初等計(jì)算復(fù)雜類中．這加強(qiáng)了A.Kawamura的關(guān)于本原實(shí)遞歸函數(shù)的可計(jì)算性結(jié)論． ·基于極限遞歸函數(shù)理論刻畫實(shí)遞歸函數(shù)

6、的一個(gè)子類的可學(xué)習(xí)性．在實(shí)遞歸函數(shù)的可學(xué)習(xí)性方面，可學(xué)習(xí)實(shí)函數(shù)賦予不連續(xù)函數(shù)的學(xué)習(xí)性質(zhì)．文中證明了M．Yasugi提出的Para-可計(jì)算函數(shù)類與實(shí)遞歸函數(shù)譜系M<,1>中的不連續(xù)函數(shù)的關(guān)系． ·基于極限遞歸函數(shù)理論刻畫遞歸實(shí)數(shù)的一個(gè)子類的可學(xué)習(xí)性．用極限遞歸函數(shù)替代遞歸函數(shù)，定義了可學(xué)習(xí)實(shí)數(shù)，證明了可學(xué)習(xí)實(shí)數(shù)與其它實(shí)數(shù)譜系的關(guān)系． ·基于模擬計(jì)算模型和無限極限，提出新的實(shí)遞歸函數(shù)的定義．本文中，基于GPAC可計(jì)算函數(shù)和取