Độ phức tạp Kolmogorov khác gì so với Entropy Shannon?

Entropy Shannon đo lường lượng thông tin trung bình theo một phân phối xác suất thống kê cho trước. Ngược lại, độ phức tạp Kolmogorov đo lượng thông tin nội tại của một đối tượng dữ liệu cá thể duy nhất dựa trên độ dài chương trình ngắn nhất sinh ra nó.

Tại sao độ phức tạp Kolmogorov không thể tính toán được (uncomputable)?

Việc tính toán độ phức tạp Kolmogorov tương đương với việc giải quyết Bài toán dừng (Halting Problem) của Alan Turing. Do không có thuật toán nào có thể xác định xem một chương trình tùy ý có dừng lại hay không, nên không thể duyệt qua mọi chương trình để tìm ra chương trình ngắn nhất.

Thế nào là một chuỗi ngẫu nhiên theo nghĩa thuật toán?

Một chuỗi nhị phân được coi là ngẫu nhiên theo nghĩa Kolmogorov và Martin-Löf nếu nó không thể nén được, tức là độ phức tạp Kolmogorov của chuỗi xấp xỉ bằng chính độ dài của nó (không có chương trình nào ngắn hơn có thể sinh ra chuỗi).

Định lý bất biến của Kolmogorov có ý nghĩa gì?

Định lý bất biến chứng minh rằng độ phức tạp Kolmogorov của một chuỗi giữa hai ngôn ngữ lập trình vạn năng hoặc máy Turing vạn năng khác nhau chỉ sai khác tối đa một hằng số cố định (độ dài trình biên dịch), giúp khẳng định đây là thuộc tính khách quan của dữ liệu.

Độ phức tạp Kolmogorov là gì? Định nghĩa và ứng dụng

Độ phức tạp Kolmogorov (Kolmogorov complexity), còn được gọi là độ phức tạp mô tả hay độ phức tạp thuật toán (algorithmic complexity), là độ dài của chương trình máy tính ngắn nhất chạy trên một máy Turing vạn năng có khả năng sinh ra một chuỗi nhị phân hoặc đối tượng dữ liệu cho trước và dừng lại. Được đề xuất độc lập bởi Andrey Kolmogorov, Ray Solomonoff và Gregory Chaitin vào giai đoạn khởi xướng, khái niệm này tạo nên nền tảng của lý thuyết thông tin thuật toán (Algorithmic Information Theory), thiết lập cầu nối sâu sắc giữa khoa học tính toán lý thuyết, lý thuyết thông tin và nhận thức luận khoa học. Mục từ này phân tích định nghĩa hình thức, định lý bất biến, tính không tính toán được, mối liên hệ với tính ngẫu nhiên thuật toán, tương quan với entropy Shannon và các ứng dụng thực tiễn trong nén dữ liệu và suy luận quy nạp.

Định nghĩa hình thức và Mô hình máy Turing

Để lượng hóa lượng thông tin nội tại chứa trong một chuỗi ký tự hữu hạn mà không phụ thuộc vào các giả định phân phối xác suất ngẫu nhiên bên ngoài, độ phức tạp Kolmogorov sử dụng mô hình tính toán hình thức của Alan Turing.

Độ phức tạp Kolmogorov thuần túy (Plain Complexity)

Cho $U$ là một máy Turing vạn năng (Universal Turing Machine) và $s$ là một chuỗi nhị phân hữu hạn thuộc tập $\{0, 1\}^*$ . Độ phức tạp Kolmogorov thuần túy của chuỗi $s$ đối với máy $U$ , ký hiệu là $C_U(s)$ , được định nghĩa là độ dài ngắn nhất của một chuỗi chương trình đầu vào $p$ sao cho khi máy $U$ thực thi chương trình $p$ , nó xuất ra chính xác chuỗi $s$ và dừng lại:

C_U(s) = \min \{ |p| : U(p) = s \}

Nếu không tồn tại chương trình nào để $U$ sinh ra $s$ , ta quy ước $C_U(s) = \infty$ . Do $U$ là máy vạn năng, luôn tồn tại chương trình in trực tiếp chuỗi $s$ , nên $C_U(s)$ luôn là một số nguyên hữu hạn không âm.

