ในทฤษฎีสารสนเทศเชิงอัลกอริทึม (สาขาย่อยของวิทยาศาสตร์คอมพิวเตอร์และคณิตศาสตร์ ) ความซับซ้อนของ Kolmogorovของวัตถุ เช่น ข้อความ คือความยาวของโปรแกรมคอมพิวเตอร์ ที่สั้นที่สุด (ในภาษาโปรแกรม ที่กำหนดไว้ล่วงหน้า ) ที่สร้างวัตถุนั้นเป็นผลลัพธ์ มันคือการวัด ทรัพยากร การคำนวณที่จำเป็นในการระบุวัตถุ และยังรู้จักกันในชื่อความซับซ้อนเชิงอัลกอริทึมความซับซ้อนของ Solomonoff–Kolmogorov–Chaitin ความซับซ้อนของขนาดโปรแกรม ความซับซ้อนเชิงพรรณนาหรือเอนโทรปีเชิงอัลกอริทึมชื่อนี้ตั้งตามAndrey Kolmogorovผู้ซึ่งตีพิมพ์ผลงานเกี่ยวกับเรื่องนี้เป็นครั้งแรกในปี 1963 ^{[ 1 ] [หมายเหตุ 1 ]}และเป็นการสรุปทั่วไปของทฤษฎีสารสนเทศแบบคลาสสิก

แนวคิดเรื่องความซับซ้อนของ Kolmogorov สามารถนำมาใช้เพื่อระบุและพิสูจน์ผลลัพธ์ที่เป็นไปไม่ได้ ซึ่งคล้ายคลึงกับข้อโต้แย้งแนวทแยงของ Cantorทฤษฎีบทความไม่สมบูรณ์ของ Gödelและปัญหาการหยุดทำงานของ Turingโดยเฉพาะอย่างยิ่ง ไม่มีโปรแกรมP ใด ที่คำนวณขอบล่างสำหรับความซับซ้อนของ Kolmogorov ของแต่ละข้อความแล้วสามารถส่งคืนค่าที่ใหญ่กว่า ความยาว ของPเองได้ (ดูหัวข้อ§ ทฤษฎีบทความไม่สมบูรณ์ของ Chaitin ) ดังนั้นจึงไม่มีโปรแกรมใดโปรแกรมเดียวที่สามารถคำนวณความซับซ้อนของ Kolmogorov ที่แน่นอนสำหรับข้อความจำนวนอนันต์ได้ 

ทฤษฎีสารสนเทศเชิงอัลกอริทึมเป็นสาขาหนึ่งของวิทยาการคอมพิวเตอร์ที่ศึกษาความซับซ้อนของ Kolmogorov และมาตรวัดความซับซ้อนอื่นๆ บนสตริง (หรือโครงสร้างข้อมูล อื่นๆ )

แนวคิดและทฤษฎีของความซับซ้อนของ Kolmogorov นั้นมีพื้นฐานมาจากทฤษฎีบทสำคัญที่ค้นพบครั้งแรกโดยRay Solomonoffซึ่งตีพิมพ์ในปี 1960 โดยอธิบายไว้ใน "รายงานเบื้องต้นเกี่ยวกับทฤษฎีทั่วไปของการอนุมานแบบอุปนัย" ^{[ 5 ]}ซึ่งเป็นส่วนหนึ่งของการคิดค้นความน่าจะเป็นเชิงอัลกอริทึม ของเขา เขาได้ให้คำอธิบายที่สมบูรณ์ยิ่งขึ้นในสิ่งพิมพ์ปี 1964 ของเขา "ทฤษฎีอย่างเป็นทางการของการอนุมานแบบอุปนัย" ตอนที่ 1 และตอนที่ 2 ในInformation and Control ^{[ 6 ] [ 7 ]}

ต่อมา Andrey Kolmogorov ได้ตีพิมพ์ทฤษฎีบทนี้ในProblems Inform. Transmission อย่างอิสระ ในปี 1965 ^{[ 8 ]} Gregory Chaitinก็ได้นำเสนอทฤษฎีบทนี้ในJournal of the ACM เช่นกัน โดยบทความของ Chaitin ถูกส่งในเดือนตุลาคม 1966 และแก้ไขในเดือนธันวาคม 1968 และอ้างอิงถึงบทความของ Solomonoff และ Kolmogorov ^{[ 9 ]}

