Vấn đề nén dữ liệu, ở dạng đơn giản nhất, có thể liên quan đến các con số và ký hiệu của chúng. Các số có thể được biểu thị bằng chữ số ("mười một" cho số 11), biểu thức toán học ("hai phần hai mươi" cho 1048576), biểu thức chuỗi ("năm chín" cho 99999), tên riêng ("số của quái thú" cho 666, "năm mất của Turing" cho năm 1954), hoặc sự kết hợp tùy tiện của chúng. Bất kỳ chỉ định nào cũng phù hợp để người đối thoại có thể xác định rõ ràng chúng ta đang nói đến con số nào. Rõ ràng, hãy nói với người đối thoại của bạn "giai thừa của tám" hiệu quả hơn ký hiệu tương đương "bốn mươi nghìn ba trăm hai mươi". Ở đây nảy sinh một câu hỏi logic: ký hiệu ngắn nhất cho một số đã cho là gì?
Nhà triết học Bertrand Russell xuất bản năm 1908 , liên quan đến vấn đề ký hiệu số từ phía đối diện: Số nhỏ nhất không yêu cầu tám mươi chữ cái là bao nhiêu?
Một con số như vậy phải tồn tại: từ 3480 chữ cái và dấu cách tiếng Nga, bạn chỉ có thể tạo thành 3480 ký hiệu, có nghĩa là sử dụng 3480 chữ cái, bạn có thể chỉ định không quá XNUMX số. Điều này có nghĩa là không thể chỉ định một số nhất định không quá XNUMX theo cách này.
Điều này có nghĩa là con số này sẽ tương ứng với chỉ định "con số nhỏ nhất mà tám mươi chữ cái là không đủ", chỉ có 78 chữ cái! Một mặt, con số này phải tồn tại; mặt khác, nếu con số này tồn tại thì tên của nó không tương ứng với nó. Nghịch lý!
Cách dễ dàng nhất để loại bỏ nghịch lý này là đề cập đến tính không chính thức của các ký hiệu bằng lời nói. Giống như, nếu chỉ cho phép một tập hợp các biểu thức được xác định cụ thể trong ký hiệu, thì "con số nhỏ nhất mà tám mươi chữ cái là không đủ" sẽ không phải là một ký hiệu hợp lệ, trong khi các ký hiệu thực tế hữu ích như "giai thừa của tám" sẽ vẫn được chấp nhận.
Có cách nào chính thức để mô tả trình tự (thuật toán) hành động trên các con số không? Có và rất nhiều - chúng được gọi là ngôn ngữ lập trình. Thay vì ký hiệu bằng lời nói, chúng tôi sẽ sử dụng các chương trình (ví dụ: bằng Python) hiển thị các số được yêu cầu. Ví dụ: đối với năm số chín, chương trình phù hợp print("9"*5). Chúng tôi sẽ tiếp tục quan tâm đến chương trình ngắn nhất cho một con số nhất định. Độ dài của một chương trình như vậy được gọi là số; đó là giới hạn lý thuyết mà một số nhất định có thể được nén.
Thay vì nghịch lý của Berry, bây giờ chúng ta có thể xem xét một nghịch lý tương tự: Số nhỏ nhất mà chương trình kilobyte không đủ để xuất ra là bao nhiêu?
Chúng ta sẽ lập luận theo cách tương tự như trước: có 2561024 văn bản kilobyte, có nghĩa là các chương trình kilobyte có thể xuất ra không quá 2561024 số. Điều này có nghĩa là một số nhất định không lớn hơn 2561024 không thể được suy ra theo cách này.
Nhưng hãy viết một chương trình bằng Python tạo ra tất cả các văn bản kilobyte có thể có, chạy chúng để thực thi và nếu chúng xuất ra một số thì hãy thêm số này vào từ điển của những văn bản có thể truy cập được. Sau khi kiểm tra tất cả 2561024 khả năng, bất kể mất bao lâu, chương trình sẽ tìm số nhỏ nhất còn thiếu trong từ điển và in ra số đó. Có vẻ như rõ ràng là một chương trình như vậy sẽ vừa với một kilobyte mã - và sẽ xuất ra chính con số mà chương trình kilobyte không thể xuất ra!
Bây giờ có gì đáng chú ý? Nó không còn có thể được quy cho tính không chính thức của ký hiệu!
Nếu bạn bối rối vì thực tế là chương trình của chúng tôi sẽ cần một lượng bộ nhớ cực lớn để hoạt động - một từ điển (hoặc mảng bit) gồm 2561024 phần tử - thì bạn có thể làm điều tương tự mà không cần nó: lần lượt cho mỗi số trong số 2561024 số , đi qua tất cả 2561024 chương trình có thể, cho đến khi không còn chương trình nào phù hợp. Việc tìm kiếm như vậy sẽ kéo dài rất lâu không thành vấn đề: sau khi kiểm tra ít hơn (2561024)2 cặp từ số và chương trình, nó sẽ kết thúc và tìm thấy con số rất đáng trân trọng đó.
Hay nó sẽ không kết thúc? Thật vậy, trong số tất cả các chương trình sẽ được thử, sẽ có while True: pass (và các chức năng tương tự của nó) - và vấn đề sẽ không đi xa hơn việc thử nghiệm một chương trình như vậy!
Không giống như nghịch lý của Berry, trong đó việc đánh bắt nằm ở tính không chính thức của ký hiệu, trong trường hợp thứ hai, chúng ta có một cách diễn đạt được ngụy trang khéo léo. . Thực tế là không thể xác định đầu ra của nó từ một chương trình trong một thời gian hữu hạn. Đặc biệt, độ phức tạp Kolmogorov : không có thuật toán nào cho phép, đối với một số nhất định, tìm độ dài của chương trình ngắn nhất in ra số này; điều đó có nghĩa là không có lời giải nào cho bài toán của Berry - tìm độ dài của ký hiệu bằng lời ngắn nhất cho một số cho trước.
Nguồn: www.habr.com