《Computable Lipschitz 歸約在隨機性及可計算性理論中的套用》是依託東南大學，由范贇擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：Computable Lipschitz 歸約在隨機性及可計算性理論中的套用
- 項目類別：青年科學基金項目
- 項目負責人：范贇
- 依託單位：東南大學
中文摘要,結題摘要,
中文摘要
Computable Lipschitz歸約（簡記為cl-歸約）是強Turing歸約，即給定變數,其用函式對應為增加某個常數[DHL01]。作為比較實數隨機性的歸約工具，cl-歸約由紐西蘭的Downey，美國的Hirschfieldt,Lafort等專家提出，其對應的cl-度內實數具有相同的隨機程度。所以，在cl-歸約下，度的結構，尤其是c.e.實數對應的度的結構,及利用cl-歸約下性質刻畫隨機實數對隨機性理論具重要意義。國內外隨機性理論研究方面諸多專家對以上的問題展開了豐富的研究，見文獻[BL06]等。另一方面，c.e.集合在cl-歸約（ibT歸約-特殊的cl-歸約）下對應的度的結構，其特殊性質，如非稠密等，促使可計算理論學者關注對cl-歸約下c.e.集合度結構的研究。本課題擬從以上兩方面來研究cl-歸約的性質。
結題摘要
本項目旨在研究在cl-歸約下可計算可枚舉（c.e.）集合度的結構和分析可計算可枚舉（c.e.）實數在cl-歸約下的性質來描述實數的隨機性。目前完成的主要結果如下：1. c.e.集合（實數）最大對是指在cl-歸約下其無共同上界。通過與專家Ambos-spies,丁德成， Wolfgang 等的合作，我們建立c.e.集合最大對與行列可計算（array computable）類, 弱真值歸約（wtt-）完備集, 圖靈歸約（T-）完備集等重要類的聯繫，並且進一步分析性質，如存在一個最大對，同時為最小對的c.e. 的cl-度，或存在一對非最大對且不具備最小的上界的c.e.的cl-度等等。2. ibT-歸約是特殊的cl-歸約，其用函式為恆等函式。通過與Ambos-spies, Bodewig 及Kräling 合作，我們得到c.e.集合的ibT-度和cl-度具有某個不同的度結構，從而從結構上區分ibT 和cl 兩種歸約。3. 我們引入一致非low_2類，通過cl-歸約下c.e.實數的性質進一步理解此集合類: 如果某c.e. 圖靈度是一致非low_2， 則對於任何不可計算的c.e.實數，此度中存在某c.e.實數使得兩者構成一個c.e.實數的最大對。 以上證明的方法具有創新性，可用於證明Barmpalias, Downey 及Greenberg （2008）中對行列可計算類刻畫的結論。 作為套用，我們證明了下列三個命題等價：（1）某c.e. 圖靈度是行列不可計算；（2）該度中存在一個c.e.實數，其不歸約與任何wtt-完備的c.e.實數；（3）該度中存在一個c.e.實數，其不歸約與任何複雜（complex）的c.e.實數。進一步，對於non-low_2類可通過cl-歸約下c.e.實數類的性質刻畫。4. Barmpalias，Day等證明了c.e.集合在ibT（cl）-歸約下非稠密。在分析其證明方法之下，我們推廣得到n-c.e集合在cl-歸約下非稠密，c.e. 實數在ibT-歸約下不稠密等結論。
