Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Methods and Applications of Algorithmic ComplexityTheoretical Aspects of Finite Approximations to Levin’s Semi-measure

Methods and Applications of Algorithmic Complexity: Theoretical Aspects of Finite Approximations... [In this chapter we study the formal properties of a Levin-inspired measure m calculated from the output distribution of small Turing machines running on a blank tape. We introduce and justify finite approximations mk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m_k$$\end{document} that work in a similar way to our D(k) distributions. We provide proofs of the relevant properties of both m and mk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m_k$$\end{document} and compare them to Levin’s Universal Distribution. We calculate error estimations of mk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m_k$$\end{document} with respect to m.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Methods and Applications of Algorithmic ComplexityTheoretical Aspects of Finite Approximations to Levin’s Semi-measure

Download PDF
11 pages

Loading next page...
 
/lp/springer-journals/methods-and-applications-of-algorithmic-complexity-theoretical-aspects-i8X6C10kk5
Publisher
Springer Berlin Heidelberg
Copyright
© Springer-Verlag GmbH Germany, part of Springer Nature 2022
ISBN
978-3-662-64983-1
Pages
89 –100
DOI
10.1007/978-3-662-64985-5_4
Publisher site
See Chapter on Publisher Site

Abstract

[In this chapter we study the formal properties of a Levin-inspired measure m calculated from the output distribution of small Turing machines running on a blank tape. We introduce and justify finite approximations mk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m_k$$\end{document} that work in a similar way to our D(k) distributions. We provide proofs of the relevant properties of both m and mk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m_k$$\end{document} and compare them to Levin’s Universal Distribution. We calculate error estimations of mk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m_k$$\end{document} with respect to m.]

Published: May 17, 2022

There are no references for this article.