A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
المؤلفون المشاركون
Soler-Toscano, Fernando
Zenil, Hector
المصدر
العدد
المجلد 2017، العدد 2017 (31 ديسمبر/كانون الأول 2017)، ص ص. 1-10، 10ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2017-12-21
دولة النشر
مصر
عدد الصفحات
10
التخصصات الرئيسية
الملخص EN
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 m calculated from the output distribution of small Turing machines.
We introduce and justify finite approximations mk 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 m and mk and compare them to Levin’s Universal Distribution.
We provide error estimations of mk with respect to m.
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.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Soler-Toscano, Fernando& Zenil, Hector. 2017. A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity،Vol. 2017, no. 2017, pp.1-10.
https://search.emarefa.net/detail/BIM-1143373
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Soler-Toscano, Fernando& Zenil, Hector. A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity No. 2017 (2017), pp.1-10.
https://search.emarefa.net/detail/BIM-1143373
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Soler-Toscano, Fernando& Zenil, Hector. A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences. Complexity. 2017. Vol. 2017, no. 2017, pp.1-10.
https://search.emarefa.net/detail/BIM-1143373
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1143373
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر