Khác biệt giữa bản sửa đổi của “Lý thuyết thông tin thuật toán”

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'' &nbsp; - &nbsp; ''c'' . Có thể chỉ ra rằng hầu hết mọi chuỗi (theo quan điểm của [[Độ đo|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 <ref> Yongge Wang: Tính ngẫu nhiên và phức tạp. Luận án Tiến sĩ, 1996. [http://webpages.uncc.edu/yonwang/papers/thesis.pdf http://webpages.uncc.edu/yonwang/ con / theory.pdf] </ref> rằng tất cả các khái niệm ngẫu nhiên này là khác nhau.

 

 

[[Thể loại:Lý thuyết thông tin]]