ทฤษฎีบทนี้กล่าวว่า ในบรรดาอัลกอริธึมที่ใช้ถอดรหัสสตริงจากคำอธิบาย (รหัส) นั้น จะมีอัลกอริธึมที่ดีที่สุดอยู่หนึ่งตัว อัลกอริธึมนี้สำหรับสตริงทุกตัว จะอนุญาตให้ใช้รหัสที่สั้นได้เท่ากับที่อัลกอริธึมอื่นๆ อนุญาต โดยมีค่าคงที่บวกเพิ่มเข้าไป ซึ่งค่าคงที่นี้ขึ้นอยู่กับอัลกอริธึมนั้นๆ แต่ไม่ขึ้นอยู่กับสตริงเอง โซโลมอนอฟใช้อัลกอริธึมนี้และความยาวของรหัสที่อัลกอริธึมนี้อนุญาต เพื่อกำหนด "ความน่าจะเป็นสากล" ของสตริง ซึ่งสามารถใช้เป็นพื้นฐานในการอนุมานแบบอุปนัยของตัวเลขถัดไปในสตริงได้ โคลโมโกโรฟใช้ทฤษฎีบทนี้เพื่อกำหนดฟังก์ชันต่างๆ ของสตริง รวมถึงความซับซ้อน ความสุ่ม และข้อมูล

เมื่อ Kolmogorov ทราบถึงงานของ Solomonoff เขาจึงยอมรับความสำคัญของ Solomonoff ^{[ 10 ]}เป็นเวลาหลายปีที่งานของ Solomonoff เป็นที่รู้จักในสหภาพโซเวียตมากกว่าในโลกตะวันตก อย่างไรก็ตาม ความเห็นพ้องโดยทั่วไปในชุมชนวิทยาศาสตร์คือการเชื่อมโยงความซับซ้อนประเภทนี้กับ Kolmogorov ซึ่งให้ความสำคัญกับความสุ่มของลำดับ ในขณะที่ความน่าจะเป็นเชิงอัลกอริทึมกลับเชื่อมโยงกับ Solomonoff ซึ่งมุ่งเน้นไปที่การทำนายโดยใช้การคิดค้นการแจกแจงความน่าจะเป็นก่อนหน้าสากล พื้นที่ที่กว้างขึ้นซึ่งครอบคลุมความซับซ้อนเชิงพรรณนาและความน่าจะเป็นมักเรียกว่าความซับซ้อนของ Kolmogorov นักวิทยาศาสตร์คอมพิวเตอร์Ming Liถือว่านี่เป็นตัวอย่างของปรากฏการณ์ Matthew : "...สำหรับทุกคนที่มีอยู่ จะได้รับเพิ่มมากขึ้น..." ^{[ 11 ]}

นอกจากนี้ยังมีรูปแบบอื่นๆ ของความซับซ้อนของ Kolmogorov หรือข้อมูลเชิงอัลกอริทึมอีกหลายแบบ รูปแบบที่ใช้กันอย่างแพร่หลายที่สุดคือรูปแบบที่อิงตามโปรแกรมที่กำหนดขอบเขตด้วยตนเองซึ่งส่วนใหญ่เป็นผลงานของLeonid Levin (1974)

แนวทางเชิงสัจพจน์สำหรับความซับซ้อนของ Kolmogorov โดยอิงตามสัจพจน์ของ Blum (Blum 1967) ได้รับการนำเสนอโดย Mark Burgin ในบทความที่ Andrey Kolmogorov นำเสนอเพื่อตีพิมพ์^{[ 12 ]}

เราเขียน${\displaystyle K(x,y)}$จะเป็น${\displaystyle K((x,y))}$, ที่ไหน${\displaystyle (x,y)}$หมายถึงวิธีการเขียนโค้ดแบบตายตัวสำหรับทูเปิลของสตริง x และ y

def kolmogorov_complexity ( s : str ): for i = 1 to infinity : for each string p of length exactly i if is_valid_program ( p ) and evaluate ( p ) == s return i

def kolmogorov_complexity ( s : str )

def generate_complex_string (): str for i = 1 to infinity : for each string s of length exactly i if kolmogorov_complexity ( s ) >= 8000000000 return s

กฎลูกโซ่สำหรับความซับซ้อนของ Kolmogorov

กฎลูกโซ่^{[ 15 ]}สำหรับความซับซ้อนของ Kolmogorov ระบุว่ามีค่าคงที่c อยู่ เช่นนั้นสำหรับXและY ทั้งหมด :

${\displaystyle K(X,Y)=K(X)+K(Y|X)+c\cdot max(1,log(K(X,Y)))}$.

ข้อความดัง กล่าวระบุว่า โปรแกรมที่สั้นที่สุดที่สร้างXและY ขึ้นมาใหม่ นั้น จะมีขนาดใหญ่กว่าโปรแกรมที่สร้างX ขึ้นมาใหม่ และโปรแกรมที่สร้างY ขึ้นมาใหม่ โดยกำหนดให้X เพียงแค่ค่าลอการิทึมเท่านั้น โดยใช้ข้อความนี้ เราสามารถกำหนดสิ่งที่เทียบเคียงได้กับข้อมูลร่วมกันสำหรับความซับซ้อนของ Kolmogorovได้

