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."
[1]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,
[2], 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,
[3] 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".
[4]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.