《可計算性理論及其在算法資訊理論中的套用》是依託南京大學，由喻良擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：可計算性理論及其在算法資訊理論中的套用
- 項目類別：青年科學基金項目
- 項目負責人：喻良
- 依託單位：南京大學
- 批准號：10701041
- 申請代碼：A0101
- 負責人職稱：教授
- 研究期限：2008-01-01 至 2010-12-31
- 支持經費：16（萬元）
項目摘要
我們研究可計算性理論（又稱遞歸論）及其在算法資訊理論中的套用。尤其是關於隨機性的刻畫問題。這是可計算性理論（甚至整個數學）的一個熱門領域。2006年國際數學家大會有多人因研究隨機性獲獎。最近著名可計算理論學家Downey因此獲得國際數學家大會45分鐘報告的邀請（這在數理邏輯中幾乎是最高榮譽）。.我們主要從可計算性理論觀點出發，刻畫隨機性。研究隨機性與可計算性的關係並且運用可計算性理論的方法研究隨機數的Kolmogorov複雜性。我們將著重於研究lowness性質以及分離2-randomness,strongly Chaitin randomness 和 3-randomness. .我們還著重於圖靈度的整體結構的研究。這是可計算性理論的一個古老課題。現在遺留的公開問題都是極為困難的。近來我們發現算法資訊理論中的一些方法可以成功地運用到這一領域。
