|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 18 van 56 gevonden artikelen
| Titel: |
Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures |
| Auteur: |
Soler-Toscano, Fernando Zenil, Hector Delahaye, Jean-Paul Gauvrit, Nicolas |
| Verschenen in: |
Computability |
| Paginering: | Jaargang 2 (2013) nr. 2 pagina's 125-140 |
| Jaar: |
2013-12-10 |
| Inhoud: |
We show that real-value approximations of Kolmogorov-Chaitin complexity K(s) using the algorithmic coding theorem, as calculated from the output frequency of a large set of small deterministic Turing machines with up to 5 states (and 2 symbols), is consistent with the number of instructions used by the Turing machines producing s, which in turn is consistent with strict integer-value program-size complexity (based on our knowledge of the smallest machine in terms of the number of instructions used). We also show that neither K(s) nor the number of instructions used manifests any correlation with Bennett's Logical Depth LD(s), other than what's predicted by the theory (shallow and non-random strings have low complexity under both measures). The agreement between the theory and the numerical calculations shows that despite the undecidability of these theoretical measures, the rate of convergence of approximations is stable enough to devise some applications. We announce a Beta version of an Online Algorithmic Complexity Calculator (OACC) implementing these methods. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 18 van 56 gevonden artikelen
| << vorige | volgende >> |