การคำนวณขอบเขตบนสำหรับK ( s ) นั้นทำได้ง่าย  เพียงแค่บีบอัดสตริงsด้วยวิธีการใดวิธีการหนึ่ง จากนั้นเขียนโปรแกรมคลายการบีบอัดที่เหมาะสมในภาษาที่เลือก นำโปรแกรมคลายการบีบอัดมาต่อกับสตริงที่บีบอัดแล้ว และวัดความยาวของสตริงที่ได้ ซึ่งก็คือ ขนาดของไฟล์เก็บถาวรแบบแตกไฟล์ได้เองในภาษาที่กำหนดนั่นเอง

สตริงsสามารถบีบอัดได้ด้วยจำนวนcถ้ามีคำอธิบายที่มีความยาวไม่เกิน | s | − cบิต ซึ่งเทียบเท่ากับการกล่าวว่าK ( s ) ≤ | s | − cมิฉะนั้นsจะไม่สามารถบีบอัดได้ด้วยcสตริงที่ไม่สามารถบีบอัดได้ด้วย c จะเรียกว่าไม่สามารถบีบอัดได้  เลย – ตามหลักการรังนกพิราบซึ่งใช้ได้เพราะสตริงที่บีบอัดแล้วทุกสตริงจะแปลงเป็นสตริงที่ไม่ถูกบีบอัดได้เพียงสตริงเดียวสตริงที่ไม่สามารถบีบอัดได้จึงต้องมีอยู่ เนื่องจากมีสตริง 2n ^บิตที่มีความยาวnแต่ มีสตริงที่สั้นกว่าเพียง ²ⁿ − 1 สตริงเท่านั้น นั่นคือสตริงที่มีความยาวน้อยกว่าn (เช่น มีความยาว 0, 1, ..., n  −  1) ^{[หมายเหตุ 7 ]}

ด้วยเหตุผลเดียวกัน สตริงส่วนใหญ่จึงมีความซับซ้อนในแง่ที่ว่าไม่สามารถบีบอัดได้อย่างมีนัยสำคัญ – ค่า K ( s ) ของสตริงเหล่านั้นจะไม่เล็กกว่า | s | มากนัก ซึ่งก็คือความยาวของsในหน่วยบิต เพื่อให้เข้าใจได้ชัดเจนยิ่งขึ้น ให้กำหนดค่าn ไว้ค่า หนึ่ง จะมี สตริงบิตที่มีความยาว nจำนวน²ⁿ สตริง การ แจกแจง ความน่าจะเป็นแบบเอกรูป บนพื้นที่ของสตริงบิตเหล่านี้จะ กำหนดน้ำหนักที่เท่ากันเป๊ะคือ 2 ^{− n}ให้กับแต่ละสตริงที่มีความยาวn

ทฤษฎีบท : ด้วยการแจกแจงความน่าจะเป็นแบบเอกรูปบนปริภูมิของสตริงบิตที่มีความยาวnความน่าจะเป็นที่สตริงนั้นไม่สามารถบีบอัดได้ด้วยc จะมี ค่าอย่างน้อย1 − 2 ^{− c +1} + 2 ^{− n}

เพื่อพิสูจน์ทฤษฎีบทนี้ โปรดสังเกตว่าจำนวนคำอธิบายที่มีความยาวไม่เกินn − cนั้นกำหนดโดยอนุกรมเรขาคณิต:

เหลืออยู่อย่างน้อย

สตริงบิตที่มีความยาวnซึ่งไม่สามารถบีบอัดได้ด้วยc ในการหาความน่าจะเป็น ให้หารด้วย²ⁿ

จากทฤษฎีบทข้างต้น ( §  การบีบอัด ) สตริงส่วนใหญ่มีความซับซ้อนในแง่ที่ว่าไม่สามารถอธิบายได้ในรูปแบบที่ "บีบอัด" ได้อย่างมีนัยสำคัญ อย่างไรก็ตาม ปรากฏว่าข้อเท็จจริงที่ว่าสตริงเฉพาะมีความซับซ้อนนั้นไม่สามารถพิสูจน์ได้อย่างเป็นทางการ หากความซับซ้อนของสตริงนั้นสูงกว่าเกณฑ์ที่กำหนด การกำหนดอย่างเป็นทางการที่แม่นยำมีดังนี้ ขั้นแรก กำหนดระบบสัจพจน์S เฉพาะ สำหรับจำนวนธรรมชาติระบบสัจพจน์นี้ต้องมีประสิทธิภาพมากพอที่จะทำให้ สามารถเชื่อมโยงสูตรF ในS กับข้อความยืนยัน A บางประการเกี่ยวกับความซับซ้อนของสตริงได้ การเชื่อมโยงนี้ต้องมีคุณสมบัติดังต่อไปนี้:

ถ้าF สามารถพิสูจน์ได้จากสัจพจน์ของSแล้ว ข้อความยืนยันA ที่สอดคล้องกัน จะต้องเป็นจริง การ "กำหนดรูปแบบอย่างเป็นทางการ" นี้สามารถทำได้โดยอาศัยการกำหนดหมายเลขแบบเกอเดล

