Это теоретический вопрос, поэтому ожидайте, что многие детали здесь не вычисляются на практике или даже в теории.
Допустим, у меня есть строка s, которую я хочу сжать.Результатом должен быть самораспаковывающийся двоичный файл (может быть x86 asm, но также может быть и другой гипотетический язык низкого уровня, полный по Тьюрингу), который выдает s.
Теперь мы можем легко перебрать все возможныедвоичные файлы / программы, упорядоченные по размеру.Пусть B_s будет подсписком этих двоичных файлов, которые выводят s (конечно, B_s не вычислимо).
Поскольку каждый набор натуральных чисел должен иметь минимум, должна быть наименьшая программаb_min_s in B_s
Из s я также могу построить каноническую программу b_cano_s, которая просто выводит s тривиальным способом.Т.е. размер b_cano_s будет в O(#s) - если мы подумаем о ELF с сегментами данных, у нас даже будет #b_cano_s ~ #s.
Есть ли набор A возможных операций над двоичными файлами, которые:
1.Сохранит вывод.
2a.Учитывая b_cano_s, мы можем каким-то образом поступить с помощью операций A в b_min_s.
(2b. Учитывая b_cano_s, мы можем прибыть во все программы в B_s.)
для всех возможных строк s.
Условия 1 + 2a слабее условий 1 + 2b.Может быть, если есть такой набор A, мы автоматически получим оба.(Это так?)
Существует ли такой набор A?Я думал о некоторых очевидных операциях, таких как поиск повторяющихся строк и сокращение этого.Или некоторые другие распространенные методы сжатия.Тем не менее, этого, вероятно, недостаточно для того, чтобы прийти ко всем программам B_s, и мое намерение также не обязательно означает b_min_s по той же причине.
Если она существует, можем ли мы выразить ее, т. Е. Можно ли вычислить