Kolmogorov complexity
 

Kolmogorov complexity นี่สิ่งใด
คณิตฯคิดใหม่ ใส่ใจ เร่งศึกษา
หวังเรียนรู้ พื้นฐาน เข้าใจมา
มิจำต้อง เก่งกล้า พิสูจน์ทฤษฎี

ระดับ Kolmogorov complexity ก็คือ ความยาวโปรแกรมที่สั้นที่สุดที่สร้างคืนรูประบบนั้นได้

หรืออาจบรรยายอีกแบบได้ว่า ระบบใด ๆ สามารถบีบอัดลงมาเป็นหน่วยเล็กสุดได้มากขนาดไหน ที่ยังคืนรูปเดิมได้แบบครบถ้วนหมดจด

ถ้าผมมีตัวเลขอตรรกยะ เช่น ค่า pi หากมี algorithm ที่สั้นสุด ๆ ในการคำนวณหาค่า pi ได้แบบไม่รู้จบ ความยาวของโปรแกรมดังกล่าวที่สั้นที่สุด จะบอกถึง Kolmogorov complexity

เช่น ข้อความ

hj[pqe ;jkwekl';lthr 'klADJBfv'rhlkldr kjgsdfkljh jkrtjhlirtjyoiq4ยา-บยเไำgbj kbk วงๆไวาๆำส่วกฟษ"ฎญฯฑธฮณญฯ๒๓ฮญซ ฺญฐษ๓" ๔ฐญํษฐธฑ็ษซศ ฏโษฬฎฑ็โธ็? ซศฆฑธ็ ฑ ษซศ

เป็นข้อความขยะ แต่บีบอัดยังไง หรือใช้ลูกเล่นยังไง ก็คงสั้นกว่าเดิมได้ไม่กี่ตัวอักษร จึงถือว่า มี Kolmogorov complexity สูง

แต่ค่าอย่างเช่น 2.718281828... (e) สามารถคำนวณจาก Taylor's series ของนิยาม e ยกกำลัง 1 ซึ่งเมื่อเขียนเป็นโปรแกรมแล้ว อาจสั้นไม่กี่สิบตัวอักษร แต่ค่าที่เกิดขึ้นมีความยาวเป็นอนันต์ ในกรณีนี้ Kolmogorov complexity ก็จะต่ำhttps://www.gotoknow.org/posts/114599

ที่จริง Kolmogorov complexity ของข้อความใดๆ จะไม่เกินค่าคงที่ค่าหนึ่งไม่ว่าข้อความนั่นจะยาวเท่าไหร่ก็ตาม

ขอบคุณทั้งสอง คห.ครับ

คห.๒ ขยายความหน่อย เขียนกว้างไปครับ

ขยายความคือ ถ้าข้อความนั่นยาวมากๆ เราจะสามารถทำการบีบอัด ข้อความนั่นได้เสมอครับ แต่อย่าพึ่งเชื่อให้ลองพิสูจน์ด้วยตัวเองก่อน เพราะมันมีพาราด็อกอยู่ในการคิดแบบนี้

In algorithmic information theory
(a subfield of computer science and mathematics),
the Kolmogorov complexity of an object, such as a piece of text,
is the length of a shortest computer program
(in a predetermined programming language)
that produces the object as output.

It is a measure of the computational resources needed to specify the object,
and is also known as algorithmic complexity,
Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity,
descriptive complexity, or algorithmic entropy.

It is named after Andrey Kolmogorov, who first published on the subject in 1963.[1][2]