В том числе. Интересно другое. Есть любопытная связь колмогоровской сложности строки с количеством возможных представлений этой строки(на множестве которых вводится псевдомера которая суммирует все к колмогоровской сложности). В некотором смысле - если у строки есть малая сложность, то у нее есть очень много больших представлений. Я это интерпретирую так, что хоть алгоритм который по псевдослучайной строке декодирует ее генератор, вряд ли доступен из общих соображений, тем не менее какой-то алгоритм(причем их должно быть много) должен это сжимать, тем не менее.

Ну и второе - реальные данные которые использует человек мало похожи на псевдослучайные. Те архиваторы которые есть сжимают, но не удивлюсь если они сжимают как раз к этому псевдослучайному барьеру, а реальная колмогоровская сложность сильно ниже, и чем сильнее ниже тем больше шансов что какой-то другой алгоритм это сожмет лучше.