Độ phức tạp Kolmogorov có điều kiện (Conditional Complexity)

Độ phức tạp Kolmogorov có điều kiện của chuỗi $s$ khi biết trước thông tin phụ trợ $y$ , ký hiệu là $C(s|y)$ , là độ dài của chương trình ngắn nhất nhận $y$ làm đầu vào bổ sung và sinh ra chuỗi $s$ :

C_U(s|y) = \min \{ |p| : U(p, y) = s \}

Khái niệm này đo lường lượng thông tin còn lại cần bổ sung để tái tạo chuỗi $s$ khi đã nắm giữ chuỗi dữ liệu $y$ .

Định lý bất biến của Kolmogorov

Một câu hỏi tự nhiên đặt ra là: liệu độ phức tạp của một chuỗi có bị phụ thuộc hoàn toàn vào việc lựa chọn ngôn ngữ lập trình hoặc cấu trúc phần cứng của máy Turing vạn năng hay không? Andrey Kolmogorov (1968) đã chứng minh Định lý bất biến (Invariance Theorem), khẳng định tính độc lập căn bản của thước đo này đối với mô hình máy tính cụ thể.

Phát biểu định lý

Cho $U$ là một máy Turing vạn năng cố định. Với mọi máy Turing $M$ bất kỳ, tồn tại một hằng số $c_M$ (chỉ phụ thuộc vào máy $M$ và $U$ , hoàn toàn không phụ thuộc vào chuỗi $s$ ) sao cho với mọi chuỗi nhị phân $s$ :

C_U(s) \le C_M(s) + c_M

Nếu $V$ cũng là một máy Turing vạn năng khác, thì áp dụng định lý theo cả hai chiều ta có:

|C_U(s) - C_V(s)| \le c_{U,V}

Ý nghĩa nền tảng

Hằng số $c_M$ về mặt trực giác chính là độ dài của chương trình mô phỏng (trình biên dịch hoặc trình thông dịch) cho phép máy vạn năng $U$ thực thi mã nguồn của máy $M$ . Khi độ dài chuỗi $s$ tiến tới vô cùng, hằng số này trở nên không đáng kể. Vì vậy, độ phức tạp Kolmogorov là một thuộc tính nội tại khách quan của chính đối tượng dữ liệu, không phụ thuộc vào công cụ tính toán được lựa chọn.

Tính không thể tính toán được (Uncomputability)

Mặc dù có định nghĩa toán học chính xác và thanh nhã, hàm độ phức tạp Kolmogorov là một hàm không thể tính toán được bằng bất kỳ thuật toán hữu hạn nào.

Mối liên hệ với Bài toán dừng (Halting Problem)

Gregory Chaitin (1966) đã chỉ ra rằng việc tính toán chính xác $C(s)$ tương đương với việc giải quyết Bài toán dừng của Alan Turing. Để tìm chương trình ngắn nhất sinh ra chuỗi $s$ , một thuật toán giả định sẽ phải duyệt qua tất cả các chương trình có độ dài tăng dần và chạy thử nghiệm. Tuy nhiên, theo định lý về bài toán dừng, không có thuật toán tổng quát nào có thể xác định xem một chương trình tùy ý sẽ dừng lại và xuất ra kết quả hay sẽ rơi vào vòng lặp vô tận.

Nghịch lý Berry và giới hạn của các hệ tiên đề hình thức

Tính không tính toán được cũng có thể được chứng minh thông qua biến thể của nghịch lý Berry: "Xét số nguyên nhỏ nhất không thể định nghĩa bằng ít hơn một trăm chữ". Nếu tồn tại một thuật toán tính được $C(s)$ , ta có thể viết một chương trình ngắn để tìm chuỗi đầu tiên có độ phức tạp lớn hơn chính độ dài chương trình đó, dẫn đến mâu thuẫn logic trực tiếp.

Hơn nữa, trong bất kỳ hệ tiên đề hình thức nhất quán nào (như hệ tiên đề Zermelo-Fraenkel), chỉ có thể chứng minh các mệnh đề có dạng $C(s) \ge k$ cho các giá trị $k$ nhỏ hơn một ngưỡng hằng số cố định phụ thuộc vào số lượng tiên đề của hệ thống.

