This is a question that I got from these posts, which essentially talked about how the constant issue impacts discussions of simplicity, and thus I wanted to ask a question about Kolmogorov Complexity:
What’s the lowest additive constant that can be achieved by a programming language while still being Turing-Complete?
Or equivalently, what’s the least overhead that you must have in order to describe an object like a computer program or string?
Bonus points for not only establishing a lower bound, but either finding a programming language that achieves the lower bound and showing the source, or actually creating a programming language that achieves the lower bound.
As a side question, I’d also like estimations of how much overhead/the additive constant is added to popular languages like Python, Java, C, C++, and Rust.
[Question] What’s the minimal additive constant for Kolmogorov Complexity that a programming language can achieve?
This is a question that I got from these posts, which essentially talked about how the constant issue impacts discussions of simplicity, and thus I wanted to ask a question about Kolmogorov Complexity:
https://www.lesswrong.com/posts/uWdAKyHZMfoxDHcCC/simplicity-arguments-for-scheming-section-4-3-of-scheming#What_is__simplicity__
https://joecarlsmith.com/2021/10/29/on-the-universal-distribution#iii-is-everything-equivalent-up-to-a-finite-fudge-factor
https://en.wikipedia.org/wiki/Kolmogorov_complexity#Invariance_theorem
What’s the lowest additive constant that can be achieved by a programming language while still being Turing-Complete?
Or equivalently, what’s the least overhead that you must have in order to describe an object like a computer program or string?
Bonus points for not only establishing a lower bound, but either finding a programming language that achieves the lower bound and showing the source, or actually creating a programming language that achieves the lower bound.
As a side question, I’d also like estimations of how much overhead/the additive constant is added to popular languages like Python, Java, C, C++, and Rust.