純リスプに基づいた頭語的評価関数の概要 : Chaitinのアルゴリズムの欠陥とその修正
スポンサーリンク
概要
- 論文の詳細を見る
アルゴリズム的情報理論(Algorithmic information theoryは、複雑さに対する定量的な尺度を与え、その性質や応用を研究する理論である。0とTからなる記号列、即ちbinary string sが与えられたとき、その複雑さ(complexity)は、"sを出力する最短のアルゴリズム(プログラム)の長さ"として定義される。プログラムの長さを決めるにはそれを実行する計算機、すなわち計算可能な部分評価関数(以下では単に部分評価関数と呼ぶ)が必要であり、complexityの性質はこの部分評価関数の選び方に依存する。そこでChaitinはこの部分評価関数としてその定義域が頭語条件を満たすものを用いれば、complexityがShannonの情報論的エントロピーに類似心た、応川上重要な性質を持つことを示した。そして頭語条件を満たす部分評価関数uが実際に存在することを示すためにまずTuringmachineに基づいたuのアルゴリズムを提案し、次に一種の純リスプに基づいたアルゴリズムを与えた。しかし、この純リスプに基づいたアルゴリズムには、Chaitinが与えたままでは欠陥があり,uの定義域が実際には頭語条件を満たさなくなってしまう。本発表ではそのことを示す。さらに、実際に頭語条件を満たすようアルゴリズムの修正を行なう。
- 一般社団法人情報処理学会の論文
- 1993-03-01
著者
関連論文
- 31a-ZF-7 半導体ヘテロ構造におけるスピン偏極2次元電子ガスのスピン拡散係数
- 3. 非線形力学系における量子古典遷移(第9回『非平衡系の統計物理』シンポジウム,研究会報告)
- Quantum Kicked RotorでのQuantum Trajectory(第8回「非平衡系の統計物理」シンポジウム,研究会報告)
- 量子古典対応とノイズ : Wigner関数の負度と古典化(第7回『非平衡系の統計物理』シンポジウム,研究会報告)
- 量子古典対応とデコヒーレンス(第5回『非平衡系の統計物理』シンポジウム)
- カオス, ノイズ, および量子古典対応(量子確率論とエントロピー解析)
- 情報消去と熱散逸 : Fokker-Planck方程式からの導出(ポスター・セッション・プログラム,第3回『非平衡系の統計物理』シンポジウム(その2),研究会報告)
- 純リスプに基づいた頭語的評価関数の概要 : Chaitinのアルゴリズムの欠陥とその修正
- 27p-PS-34 spin-echo系のalgorithmic complexity
- アルゴリズム的情報理論における語頭的評価関数
- 純リスプに基づいた頭語的評価関数--Chaitinのアルゴリズムの欠陥とその修正