Độ phức tạp tiền tố (Prefix Kolmogorov Complexity)

Trong cấu trúc độ phức tạp thuần túy $C(s)$ , việc xác định điểm kết thúc của chương trình $p$ đòi hỏi thông tin về độ dài của chương trình đó. Để khắc phục khiếm khuyết này và xây dựng một lý thuyết xác suất chặt chẽ, các nhà nghiên cứu đã giới thiệu Độ phức tạp tiền tố.

Khái niệm mã không tiền tố và Bất đẳng thức Kraft

Một tập hợp các chuỗi nhị phân được gọi là mã tiền tố tự do (prefix-free code) nếu không có chuỗi nào trong tập hợp là tiền tố của một chuỗi khác. Máy Turing tiền tố (Prefix Turing Machine) là máy chỉ chấp nhận tập miền xác định là một mã tiền tố tự do.

Theo Bất đẳng thức Kraft, đối với mọi tập chương trình hợp lệ của máy Turing tiền tố, tổng lũy thừa âm của độ dài các chương trình luôn hội tụ và bị chặn trên:

\sum_{p \in \mathrm{dom}(U)} 2^{-|p|} \le 1

Số ngẫu nhiên Chaitin Omega

Tổng xác suất dừng phổ quát của máy Turing tiền tố định nghĩa nên hằng số Chaitin $\Omega$ :

\Omega = \sum_{p \in \mathrm{dom}(U)} 2^{-|p|}

Hằng số $\Omega$ là một số thực nằm trong khoảng giữa 0 và 1, biểu diễn xác suất để một chương trình được sinh ngẫu nhiên từng bit sẽ dừng lại. Đây là một số siêu việt không thể tính toán được và mang tính ngẫu nhiên thuật toán tối đa.

Tính ngẫu nhiên thuật toán và Tính không thể nén

Trước khi lý thuyết độ phức tạp Kolmogorov ra đời, lý thuyết xác suất cổ điển gặp khó khăn trong việc định nghĩa thế nào là một chuỗi cá thể ngẫu nhiên. Ví dụ, một chuỗi gồm toàn chữ số 0 và một chuỗi tung đồng xu ngẫu nhiên có cùng xác suất xuất hiện $2^{-n}$ trong phân phối đều, nhưng trực giác cho thấy chuỗi thứ hai có tính ngẫu nhiên cao hơn.

Định nghĩa tính ngẫu nhiên theo Kolmogorov và Martin-Löf

Per Martin-Lof (1966) cùng với Kolmogorov và Chaitin đã đưa ra định nghĩa tính ngẫu nhiên thông qua tính không thể nén được của thuật toán (algorithmic incompressibility). Một chuỗi nhị phân $s$ có độ dài $n$ được coi là ngẫu nhiên nếu độ phức tạp Kolmogorov của nó xấp xỉ bằng chính độ dài của nó:

C(s) \ge n - c

trong đó $c$ là một hằng số nhỏ độc lập với $n$ . Một chuỗi ngẫu nhiên là chuỗi không chứa đựng bất kỳ quy luật hay cấu trúc lặp lại nào có thể được nén lại thành một chương trình ngắn hơn.

Sự tồn tại của các chuỗi không nén được

Bằng nguyên lý chuồng bồ câu (Pigeonhole Principle), ta có thể chứng minh sự tồn tại tất yếu của các chuỗi không thể nén được. Số lượng chương trình nhị phân có độ dài nhỏ hơn $n$ là:

\sum_{i=0}^{n-1} 2^i = 2^n - 1

Do tổng số chuỗi nhị phân có độ dài chính xác bằng $n$ là $2^n$ , nên số lượng chương trình ngắn hơn luôn ít hơn số lượng chuỗi cần biểu diễn ít nhất 1 chương trình. Do đó, với mọi độ dài $n$ , luôn tồn tại ít nhất một chuỗi có $C(s) \ge n$ , và phần lớn các chuỗi nhị phân đều có độ phức tạp xấp xỉ $n$ .

Mối quan hệ giữa Độ phức tạp Kolmogorov và Entropy Shannon