ทฤษฎีบท : มีค่าคงที่L อยู่ค่าหนึ่ง (ซึ่งขึ้นอยู่กับSและการเลือกภาษาอธิบายเท่านั้น) โดยที่ไม่มีสตริงs ใดๆ ที่ทำให้ข้อความนั้น เป็นจริง

${\displaystyle K(s)\geq L}$   (ตามที่กำหนดไว้ในS )

สามารถพิสูจน์ได้^{ภายใน} S [ ^{16 ] [ 17 ]}

แนวคิดการพิสูจน์ : การพิสูจน์ผลลัพธ์นี้จำลองมาจากโครงสร้างแบบอ้างอิงตนเองที่ใช้ในปรากฏการณ์ขัดแย้งของเบอร์รีเริ่มต้นด้วยการสร้างโปรแกรมที่แจงนับการพิสูจน์ภายในSและกำหนดขั้นตอนPซึ่งรับอินพุตเป็นจำนวนเต็มLและพิมพ์สตริงxที่อยู่ในหลักฐานการพิสูจน์ภายในSของข้อความK ( x ) ≥ Lโดยการตั้งค่าLให้มากกว่าความยาวของขั้นตอนP นี้ เราจะได้ว่าความยาวที่จำเป็นของโปรแกรมในการพิมพ์xตามที่ระบุไว้ในK ( x ) ≥ Lซึ่งอย่างน้อยที่สุดคือLนั้น น้อยกว่าจำนวนLนับตั้งแต่สตริงxถูกพิมพ์โดยขั้นตอนPนี่คือข้อขัดแย้ง ดังนั้นจึงเป็นไปไม่ได้ที่ระบบการพิสูจน์Sจะพิสูจน์K ( x ) ≥ LสำหรับL ที่ มีขนาดใหญ่มาก โดยเฉพาะอย่างยิ่งสำหรับLที่มากกว่าความยาวของขั้นตอนP (ซึ่งมีค่าจำกัด)

การพิสูจน์ :

เราสามารถค้นหาการแจงนับที่มีประสิทธิภาพของบทพิสูจน์เชิงรูปธรรมทั้งหมดในSได้โดยใช้ขั้นตอนบางอย่าง

def nth_proof ( n : int )

ซึ่งรับค่าn เป็นอินพุต และส่งออกหลักฐานบางอย่าง ฟังก์ชันนี้จะแจงนับหลักฐานทั้งหมด บางส่วนเป็นหลักฐานสำหรับสูตรที่เราไม่สนใจในที่นี้ เนื่องจากหลักฐานที่เป็นไปได้ทั้งหมดในภาษาSจะถูกสร้างขึ้นสำหรับค่าn บาง ค่า บางส่วนเป็นสูตรความซับซ้อนในรูปแบบK ( s )  ≥ nโดยที่sและnเป็นค่าคงที่ในภาษาSมีขั้นตอนหนึ่ง 

def nth_proof_proves_complexity_formula ( n : int ): bool

ซึ่งจะกำหนดว่า การพิสูจน์ครั้งที่ nนั้นพิสูจน์สูตรความซับซ้อนK ( s )  ≥ L ได้จริงหรือ ไม่ สตริงsและจำนวนเต็มLนั้นสามารถคำนวณได้โดยใช้ขั้นตอนดังนี้: 

def string_nth_proof ( n : int )

def complexity_lower_bound_nth_proof ( n : int ): int

พิจารณาขั้นตอนต่อไปนี้:

def generate_provably_complex_string ( n : int ): for i = 1 to infinity : if nth_proof_proves_complexity_formula ( i ) and complexity_lower_bound_nth_proof ( i ) ≥ n return string_nth_proof ( i )

เมื่อกำหนด${\displaystyle n}$ขั้นตอนนี้จะลองพิสูจน์ทุกวิธีจนกว่าจะพบสตริงและการพิสูจน์ในระบบที่เป็นทางการSของสูตร${\displaystyle K(s)\geq L}$สำหรับบางคน${\displaystyle L\geq n}$หากไม่มีหลักฐานดังกล่าว กระบวนการก็จะวนซ้ำไปเรื่อยๆ

สุดท้ายนี้ ลองพิจารณาโปรแกรมที่ประกอบด้วยคำจำกัดความของขั้นตอนทั้งหมดเหล่านี้ และการเรียกใช้งานหลัก:

generate_provably_complex_string ( n ₀ )

