Đây là một câu hỏi lý thuyết, do đó, hy vọng rằng nhiều chi tiết ở đây không được tính toán trong thực tế hoặc thậm chí trong lý thuyết.Tốc độ nén tối đa về mặt lý thuyết có thể là bao nhiêu?
Giả sử tôi có một chuỗi s mà tôi muốn nén. Kết quả phải là một nhị phân tự giải nén (có thể là trình biên dịch x86, nhưng nó cũng có thể là một số ngôn ngữ mức độ thấp hoàn toàn giả thuyết Turing khác) xuất ra s.
Bây giờ, chúng tôi có thể dễ dàng lặp qua tất cả các chương trình và tệp nhị phân như vậy, được sắp xếp theo kích thước. Hãy để B_s là danh sách phụ của những tệp nhị phân này, xuất ra s (tất nhiên là B_s là không thể chối cãi).
Vì mỗi bộ số nguyên dương phải có giá trị nhỏ nhất, phải có chương trình nhỏ nhất b_min_s trong B_s.
Đối với ngôn ngữ nào (tức là tập hợp các chuỗi), chúng tôi có biết điều gì đó về kích thước của b_min_s không? Có lẽ chỉ là một ước tính. (Tôi có thể xây dựng một số ví dụ tầm thường nơi tôi luôn có thể thậm chí tính toán B_s và cũng b_min_s, nhưng tôi quan tâm đến ngôn ngữ thú vị hơn.)
Tôi nhớ lại một số chương trình rất thông minh từ những ngày cũ, chẳng hạn như bộ tải khởi động tự ghi đè nhiều lần. Có khả năng, để đạt được kích thước tối thiểu tổng thể của chương trình tự giải nén, chương trình có thể sử dụng văn bản riêng của nó bằng cách nào đó - ví dụ, như một nguồn của các hằng số. –