Кто-то скажет (тот, кто пишет на С), что код, написанный на C, короче, чем код, написанный на Java или Basic. Или действительно короче?
Вы удивитесь, но, оказывается, если взять 2 языка программирования, назовём их А и Б, то существует константа, которая составляет разницу между длинами кодов этих двух языков для всех программ.
Серьёзно!
Для начала пара обозначений.
Пусть Длина(А, ф) для языка А и функции ф — это количество символов в самой маленькой по длине программе, которая вычисляет функцию ф, написанной на языке А. (Здесь надо подумать)
Список всех функций определим как ф(1), ф(2), ф(3),… (их бесконечно много)
В результате мы получим одну единственную константу с, такую что для любого i:
Длина(А, Ф(i)) <= Длина(Б, Ф(i)) + с и наоборот,
Длина(Б, Ф(i)) <= Длина(А, Ф(i)) + с
Почему?
Потому что на языке А можно написать интерпретатор для языка Б и передавать программу языка Б как параметр программе, написанной на языке А. И наоборот. Тогда нашей константой с выступит сумма длин программ-интерпретаторов, написанных на языке А и на языке Б.
P.S. Не надо говорить, что не на всяком языке программирования можно написать интерпретатор, потому что рассматривается просто общий случай.
Литература: Ming Li, Paul Vitanyi — An Introduction to Kolmogorov Complexity and its Applications.
Вы удивитесь, но, оказывается, если взять 2 языка программирования, назовём их А и Б, то существует константа, которая составляет разницу между длинами кодов этих двух языков для всех программ.
Серьёзно!
Для начала пара обозначений.
Пусть Длина(А, ф) для языка А и функции ф — это количество символов в самой маленькой по длине программе, которая вычисляет функцию ф, написанной на языке А. (Здесь надо подумать)
Список всех функций определим как ф(1), ф(2), ф(3),… (их бесконечно много)
В результате мы получим одну единственную константу с, такую что для любого i:
Длина(А, Ф(i)) <= Длина(Б, Ф(i)) + с и наоборот,
Длина(Б, Ф(i)) <= Длина(А, Ф(i)) + с
Почему?
Потому что на языке А можно написать интерпретатор для языка Б и передавать программу языка Б как параметр программе, написанной на языке А. И наоборот. Тогда нашей константой с выступит сумма длин программ-интерпретаторов, написанных на языке А и на языке Б.
P.S. Не надо говорить, что не на всяком языке программирования можно написать интерпретатор, потому что рассматривается просто общий случай.
Литература: Ming Li, Paul Vitanyi — An Introduction to Kolmogorov Complexity and its Applications.
