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, rằng tất cả các khái niệm ngẫu nhiên này là khác nhau.

Tham khảo