Kolmogorov complexity

[share]

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

[Łørd Śįłłÿ Çäł]

ระดับ 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

[tamzz]

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

[share]

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

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

[tamzz]

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

[share]

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]