Very Simple Chaitin Machines for Concrete AIT

MaRDI QIDQ5472891zbMATH OpenFDO

Authors Michael Stay

Publication date 19 June 2006

Full work available at URL https://arxiv.org/abs/cs/0508056

zbMATH Keywords

lambda calculus

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: In 1975, Chaitin introduced his celebrated Omega number, the halting probability of a universal Chaitin machine, a universal Turing machine with a prefix-free domain. The Omega number's bits are {em algorithmically random}--there is no reason the bits should be the way they are, if we define ``reason to be a computable explanation smaller than the data itself. Since that time, only {em two} explicit universal Chaitin machines have been proposed, both by Chaitin himself. Concrete algorithmic information theory involves the study of particular universal Turing machines, about which one can state theorems with specific numerical bounds, rather than include terms like O(1). We present several new tiny Chaitin machines (those with a prefix-free domain) suitable for the study of concrete algorithmic information theory. One of the machines, which we call Keraia, is a binary encoding of lambda calculus based on a curried lambda operator. Source code is included in the appendices. We also give an algorithm for restricting the domain of blank-endmarker machines to a prefix-free domain over an alphabet that does not include the endmarker; this allows one to take many universal Turing machines and construct universal Chaitin machines from them.

Recommendations

• scientific article; zbMATH DE number 4084874
• Publication:3483324
• Concrete lattices
• scientific article; zbMATH DE number 567280
• Concrete fibrations
• Constructing the Simples
• A general failure criterion for plain concrete
• Counter machines
• Forming tile shapes with simple robots

Cited in

(3)

• scientific article; zbMATH DE number 1542864 (Why is no real title available?)
• Computing a Glimpse of Randomness
• Natural halting probabilities, partial randomness, and zeta functions

This page was built for publication: Very Simple Chaitin Machines for Concrete AIT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5472891)