Fuzzy Kolmogorov Complexity Based on a Classical Description
In this paper, we give a definition for fuzzy Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a single finite string is the length of the shortest program that produces this string. We define the fuzzy Kolmogorov complexity as the minimum classical description length of...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/22/1/66 |
| _version_ | 1798035385194905600 |
|---|---|
| author | Songsong Dai |
| author_facet | Songsong Dai |
| author_sort | Songsong Dai |
| collection | DOAJ |
| description | In this paper, we give a definition for fuzzy Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a single finite string is the length of the shortest program that produces this string. We define the fuzzy Kolmogorov complexity as the minimum classical description length of a finite-valued fuzzy language through a universal finite-valued fuzzy Turing machine that produces the desired fuzzy language. The classical Kolmogorov complexity is extended to the fuzzy domain retaining classical descriptions. We show that our definition is robust, that is to say, the complexity of a finite-valued fuzzy language does not depend on the underlying finite-valued fuzzy Turing machine. |
| first_indexed | 2024-04-11T20:57:20Z |
| format | Article |
| id | doaj.art-60b726c9914a43eb97a2352573e4c86c |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-11T20:57:20Z |
| publishDate | 2020-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-60b726c9914a43eb97a2352573e4c86c2022-12-22T04:03:38ZengMDPI AGEntropy1099-43002020-01-012216610.3390/e22010066e22010066Fuzzy Kolmogorov Complexity Based on a Classical DescriptionSongsong Dai0School of Electronics and Information Engineering, Taizhou University, Taizhou 318000, ChinaIn this paper, we give a definition for fuzzy Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a single finite string is the length of the shortest program that produces this string. We define the fuzzy Kolmogorov complexity as the minimum classical description length of a finite-valued fuzzy language through a universal finite-valued fuzzy Turing machine that produces the desired fuzzy language. The classical Kolmogorov complexity is extended to the fuzzy domain retaining classical descriptions. We show that our definition is robust, that is to say, the complexity of a finite-valued fuzzy language does not depend on the underlying finite-valued fuzzy Turing machine.https://www.mdpi.com/1099-4300/22/1/66fuzzy turing machinesfuzzy languageskolmogorov complexity |
| spellingShingle | Songsong Dai Fuzzy Kolmogorov Complexity Based on a Classical Description Entropy fuzzy turing machines fuzzy languages kolmogorov complexity |
| title | Fuzzy Kolmogorov Complexity Based on a Classical Description |
| title_full | Fuzzy Kolmogorov Complexity Based on a Classical Description |
| title_fullStr | Fuzzy Kolmogorov Complexity Based on a Classical Description |
| title_full_unstemmed | Fuzzy Kolmogorov Complexity Based on a Classical Description |
| title_short | Fuzzy Kolmogorov Complexity Based on a Classical Description |
| title_sort | fuzzy kolmogorov complexity based on a classical description |
| topic | fuzzy turing machines fuzzy languages kolmogorov complexity |
| url | https://www.mdpi.com/1099-4300/22/1/66 |
| work_keys_str_mv | AT songsongdai fuzzykolmogorovcomplexitybasedonaclassicaldescription |