List Approximation for Increasing Kolmogorov Complexity
It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. However, is it possible to construct a few strings, no longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that takes as inpu...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-12-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/10/4/334 |