โดยที่ค่าคงที่${\displaystyle n_{0}}$จะกำหนดในภายหลัง ความยาวโดยรวมของโครงการสามารถแสดงได้ดังนี้${\displaystyle U+log_{2}(n_{0})}$, ที่ไหน${\displaystyle U}$เป็นค่าคงที่บางอย่างและ${\displaystyle log_{2}(n_{0})}$แสดงถึงความยาวของค่าจำนวนเต็ม${\displaystyle n_{0}}$ภายใต้สมมติฐานที่สมเหตุสมผลว่ามันถูกเข้ารหัสในรูปแบบเลขฐานสอง เราจะเลือก${\displaystyle n_{0}}$มีค่ามากกว่าความยาวของโปรแกรม กล่าวคือ มีค่าในลักษณะที่ว่า${\displaystyle n_{0}>U+log_{2}(n_{0})}$นี่เป็นความจริงอย่างชัดเจนสำหรับ${\displaystyle n_{0}}$มีขนาดใหญ่พอสมควร เนื่องจากด้านซ้ายมือเติบโตเป็นเส้นตรงใน${\displaystyle n_{0}}$ในขณะที่ฝั่งขวามือเติบโตแบบลอการิทึมใน${\displaystyle n_{0}}$จนถึงค่าคงที่ที่กำหนดไว้${\displaystyle U}$.

งั้นก็ไม่มีหลักฐานของแบบฟอร์มนั้น${\displaystyle K(s)\geq L}$" กับ${\displaystyle L\geq n_{0}}$สามารถหาได้ในSดังที่เห็นได้จากข้อโต้แย้งทางอ้อม : ถ้าcomplexity_lower_bound_nth_proof(i)สามารถส่งคืนค่าได้${\displaystyle \geq n_{0}}$จากนั้นลูปภายในgenerate_provably_complex_stringจะสิ้นสุดลงในที่สุด และกระบวนการนั้นจะส่งคืนสตริงsโดยที่

	${\displaystyle K(s)}$
≥	${\displaystyle n_{0}}$	โดยการก่อสร้างgenerate_provably_complex_string
>	${\displaystyle U+log_{2}(n_{0})}$	โดยการเลือกของ${\displaystyle n_{0}}$
≥	${\displaystyle K(s)}$	เนื่องจาก${\displaystyle s}$ได้รับการอธิบายโดยโปรแกรมที่มีความยาวดังกล่าว

นี่คือความขัดแย้งพิสูจน์แล้ว

ดังนั้น โปรแกรมข้างต้นจึงมีค่าที่เลือกไว้ดังนี้${\displaystyle n_{0}}$ต้องวนลูปไปเรื่อยๆ

แนวคิดที่คล้ายกันนี้ถูกนำมาใช้เพื่อพิสูจน์คุณสมบัติของ ค่าคงที่ ของChaitin

หลักการความยาวข้อความขั้นต่ำของการอนุมานเชิงสถิติและอุปนัยและการเรียนรู้ของเครื่องได้รับการพัฒนาโดยCS Wallaceและ DM Boulton ในปี 1968 MML เป็นแบบเบย์เซียน (กล่าวคือรวมความเชื่อก่อนหน้า) และทฤษฎีสารสนเทศ มีคุณสมบัติที่พึงประสงค์ของความไม่แปรผันทางสถิติ (กล่าวคือ การอนุมานจะแปลงไปเมื่อมีการกำหนดพารามิเตอร์ใหม่ เช่น จากพิกัดเชิงขั้วเป็นพิกัดคาร์ทีเซียน) ความสอดคล้องทางสถิติ (กล่าวคือ แม้แต่สำหรับปัญหาที่ยากมาก MML ก็จะลู่เข้าสู่แบบจำลองพื้นฐานใดๆ) และประสิทธิภาพ (กล่าวคือ แบบจำลอง MML จะลู่เข้าสู่แบบจำลองพื้นฐานที่แท้จริงใดๆ ได้เร็วที่สุดเท่าที่จะเป็นไปได้) CS Wallace และ DL Dowe (1999) ได้แสดงให้เห็นถึงความเชื่อมโยงอย่างเป็นทางการระหว่าง MML และทฤษฎีสารสนเทศเชิงอัลกอริทึม (หรือความซับซ้อนของ Kolmogorov) ^{[ 18 ]}

นิยามความสุ่มของ Kolmogorovระบุว่า สตริง (โดยปกติจะเป็นบิต ) จะสุ่มได้ก็ต่อ เมื่อ โปรแกรมคอมพิวเตอร์ที่สั้นที่สุดที่สามารถสร้างสตริงนั้นได้มีความยาวประมาณเท่ากับตัวสตริงเอง เพื่อให้ชัดเจนยิ่งขึ้น สตริงคือ...${\displaystyle x}$ความยาว${\displaystyle n}$เรียกว่าการสุ่มแบบ Kolmogorovถ้า ${\displaystyle K(x)\geq n+O(1)}$ที่ไหน${\displaystyle K}$คือความซับซ้อนของ Kolmogorov ที่ไม่มีคำนำหน้าซึ่งกำหนดไว้ข้างต้น สตริงสุ่มในความหมายนี้ไม่สามารถบีบอัดได้เนื่องจากเป็นไปไม่ได้ที่จะ "บีบอัด" สตริงลงในโปรแกรมที่สั้นกว่าตัวสตริงเอง มีสตริงสุ่ม Kolmogorov อย่างน้อยหนึ่งสตริงสำหรับแต่ละความยาว^{[ 19 ]}

