2025-11-24T00:07:16.848038

A Variant Of Chaitin's Omega function

Li, Zhang, Zhang et al.

We investigate the continuous function $f$ defined by $$x\mapsto \sum_{Ï\le_L x }2^{-K(Ï)}$$ as a variant of Chaitin's Omega from the perspective of analysis, computability, and algorithmic randomness. Among other results, we obtain that: (i) $f$ is differentiable precisely at density random points; (ii) $f(x)$ is $x$-random if and only if $x$ is weakly low for $K$ (low for $Î©$); (iii) the range of $f$ is a null, nowhere dense, perfect $Î ^0_1(\emptyset')$ class with Hausdorff dimension $1$; (iv) $f(x)\oplus x\ge_T\emptyset'$ for all $x$; (v) there are $2^{\aleph_0}$ many $x$ such that $f(x)$ is not 1-random; (vi) $f$ is not Turing invariant but is Turing invariant on the ideal of $K$-trivial reals. We also discuss the connection between $f$ and other variants of Omega.

academic

Chaitin's Omega関数の変種

基本情報

論文ID: 2508.16892
タイトル: A Variant Of Chaitin's Omega Function
著者: Yuxuan Li, Shuheng Zhang, Xiaoyan Zhang, Xuanheng Zhao
分類: math.LO（数理論理学）
発表日時: 2025年10月10日（arXiv v2）
論文リンク: https://arxiv.org/abs/2508.16892v2

要旨

本論文は、数学解析、計算可能性、およびアルゴリズム的ランダム性の観点から、連続関数 $f: x \mapsto \sum_{\sigma \leq_L x} 2^{-K(\sigma)}$ をChaitin's Omegaの変種として研究する。主な結果は以下の通りである：(i) $f$ は密度ランダム点においてのみ微分可能である；(ii) $f(x)$ が $x$ -ランダムであることと $x$ が弱 $K$ -低い（ $\Omega$ より低い）ことは同値である；(iii) $f$ の値域は零測度、疎密でない完全な $\Pi^0_1(\emptyset')$ 類であり、Hausdorff次元は1である；(iv) すべての $x$ に対して $f(x) \oplus x \geq_T \emptyset'$ である；(v) $f(x)$ が1-ランダムでない $x$ が $2^{\aleph_0}$ 個存在する；(vi) $f$ はチューリング不変ではないが、 $K$ -自明実数のイデアル上ではチューリング不変である。

研究背景と動機

問題背景

Chaitin's Omega関数 $\Omega = \sum_{U(\sigma)\downarrow} 2^{-|\sigma|}$ はアルゴリズム的ランダム性理論の中核概念であり、最適前置自由機械の停止確率を表す。左可枚挙かつ1-ランダムな実数の典型例として、Omegaは計算可能性理論において重要な地位を占めている。

研究動機

既存のOmega変種の研究は主に以下に集中している：

オラクル機械変種：Downeyらが定義したオラクルOmega作用素 $x \mapsto \sum_{V^x(\sigma)\downarrow} 2^{-|\sigma|}$ であるが、この作用素は連続でなく、チューリング不変ではない
連続関数変種：Hölzlらが研究した $x \mapsto \sum_{\sigma \prec x} 2^{-K_U(\sigma)}$ であり、これが1-ランダム実数においてのみ微分可能であることを証明した

本論文の革新点

本論文は新しい変種 $f(x) = \sum_{\sigma \leq_L x} 2^{-K_U(\sigma)}$ を導入する。ここで $\sigma \leq_L x$ は $\sigma$ が $x$ の左側にあるか、 $x$ の初期セグメントであることを意味する。この関数は厳密単調増加性を持ち、その値域構造は既存の変種よりも分析しやすい。

核心的貢献

微分可能性の特性化： $f$ が密度ランダム点においてのみ微分可能であり、導数が0であることを証明した
ランダム性の同値性： $f(x)$ の $x$ -ランダム性と $x$ の弱 $K$ -低さの同値関係を確立した
値域の幾何学的構造： $f(2^\omega)$ の測度論的および位相的性質を完全に特性化した
複雑度分析： $f(x) \oplus x \geq_T \emptyset'$ の普遍的性質を証明した
チューリング不変性：異なる実数類上での $f$ のチューリング不変性を分析した
存在性結果：非1-ランダムな関数値 $2^{\aleph_0}$ 個を構成した

方法の詳細

核心的定義

関数定義： $x \in 2^\omega$ に対して、 $f(x) = \sum_{\sigma \leq_L x} 2^{-K_U(\sigma)}$ と定義する。ここで：

$\sigma <_L x$ は、ある $n$ が存在して $\sigma \restriction n = x \restriction n$ 、 $\sigma(n) = 0$ 、 $x(n) = 1$ を意味する
$\sigma \leq_L x$ は $\sigma <_L x$ または $\sigma$ が $x$ の初期セグメントであることを意味する

技術的ツール

補助関数の構成

補助関数を定義する： $\hat{f}(\sigma) = 2^{|\sigma|}(f(\sigma 1^\infty) - f(\sigma 0^\infty))$

この関数は可枚挙上マルチンゲールであり、関数のランダム性質の分析に用いられる。

小摂動補題

補題5.13（小摂動補題）：任意の実数 $x$ と $n \in \omega$ に対して、 $|f(x \triangle j) - f(x)| > 2^{-n}$ となる $j$ が存在すれば、 $2^{-n-c} \leq |f(y) - f(x)| \leq 2^{-n}$ を満たす $y \in 2^\omega$ が存在する。