純リスプに基づいた頭語的評価関数の概要 : Chaitinのアルゴリズムの欠陥とその修正

IPSJ

Bibliographic Information

Other Title
  • The Lisp based self-delimiting universal function

Search this article

Abstract

アルゴリズム的情報理論(Algorithmic information theoryは、複雑さに対する定量的な尺度を与え、その性質や応用を研究する理論である。0とTからなる記号列、即ちbinary string sが与えられたとき、その複雑さ(complexity)は、"sを出力する最短のアルゴリズム(プログラム)の長さ"として定義される。プログラムの長さを決めるにはそれを実行する計算機、すなわち計算可能な部分評価関数(以下では単に部分評価関数と呼ぶ)が必要であり、complexityの性質はこの部分評価関数の選び方に依存する。そこでChaitinはこの部分評価関数としてその定義域が頭語条件を満たすものを用いれば、complexityがShannonの情報論的エントロピーに類似心た、応川上重要な性質を持つことを示した。そして頭語条件を満たす部分評価関数uが実際に存在することを示すためにまずTuringmachineに基づいたuのアルゴリズムを提案し、次に一種の純リスプに基づいたアルゴリズムを与えた。しかし、この純リスプに基づいたアルゴリズムには、Chaitinが与えたままでは欠陥があり,uの定義域が実際には頭語条件を満たさなくなってしまう。本発表ではそのことを示す。さらに、実際に頭語条件を満たすようアルゴリズムの修正を行なう。

Journal

Details 詳細情報について

Report a problem

Back to top