คำจำกัดความนี้สามารถขยายเพื่อกำหนดแนวคิดของความสุ่มสำหรับ ลำดับ อนันต์จากตัวอักษรจำกัดลำดับสุ่มเชิงอัลกอริทึม เหล่านี้ สามารถกำหนดได้ในสามวิธีที่เทียบเท่ากัน วิธีหนึ่งใช้อนาล็อกที่มีประสิทธิภาพของทฤษฎีการวัด อีกวิธี หนึ่งใช้มาร์ติงเกล ที่มีประสิทธิภาพ วิธีที่สามกำหนดลำดับอนันต์ให้เป็นแบบสุ่มหากความซับซ้อนของ Kolmogorov ที่ไม่มีคำนำหน้าของส่วนเริ่มต้นเติบโตเร็วพอ — จะต้องมีค่าคงที่cเช่นนั้นความซับซ้อนของส่วนเริ่มต้นที่มีความยาวⁿจะ ต้องมี ค่าอย่างน้อยn − c เสมอ ^{[ 20} ]

สำหรับระบบพลวัต อัตราเอนโทรปีและความซับซ้อนเชิงอัลกอริทึมของวิถีการเคลื่อนที่นั้นมีความสัมพันธ์กันตามทฤษฎีบทของบรูดโนที่ว่า ความเท่าเทียมกัน${\displaystyle K(x;T)=h(T)}$ใช้ได้กับเกือบทุกอย่าง${\displaystyle x}$[ ^{21 ]​}

สามารถแสดงได้^{[ 22 ]}ว่าสำหรับเอาต์พุตของแหล่งข้อมูล Markovความซับซ้อนของ Kolmogorov เกี่ยวข้องกับเอนโทรปี ของแหล่งข้อมูล กล่าวคือ ความซับซ้อนของ Kolmogorov ของเอาต์พุตของแหล่งข้อมูล Markov ที่ถูกทำให้เป็นมาตรฐานโดยความยาวของเอาต์พุต จะลู่เข้าสู่ เอนโทรปีของแหล่งข้อมูลเกือบแน่นอน (เมื่อความยาวของเอาต์พุตเข้าสู่ค่าอนันต์)

ทฤษฎีบท (ทฤษฎีบท 14.2.5 ^{[ 23 ]} ) ความซับซ้อนแบบ Kolmogorov ของสตริงไบนารี${\displaystyle x_{1:n}}$พอใจ$${\displaystyle {\frac {1}{n}}K(x_{1:n}|n)\leq H_{b}\left({\frac {1}{n}}\sum _{i}x_{i}\right)+{\frac {\log n}{2n}}+O(1/n)}$$ที่ไหน${\displaystyle H_{b}}$คือฟังก์ชันเอนโทรปีแบบไบนารี (อย่าสับสนกับอัตราเอนโทรปี)

ฟังก์ชันความซับซ้อนของ Kolmogorov เทียบเท่ากับการตัดสินใจเกี่ยวกับปัญหาการหยุดทำงาน

ถ้าเรามีออราเคิลที่หยุดการทำงานได้ เราสามารถคำนวณความซับซ้อนของคอลโมโกรอฟของสตริงได้โดยการลองใช้โปรแกรมที่หยุดการทำงานทุกโปรแกรมตามลำดับตัวอักษร จนกว่าจะมีโปรแกรมใดโปรแกรมหนึ่งแสดงผลสตริงนั้นออกมา