Lý thuyết thông tin cổ điển của Claude Shannon đo lường lượng thông tin trung bình của một biến ngẫu nhiên theo phân phối xác suất, trong khi độ phức tạp Kolmogorov đo lường lượng thông tin nội tại của một đối tượng cụ thể duy nhất.

Sự hội tụ tiệm cận

Thomas M. Cover và Joy A. Thomas (2005) trong Elements of Information Theory đã làm sáng tỏ mối liên kết toán học giữa hai trường phái này. Cho một dãy các biến ngẫu nhiên độc lập đồng phân phối (i.i.d.) $X_1, X_2, \dots, X_n$ tuân theo phân phối xác suất $P$ với Entropy Shannon là $H(P)$ . Giới hạn kỳ vọng toán học của độ phức tạp Kolmogorov trên mỗi ký tự sẽ hội tụ chính xác về Entropy Shannon khi độ dài chuỗi tiến tới vô cùng:

\lim_{n \to \infty} \frac{1}{n} \mathbb{E}[C(X_1 X_2 \dots X_n)] = H(P)

Tiêu chí so sánh	Entropy Shannon $H(X)$	Độ phức tạp Kolmogorov $K(s)$
Đối tượng nghiên cứu	Biến ngẫu nhiên và phân phối xác suất tập thể	Một chuỗi ký tự hoặc đối tượng dữ liệu đơn lẻ
Bản chất đo lường	Lượng thông tin trung bình thống kê	Độ dài chương trình sinh ngắn nhất
Khả năng tính toán	Hoàn toàn tính toán được nếu biết phân phối	Không thể tính toán được về mặt thuật toán
Ràng buộc tiên nghiệm	Đòi hỏi giả định về không gian mẫu và phân phối	Phi tham số, không phụ thuộc phân phối xác suất

Ứng dụng lý thuyết và Thực tiễn

Mặc dù không thể tính toán tuyệt đối, các nguyên lý rút ra từ độ phức tạp Kolmogorov đã thúc đẩy nhiều bước tiến quan trọng trong khoa học hiện đại.

Suy luận quy nạp Solomonoff và Trí tuệ nhân tạo

Ray Solomonoff (1964) đã phát triển lý thuyết quy nạp hình thức bằng cách gán cho mỗi mô hình giả thuyết một xác suất tiên nghiệm tỷ lệ nghịch với lũy thừa của độ phức tạp Kolmogorov của nó. Đây là sự toán học hóa chuẩn xác của Nguyên lý Dao cạo Occam: mô hình đơn giản nhất giải thích được dữ liệu quan sát chính là mô hình có xác suất đúng cao nhất. Mô hình AIXI của Marcus Hutter trong lý thuyết học tăng cường tổng quát là sự hiện thực hóa trực tiếp của nguyên lý quy nạp Solomonoff.

Nguyên lý độ dài mô tả tối thiểu (MDL)

Trong học máy và thống kê suy luận, Jorma Rissanen đã phát triển Nguyên lý độ dài mô tả tối thiểu (Minimum Description Length - MDL). MDL xấp xỉ độ phức tạp Kolmogorov thực tế bằng cách chọn mô hình sao cho tổng độ dài mô tả của mô hình cộng với độ dài mô tả của dữ liệu sai lệch khi dùng mô hình đó là nhỏ nhất, giúp giải quyết triệt để hiện tượng quá khớp (overfitting).

Khoảng cách thông tin chuẩn hóa (NID) và Nén dữ liệu

Ming Li và Paul Vitanyi (2019) trong công trình tổng kết của mình đã giới thiệu Khoảng cách thông tin chuẩn hóa (Normalized Information Distance - NID), một thước đo khoảng cách vạn năng giữa hai đối tượng dựa trên độ phức tạp Kolmogorov có điều kiện. Trong thực tế, các thuật toán nén dữ liệu tiêu chuẩn (như Gzip, LZMA) được sử dụng để xấp xỉ NID thành Khoảng cách nén chuẩn hóa (Normalized Compression Distance - NCD), cho phép phân cụm dữ liệu tự động trên văn bản, mã nguồn, âm nhạc và trình tự chuỗi gen sinh học mà không cần tri thức chuyên ngành.