✦ LIBER ✦

Kolmogorov complexity and set theoretical representations of integers

✍ Scribed by Marie Ferbus-Zanda; Serge Grigorieff

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 345 KB
Volume: 52
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.200510040

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We reconsider some classical natural semantics of integers (namely iterators of functions, cardinals of sets, index of equivalence relations) in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self‐enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations (cf. [6]). This contrasts with the well‐known fact that usual Kolmogorov complexity does not depend (up to a constant) on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 SIMILAR VOLUMES

On Optimal Subset Representations of Int

On Optimal Subset Representations of Integer Sets

✍ Mike Develin 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 121 KB

In this paper, we investigate representations of sets of integers as subset sums of other sets of minimal size, achieving results on the nature of the representing set as well as providing several reformulations of the problem. We apply one of these reformulations to prove a conjecture and extend a

Construction of expanders and superconce

Construction of expanders and superconcentrators using Kolmogorov complexity

✍ Uwe Schöning 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

We show the existence of various versions of expander graphs using Kolmogorov complexity. This method seems superior to the usual probabilistic construction. It turns out that the best known bounds on the size of expanders and superconcentrators can be attained based on this method. In the case of (

Kolmogorov complexity and characteristic

Kolmogorov complexity and characteristic constants of formal theories of arithmetic

✍ Shingo Ibuka; Makoto Kikuchi; Hirotaka Kikyo 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB

We investigate two constants c T and r T , introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that c T does not represent the complexity of T and f

The set of fuzzy relative integers and f

The set of fuzzy relative integers and fuzzy bags

✍ Daniel Rocacher; Patrick Bosc 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB

A characterization of fuzzy bags with conjunctive fuzzy integers (N f ) provides a general framework in which sets, bags, fuzzy sets, and fuzzy bags are treated in a uniform way. In this context, the difference between two fuzzy bags does not always exist and, in such cases, only approximations of t

Complexity of Representations of Quantis

Complexity of Representations of Quantised Function Algebras and Representation Type

✍ Iain Gordon 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 287 KB

Ž q . w x B be opposite Borel subgroups of G, and ᑿ s Lie B . Let O G be the ⑀ quantised function algebra at a root of unity ⑀ and let U G 0 be the quantised ⑀ enveloping algebra of ᑿ at a root of unity. We study the finite dimensional factor w xŽ . G 0 Ž . y algebras O G g and U b for g g G and b g

On set intersection representations of g

On set intersection representations of graphs

✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only