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.