Lý thuyết thông tin thuật toán

Lý thuyết thông tin thuật toán là một lĩnh vực của lý thuyết thông tin và khoa học máy tính liên quan đến mối quan hệ giữa tính toán và thông tin. Theo Gregory Chaitin, đó là "kết quả của việc đưa lý thuyết thông tin của Shannon và lý thuyết tính toán của Turing vào một bình lắc cocktail và lắc mạnh."

Lý thuyết thông tin thuật toán chủ yếu nghiên cứu các biện pháp phức tạp trên các chuỗi (hoặc các cấu trúc dữ liệu khác). Bởi vì hầu hết các đối tượng toán học có thể được mô tả dưới dạng chuỗi hoặc là giới hạn của chuỗi chuỗi, nên nó có thể được sử dụng để nghiên cứu nhiều loại đối tượng toán học, bao gồm cả số nguyên.

Lý thuyết được thành lập bởi Ray Solomonoff,, người đã công bố những ý tưởng cơ bản mà lĩnh vực này dựa trên phát minh của ông về xác suất thuật toán cách thức khắc phục các vấn đề nghiêm trọng liên quan đến việc áp dụng các quy tắc của Bayes trong thống kê. Ông lần đầu tiên mô tả kết quả của mình tại một Hội nghị tại Caltech năm 1960, và trong một báo cáo, tháng 2 năm 1960, "Báo cáo sơ bộ về một lý thuyết chung về suy luận quy nạp".

Lý thuyết thông tin thuật toán sau đó được phát triển độc lập bởi Andrey Kolmogorov, vào năm 1965 và Gregory Chaitin, vào khoảng năm 1966. Có một số biến thể của thông tin thuật toán hoặc độ phức tạp Kolmogorov; một chương trình được sử dụng rộng rãi nhất dựa trên các chương trình tự phân định và chủ yếu là do Leonid Levin (1974).

Per Martin-Löf cũng đóng góp đáng kể vào lý thuyết thông tin về các chuỗi vô hạn. Một cách tiếp cận tiên đề cho lý thuyết thông tin thuật toán dựa trên các tiên đề Blum (Blum 1967) đã được Mark Burgin giới thiệu trong một bài báo được trình bày để xuất bản bởi Andrey Kolmogorov (Burgin 1982). Cách tiếp cận tiên đề bao gồm các công thức khác.

Tổng quan

Lý thuyết thông tin thuật toán chủ yếu nghiên cứu các biện pháp phức tạp trên các chuỗi (hoặc các cấu trúc dữ liệu khác). Bởi vì hầu hết các đối tượng toán học có thể được mô tả dưới dạng chuỗi hoặc là giới hạn của chuỗi chuỗi, nên nó có thể được sử dụng để nghiên cứu nhiều loại đối tượng toán học, bao gồm cả số nguyên.

Một cách không chính thức, từ quan điểm của lý thuyết thông tin thuật toán, nội dung thông tin của một chuỗi tương đương với độ dài của biểu diễn tự chứa có thể nén nhất của chuỗi đó. Một đại diện khép kín về cơ bản là một chương trình, trong một số ngôn ngữ lập trình phổ quát cố định nhưng không liên quan, thì khi chạy, sẽ xuất ra chuỗi gốc.

Từ quan điểm này, một bách khoa toàn thư 3000 trang thực sự chứa ít thông tin hơn 3000 trang của các chữ cái hoàn toàn ngẫu nhiên, mặc dù thực tế là bách khoa toàn thư hữu ích hơn nhiều. Điều này là do để xây dựng lại toàn bộ chuỗi các chữ cái ngẫu nhiên, người ta phải biết, ít nhiều, mỗi chữ cái là gì. Mặt khác, nếu mọi nguyên âm được loại bỏ khỏi bách khoa toàn thư, một người có kiến thức hợp lý về ngôn ngữ tiếng Anh có thể tái tạo lại nó, giống như người Anh có thể tái tạo lại câu "Ths sntnc hs lw nfrmtn cntnt" từ ngữ cảnh và phụ âm.

Không giống như lý thuyết thông tin cổ điển, lý thuyết thông tin thuật toán đưa ra các định nghĩa chính thức, nghiêm ngặt về một chuỗi ngẫu nhiên và một chuỗi vô hạn ngẫu nhiên không phụ thuộc vào trực giác vật lý hoặc triết học về thuyết không xác định hoặc khả năng. (Tập hợp các chuỗi ngẫu nhiên phụ thuộc vào sự lựa chọn của máy Turing phổ dụng được sử dụng để xác định độ phức tạp Kolmogorov, nhưng bất kỳ lựa chọn nào cũng cho kết quả tiệm cận giống hệt nhau vì độ phức tạp Kolmogorov của chuỗi là bất biến phụ thuộc vào hằng số phụ thuộc máy móc. Vì lý do này, tập hợp các chuỗi vô hạn ngẫu nhiên không phụ thuộc vào sự lựa chọn của máy vạn năng.)

Một số kết quả của lý thuyết thông tin thuật toán, chẳng hạn như định lý không hoàn chỉnh của Chaitin, dường như thách thức các trực giác toán học và triết học phổ biến. Đáng chú ý nhất trong số này là việc xây dựng liên tục Chaitin của Ω, một số thực mà diễn tả xác suất mà một máy Turing phổ tự phân chia ranh giới sẽ ngừng khi đầu vào của nó được cung cấp bởi flips một xu công bằng (đôi khi coi là xác suất mà một ngẫu nhiên chương trình máy tính cuối cùng sẽ dừng lại). Mặc dù Ω có thể dễ dàng xác định, trong bất kỳ phù hợp axiomatizable lý thuyết duy nhất có thể tính hữu hạn nhiều chữ số của Ω, vì vậy nó là ở một số cảm giác không thể biết, cung cấp một giới hạn tuyệt đối về kiến thức đó là gợi nhớ đến không đầy đủ Định lý Gödel. Mặc dù các chữ số của Ω không thể được xác định, nhiều tài sản của Ω được biết; ví dụ, nó là một chuỗi ngẫu nhiên theo thuật toán và do đó các chữ số nhị phân của nó được phân bố đều (thực tế nó là bình thường).