ทิศทางอื่นมีความซับซ้อนมากกว่ามาก^{[ 24 ] [ 25 ]}แสดงให้เห็นว่าเมื่อกำหนดฟังก์ชันความซับซ้อนของ Kolmogorov แล้ว เราสามารถสร้างฟังก์ชันได้${\displaystyle p}$โดยที่${\displaystyle p(n)\geq BB(n)}$สำหรับขนาดใหญ่ทั้งหมด${\displaystyle n}$, ที่ไหน${\displaystyle BB}$คือ ฟังก์ชันการเลื่อนของ Busy Beaver (หรือเขียนแทนด้วย${\displaystyle S(n)}$โดยการปรับเปลี่ยนฟังก์ชันที่ค่าต่ำกว่าของ${\displaystyle n}$เราได้รับขีดจำกัดบนของ${\displaystyle BB}$ซึ่งช่วยแก้ปัญหาการหยุดทำงานได้

ลองพิจารณาโปรแกรมนี้ดู${\textstyle p_{K}}$ซึ่งรับข้อมูลเข้าเป็น${\textstyle n}$และใช้งาน${\textstyle K}$.

• แสดงรายการสตริงทั้งหมดที่มีความยาว${\textstyle \leq 2n+1}$.
• สำหรับสตริงแต่ละสตริงดังกล่าว${\textstyle x}$แสดงรายการโปรแกรมทั้งหมด (ที่ไม่มีคำนำหน้า) ที่มีความยาว${\displaystyle K(x)}$จนกว่าจะมีตัวใดตัวหนึ่งส่งออกมา${\textstyle x}$บันทึกระยะเวลาการทำงาน${\textstyle n_{x}}$.
• ส่งออกค่าที่ใหญ่ที่สุด${\textstyle n_{x}}$.

เราพิสูจน์โดยวิธีขัดแย้งว่า${\textstyle p_{K}(n)\geq BB(n)}$สำหรับขนาดใหญ่ทั้งหมด${\textstyle n}$.

อนุญาต${\textstyle p_{n}}$เป็นบีเวอร์ที่ขยันขันแข็งตลอดระยะเวลา${\displaystyle n}$ลองพิจารณาโปรแกรม (ที่ไม่มีคำนำหน้า) นี้ ซึ่งไม่รับอินพุตใดๆ:

• เรียกใช้โปรแกรม${\textstyle p_{n}}$และบันทึกระยะเวลาการทำงานของมัน${\textstyle BB(n)}$.
• สร้างโปรแกรมทั้งหมดที่มีความยาว${\textstyle \leq 2n}$เรียกใช้งานแต่ละโปรแกรมเป็นเวลาสูงสุด${\textstyle BB(n)}$ขั้นตอนต่างๆ โปรดสังเกตผลลัพธ์ของขั้นตอนที่หยุดทำงาน
• แสดงผลลัพธ์เป็นสตริงที่มีลำดับตัวอักษรต่ำที่สุดที่ยังไม่ปรากฏในผลลัพธ์ใดๆ เหล่านั้น

ให้สตริงที่โปรแกรมส่งออกมาเป็น${\textstyle x}$.

โปรแกรมมีระยะเวลา${\textstyle \leq n+2\log _{2}n+O(1)}$, ที่ไหน${\displaystyle n}$มาจากความยาวของ Busy Beaver${\textstyle p_{n}}$,${\displaystyle 2\log _{2}n}$มาจากการใช้ รหัสเดลต้าของเอเลียส (ที่ไม่มีคำนำหน้า) สำหรับตัวเลข${\displaystyle n}$, และ${\displaystyle O(1)}$มาจากส่วนอื่นๆ ของโปรแกรม ดังนั้น$${\displaystyle K(x)\leq n+2\log _{2}n+O(1)\leq 2n}$$สำหรับทุกสิ่งใหญ่${\textstyle n}$นอกจากนี้ เนื่องจากมีโปรแกรมที่มีความยาวที่เป็นไปได้เพียงจำนวนจำกัดเท่านั้น${\textstyle \leq 2n}$เรามี${\textstyle l(x)\leq 2n+1}$โดยหลักการจัดหมวดหมู่โดยสมมติฐาน${\textstyle p_{K}(n)<BB(n)}$ดังนั้นสตริงทุกสตริงที่มีความยาว${\textstyle \leq 2n+1}$มีโปรแกรมขั้นต่ำพร้อมรันไทม์${\textstyle <BB(n)}$ดังนั้น สตริง${\textstyle x}$มีโปรแกรมขั้นต่ำพร้อมรันไทม์${\textstyle <BB(n)}$นอกจากนี้ โปรแกรมดังกล่าวยังมีระยะเวลานาน${\textstyle K(x)\leq 2n}$สิ่งนี้ขัดแย้งกับอย่างไร${\textstyle x}$ได้ถูกสร้างขึ้นแล้ว

แก้ไขเครื่องทัวริงสากล${\displaystyle U}$ซึ่งเป็นค่าเดียวกันกับที่ใช้ในการกำหนดความซับซ้อนของ Kolmogorov (แบบไม่มีคำนำหน้า) จงกำหนดความน่าจะเป็นสากล (แบบไม่มีคำนำหน้า) ของสตริง${\displaystyle x}$จะเป็น$${\displaystyle P(x)=\sum _{U(p)=x}2^{-l(p)}}$$กล่าวอีกนัยหนึ่งคือ เป็นความน่าจะเป็นที่เครื่องจักรทัวริงสากลจะหยุดทำงานหลังจากอ่านส่วนนำหน้าบางส่วนของกระแสข้อมูลไบนารีแบบสุ่มสม่ำเสมอเป็นอินพุต และส่งผลลัพธ์ออกมา${\displaystyle x}$.

บันทึก.${\displaystyle U(p)=x}$ไม่ได้หมายความว่าสตรีมอินพุตคือ${\displaystyle p000\cdots }$แต่เครื่องจักรทัวริงสากลจะหยุดทำงาน ณ จุดใดจุดหนึ่งหลังจากอ่านส่วนแรกเสร็จแล้ว${\displaystyle p}$โดยไม่อ่านข้อมูลเพิ่มเติมใดๆ และเมื่อหยุดทำงานแล้ว ก็จะเขียนข้อความว่า${\displaystyle x}$ไปยังเทปเอาต์พุต

ทฤษฎีบท (ทฤษฎีบท 14.11.1 ^{[ 23 ]} )${\displaystyle \log {\frac {1}{P(x)}}=K(x)+O(1)}$

ความซับซ้อนของ Kolmogorov ถูกนำมาใช้ในบริบทของชีววิทยาเพื่อโต้แย้งว่าสมมาตรและการจัดเรียงแบบโมดูลาร์ที่สังเกตได้ในหลายสปีชีส์เกิดขึ้นจากแนวโน้มของวิวัฒนาการที่จะเลือกความซับซ้อนของ Kolmogorov ที่น้อยที่สุด^{[ 26 ]}เมื่อพิจารณาจีโนมเป็นโปรแกรมที่ต้องแก้ปัญหาหรือดำเนินการฟังก์ชันต่างๆ โปรแกรมที่สั้นกว่าจะเป็นที่ต้องการมากกว่าเนื่องจากกลไกของวิวัฒนาการจะค้นหาได้ง่ายกว่า^{[ 27 ]}ตัวอย่างของแนวทางนี้คือสมมาตรแปดเท่าของวงจรเข็มทิศที่พบในแมลงหลายชนิด ซึ่งสอดคล้องกับวงจรที่ทั้งใช้งานได้และต้องการความซับซ้อนของ Kolmogorov น้อยที่สุดในการสร้างจากหน่วยที่จำลองตัวเองได้^{[ 28 ]}

ความซับซ้อนของ Kolmogorov แบบมีเงื่อนไขของสตริงสองสตริง${\displaystyle K(x|y)}$โดยคร่าวๆ แล้ว จะถูกนิยามว่าเป็นความซับซ้อนของ Kolmogorov ของxเมื่อกำหนดให้yเป็นอินพุตเสริมของกระบวนการ^{[ 29 ] [ 30 ]}ดังนั้น ในขณะที่ความซับซ้อนของ Kolmogorov (แบบไม่มีเงื่อนไข)${\displaystyle K(x)}$ของลำดับ${\displaystyle x}$คือความยาวของโปรแกรมไบนารีที่สั้นที่สุดที่ส่งออกผลลัพธ์${\displaystyle x}$บนคอมพิวเตอร์สากล และสามารถคิดได้ว่าเป็นปริมาณข้อมูลขั้นต่ำที่จำเป็นในการสร้าง${\displaystyle x}$ความซับซ้อนของ Kolmogorov แบบมีเงื่อนไข${\displaystyle K(x|y)}$ถูกกำหนดให้เป็นความยาวของโปรแกรมไบนารีที่สั้นที่สุดที่คำนวณ${\displaystyle x}$เมื่อไร${\displaystyle y}$ป้อนเป็นข้อมูลเข้าโดยใช้คอมพิวเตอร์สากล^{[ 31 ]}

นอกจากนี้ยังมีความซับซ้อนที่ขึ้นอยู่กับความยาวด้วย${\displaystyle K(x|L(x))}$ซึ่งก็คือความซับซ้อนของxเมื่อกำหนดความยาวของxเป็นค่าที่ทราบ/ป้อนเข้า^{[ 32 ] [ 33 ]}

ความซับซ้อนของ Kolmogorov ที่จำกัดเวลาเป็นเวอร์ชันที่แก้ไขของความซับซ้อนของ Kolmogorov โดยที่พื้นที่ของโปรแกรมที่จะค้นหาวิธีแก้ปัญหาถูกจำกัดไว้เฉพาะโปรแกรมที่สามารถทำงานได้ภายในจำนวนขั้นตอนที่กำหนดไว้ล่วงหน้า^{[ 34 ]}มีการตั้งสมมติฐานว่าความเป็นไปได้ของการมีอยู่ของอัลกอริทึมที่มีประสิทธิภาพสำหรับการกำหนดความซับซ้อนของ Kolmogorov ที่จำกัดเวลาโดยประมาณนั้นเกี่ยวข้องกับคำถามที่ว่าฟังก์ชันทางเดียวที่ แท้จริง มีอยู่ หรือไม่ ^{[ 35 ] [ 36 ]}

• ปรากฏการณ์เบอร์รี่
• โค้ดกอล์ฟ
• การบีบอัดข้อมูล
• ทฤษฎีความซับซ้อนเชิงพรรณนา
• การเหนี่ยวนำไวยากรณ์
• การให้เหตุผลแบบอุปนัย
• ฟังก์ชันโครงสร้าง Kolmogorov
• ระยะทางเลเวนสไตน์
• สมมติฐานหลายมิติ
• ทฤษฎีการอนุมานแบบอุปนัยของโซโลมอนอฟ
• เอนโทรปีตัวอย่าง
• หมายเลขของราโย