NDLI: A Chaitin $$\Upomega$$ number based on compressible strings

Content Provider	Springer Nature Link
Author	Tadaki, Kohtaro
Copyright Year	2011
Abstract	In 1975 Chaitin introduced his $$Ω$$ number as a concrete example of random real. The real $$Ω$$ is defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed $$Ω$$ to be random by discovering the property that the first n bits of the base-two expansion of $$Ω$$ solve the halting problem of U for all binary inputs of length at most n. In this article, we introduce a new variant $$Θ$$ of Chaitin $$Ω$$ number. The real $$Θ$$ is defined based on the set of all compressible strings. We investigate the distribution of compressible strings and show that $$Θ$$ is random. In addition, we generalize $$Θ$$ to $$Θ(Q, R)$$ with reals Q, R > 0 and study its properties. In particular, we show that the computability of the real $$Θ(T,\,1)$$ gives a sufficient condition for a real T ∈ (0, 1) to be a fixed point for partial randomness, i.e., to satisfy that the compression rate of T equals to T.
Starting Page	117
Ending Page	128
Page Count	12
File Format	PDF
ISSN	15677818
Journal	Natural Computing
Volume Number	11
Issue Number	1
e-ISSN	15729796
Language	English
Publisher	Springer Netherlands
Publisher Date	2011-08-21
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithmic information theory Algorithmic randomness Chaitin $$Ω$$ number Compressible string Fixed point Partial randomness Program-size complexity Evolutionary Biology Theory of Computation Artificial Intelligence (incl. Robotics) Processor Architectures Statistical Physics, Dynamical Systems and Complexity
Content Type	Text
Resource Type	Article
Subject	Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fixed points on partial randomness.

Classical, quantum and biological randomness as relative unpredictability

Entropy and algorithmic complexity in quantum information theory

Fixed point theorems on partial randomness (2009)

Light-based string matching

Toward minimum size self-assembled counters

Turing patterns with Turing machines: emergence and low-level structure formation

Computation in Sofic Quantum Dynamical Systems

Algorithmic applications of XPCR

A Chaitin $$\Upomega$$ number based on compressible strings

Similar Documents

Fixed points on partial randomness.

Classical, quantum and biological randomness as relative unpredictability

Entropy and algorithmic complexity in quantum information theory

Fixed point theorems on partial randomness (2009)

Light-based string matching

Toward minimum size self-assembled counters

Turing patterns with Turing machines: emergence and low-level structure formation

Computation in Sofic Quantum Dynamical Systems

Algorithmic applications of XPCR

A Chaitin $$\Upomega$$ number based on compressible strings