Lịch sử

Lý thuyết thông tin thuật toán được thành lập bởi Ray Solomonoff,, người đã công bố những ý tưởng cơ bản mà lĩnh vực này dựa trên phát minh của ông về xác suất thuật toán cách khắc phục các vấn đề nghiêm trọng liên quan đến việc áp dụng các quy tắc của Bayes trong thống kê. Ông lần đầu tiên mô tả kết quả của mình tại một Hội nghị tại Caltech năm 1960, và trong một báo cáo, tháng 2 năm 1960, "Báo cáo sơ bộ về một lý thuyết chung về suy luận quy nạp". Lý thuyết thông tin thuật toán sau đó được phát triển độc lập bởi Andrey Kolmogorov, vào năm 1965 và Gregory Chaitin, vào khoảng năm 1966.

Có một số biến thể của thông tin thuật toán hoặc độ phức tạp Kolmogorov; một chương trình được sử dụng rộng rãi nhất dựa trên các chương trình tự phân định và chủ yếu là do Leonid Levin (1974). Per Martin-Löf cũng đóng góp đáng kể vào lý thuyết thông tin về các chuỗi vô hạn. Một cách tiếp cận tiên đề đối với lý thuyết thông tin thuật toán dựa trên các tiên đề Blum (Blum 1967) đã được Mark Burgin giới thiệu trong một bài báo được trình bày để xuất bản bởi Andrey Kolmogorov (Burgin 1982). Cách tiếp cận tiên đề bao gồm các cách tiếp cận khác trong lý thuyết thông tin thuật toán. Có thể coi các biện pháp khác nhau của thông tin thuật toán là các trường hợp cụ thể của các biện pháp xác định tiên đề của thông tin thuật toán. Thay vì chứng minh các định lý tương tự, chẳng hạn như định lý bất biến cơ bản, đối với từng biện pháp cụ thể, có thể dễ dàng suy ra tất cả các kết quả như vậy từ một định lý tương ứng đã được chứng minh trong thiết lập tiên đề. Đây là một lợi thế chung của phương pháp tiên đề trong toán học. Cách tiếp cận tiên đề cho lý thuyết thông tin thuật toán đã được phát triển thêm trong cuốn sách (Burgin 2005) và áp dụng cho các số liệu phần mềm (Burgin và Debnath, 2003; Debnath và Burgin, 2003).

Định nghĩa chính xác

Một chuỗi nhị phân được gọi là ngẫu nhiên nếu độ phức tạp Kolmogorov của chuỗi ít nhất là độ dài của chuỗi. Một đối số đếm đơn giản cho thấy rằng một số chuỗi có độ dài bất kỳ là ngẫu nhiên và hầu như tất cả các chuỗi đều rất gần với ngẫu nhiên. Do độ phức tạp Kolmogorov phụ thuộc vào sự lựa chọn cố định của máy Turing phổ dụng (không chính thức, một "ngôn ngữ mô tả" cố định trong đó "mô tả" được đưa ra), nên bộ sưu tập các chuỗi ngẫu nhiên phụ thuộc vào sự lựa chọn của máy vạn năng cố định. Tuy nhiên, toàn bộ tập hợp các chuỗi ngẫu nhiên, có các thuộc tính tương tự bất kể máy cố định, vì vậy người ta có thể (và thường không) nói về các thuộc tính của chuỗi ngẫu nhiên như một nhóm mà không cần phải chỉ định trước một máy phổ quát.

Một chuỗi nhị phân vô hạn được gọi là ngẫu nhiên nếu, đối với một số hằng số c, với mọi n, độ phức tạp Kolmogorov của đoạn ban đầu có độ dài n của chuỗi ít nhất là n   -   c. Có thể chỉ ra rằng hầu hết mọi chuỗi (theo quan điểm của thước đo tiêu chuẩn - "đồng tiền công bằng" hoặc thước đo Lebesgue, không gian của chuỗi nhị phân vô hạn) là ngẫu nhiên. Ngoài ra, vì có thể chỉ ra rằng độ phức tạp Kolmogorov so với hai máy vạn năng khác nhau khác nhau nhiều nhất là một hằng số, tập hợp các chuỗi vô hạn ngẫu nhiên không phụ thuộc vào sự lựa chọn của máy vạn năng (trái ngược với chuỗi hữu hạn). Định nghĩa về tính ngẫu nhiên này thường được gọi là tính ngẫu nhiên của Martin-Löf, sau Per Martin-Löf, để phân biệt nó với các khái niệm ngẫu nhiên tương tự khác. Đôi khi nó còn được gọi là ngẫu nhiên 1 để phân biệt với các khái niệm ngẫu nhiên mạnh hơn khác (2 ngẫu nhiên, 3 ngẫu nhiên, v.v.). Ngoài các khái niệm ngẫu nhiên Martin-Löf, còn có các ngẫu nhiên đệ quy, ngẫu nhiên Schnorr và ngẫu nhiên Kurtz, v.v. Yongge Wang đã chỉ ra rằng tất cả các khái niệm ngẫu nhiên này là khác nhau.