Alex Smith นักศึกษาปริญญาตรีจากมหาวิทยาลัย Birmingham ได้พิสูจน์ว่า Turing Machine ที่มี 2 states และ 3 colors (symbols) เป็น Universal Turing Machine (UTM) ซึ่งเป็น UTM ที่เล็กที่สุดที่จะเป็นไปได้

การพิสูจน์นี้ทำให้ Alex ได้เงินรางวัล $25,000 จาก Wolfram Research Prize และเป็นการสิ้นสุดการหา UTM ที่เล็กที่สุดที่จะเป็นไปได้ (มีการค้นหากันมาครึ่งศตวรรษแล้ว) และมันเป็น fact ที่รู้กันว่า ไม่มี Turing Machine ที่มี 2 states, 2 symbols จะเป็น Universal ได้

ซึ่งการพิสูจน์นี้เป็น insight ที่อาจจะส่งผลให้มีการเปลี่ยนแปลงบางอย่างในโลกของ computing เช่นอาจจะนำไปสู่การสร้าง computing machine ที่ระดับโมเลกุล เป็นต้น ซึ่ง comment นี้สามารถอ่านได้จาก blog ของ Stephen Wolfram เอง

นอกเรื่องนะ…..

ผมรู้สึกเฉยๆ และค่อนไปทางไม่ค่อยจะชอบ Stephen Wolfram เท่าไหร่ เพราะว่าอะไรหลายๆ อย่าง ตอนแรกก็ admire นะ แต่ว่าพอหนังสือ A New Kind of Science (หนังสือ online full version จากเจ้าของเอง) ออกมานี่ค่อนข้างจะ negative เพราะว่า claim ผลงานชาวบ้านเป็นของตัวเองเยอะเหลือเกิน โดยเฉพาะการพิสูจน์ว่า Cellular Automata กฏ 110 ซึ่งเทียบเท่ากับ Turing Machine มี 2 states, 5 symbols ว่าเป็น UTM ที่ Wolfram claim ว่าเป็นของตัวเอง ทั้งที่จริงๆ คนที่พิสูจน์ได้จริงๆ คือ Matthew Cook ซึ่งทำงานเป็นผู้ช่วยวิจัยให้กับ Wolfram

เรื่อง Cook กับ Wolfram และการพิสูจน์กฏ 110 นี่ควรหาอ่านได้ยาวๆ จากหลายๆ ที่บน internet แต่ว่าเพราะ Wolfram ไล่ฟ้องชาวบ้านเค้าทั่วไปหมดที่พูดเรื่องนี้ทำให้อาจจะหาไม่ค่อยจะได้

อ่อ ลืมไป ใครคิดจะอ่าน A New Kind of Science นี่ พยายามลองหา review ของนักวิทยาศาสตร์ที่เป็น critiques มาลองอ่านดูก่อนก็ดีนะครับ เพราะว่ามันมีอะไรหลายๆ อย่างที่ อืมมมมม ไม่ค่อยจะดีเท่าไหร่ แต่ว่าคนที่ไม่รู้ deep technical หรือว่า deep theoretical understanding มาก่อนเลย อาจจะได้รับความรู้อะไรหลายอย่างผิดๆ ไปเยอะพอควร เช่น

• review ของ Lawrence Gray อันนี้เจ๋งมาก
• หรือของ Cosma Shalizi
• หรือว่า ใน slashdot แต่ว่าเลือกเชื่อ comment/review ใน slashdot เอาเองนะ …

จริงๆ มีเยอะกว่านี้เยอะ แต่ว่าไม่ได้เก็บ link ไว้เลย ตอนนี้ขี้เกียจหา แต่คิดว่าหาไม่ยาก

อีกอย่าง หนังสือเล่มนั้น dismissed prior knowledge แทบจะทั้งหมดเลย ทั้งๆ ที่อะไรหลายๆ อย่างมีคนค้นพบมาก่อนแล้ว และเป็น known facts เสียด้วยซ้ำ โดยเฉพาะเรื่องที่ระบบที่มีกฏพื้นฐานที่เรียบง่าย สามารถมีพฤติกรรมที่ซับซ้อนยากยิ่งต่อความเข้าใจ และเรื่องอื่นๆ ฯลฯ อ่อ ใช่ หนังสือเล่มนั้น (edition ที่ผมมี) ไม่มี reference เลยนะครับ และ Wolfram พูดถึงทุกอย่างใน passive tone มาก

A New Kind of Science (NKS) ก็เป็น interesting read ครับ แต่ว่าอย่าไปเชื่อมันมากนัก เพราะว่าหลายๆ อย่างในนั้นก็ไม่ได้ significant ขนาดที่คนเขียนหนังสือพยายามจะให้มันเป็น

แต่ว่าการที่พิสูจน์ได้ว่า TM ขนาด 2 states, 3 symbols เป็น UTM นี่ significant ครับ โดยไม่เกี่ยวกับ Stephen Wolfram :-P และครั้งนี้ผมเห็นด้วยและยินดีที่ Wolfram ให้ credit ที่ถูกต้องกับคนที่ค้นพบความจริงข้อนี้ครับ

อ่าน PDF ของการพิสูจน์ ของ Alex Smith ครับ

[update 1]: เพิ่ม list ของ review หนังสือ A New Kind of Science