可計算與可學習的實遞歸函數(shù).pdf

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

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

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

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

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

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