Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity and that, usually, generic lossless compression algorithms fall short at characterizing features other than statistical ones not different from entropy evaluations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure calculated from the output distribution of small Turing machines. We introduce and justify finite approximations that have been used in some applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both and and compare them to Levin’s Universal Distribution. We provide error estimations of with respect to . Finally, we present an application to integer sequences from the On-Line Encyclopedia of Integer Sequences, which suggests that our AP-based measures may characterize nonstatistical patterns, and we report interesting correlations with textual, function, and program description lengths of the said sequences.
from #AlexandrosSfakianakis via Alexandros G.Sfakianakis on Inoreader http://ift.tt/2BV3ZZQ
via IFTTT
Εγγραφή σε:
Σχόλια ανάρτησης (Atom)
Δημοφιλείς αναρτήσεις
-
from #AlexandrosSfakianakis via Alexandros G.Sfakianakis on Inoreader http://ift.tt/2z8PLPw via IFTTT
-
Purpose: Loss of volume in the sub-brow fat pad with associated descent of the eyebrow is a common anatomical finding resulting in both func...
-
Publication date: October 2017 Source: International Journal of Biological Macromolecules, Volume 103 Author(s): Mingan Yu, Duqiang Liu, ...
-
Cachexia is a debilitating syndrome characterized by involuntary muscle wasting that is triggered at the late stage of many cancers. While t...
-
Abstract Endurance exercise generates CO 2 via aerobic metabolism; however, its role remains unclear. Exogenous CO 2 by transcutaneous d...
-
Publication date: Available online 5 December 2017 Source: Biochimie Author(s): Jameel Lone, Hilal Ahmad Parray, Jong Won Yun Browning of...
-
Publication date: Available online 13 April 2017 Source: Biochimica et Biophysica Acta (BBA) - Molecular Cell Research Author(s): Marcos J...
-
Daily Mail Sarah was diagnosed with the cancer that killed Steve Jobs Daily Mail The symptoms Sarah Smith experienced on and off for...
-
Chapter 1 Introduction Background of the Study Cockroaches are common pests in the tropics. They have been known to cause allergic reactions...
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου