# 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

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.

Access the full text.

Sign up today, get DeepDyve free for 14 days.