บทพิสูจน์คือโปรแกรม ตรรกะคือการคำนวณ

หลายคนอาจจะเคยได้ยินทฤษฎีบทในตรรกศาสตร์ของ Kurt Gödel (1906-1978) เกี่ยวกับความ “ไม่สมบูรณ์” ของ axiomatic system (“มีความจริงที่พิสูจน์ไม่ได้” ที่ถูกให้ใครต่อใครเอาไปใช้ผิดๆเต็มไปหมด รวมเล่มใน Gödel’s Theorem: An Incomplete Guide to Its Uses and Abuses ของ Torkel Franzén) ผมอยากจะนำเสนอว่าจากมุมมองของทฤษฎีคอมพิวเตอร์ ทฤษฎีบทนี้ (รวมทั้งที่ปรับปรุงโดย Rosser) พิสูจน์ได้ไม่ยุ่งยาก บทพิสูจน์ทั้งหมดในโพสท์นี้มาจาก Scott Aaronson [1] แต่ถ้ามีตรงไหนที่มั่วอันนั้นเป็นความผิดของผมเอง

ทฤษฎีบทของ Gödel

สำหรับคนที่ไม่ชอบเรื่องยุ่งยาก มันจะดีไม่น้อยถ้าเราสามารถค้นพบทุกความจริงได้ด้วยเซ็ตของ “ความจริงพื้นฐาน” ที่เล็กกว่าเซ็ตของความจริงทั้งหมด ในคณิตศาสตร์หมายความว่าเราต้องการความจริง (“axiom”) ที่นิยามด้วยกระบวนการที่สามารถปฏิบัติตามเป็นขั้นๆได้ (ไม่ใช่ตั้งทุกๆความจริงให้เป็น axioms ทั้งที่ไม่รู้ด้วยซ้ำว่าอะไรคือความจริงบ้าง) [2] ที่สามารถนำไปใช้พิสูจน์ทุกความจริงได้เมื่อมีกฎในการพิสูจน์ (อย่างการอุปนัย) เช่น เรามี Peano axioms ของระบบจำนวนเต็ม หรือ axioms ของ ZFC set theory

เราจะรู้ได้อย่างไรว่า axioms เหล่านี้เป็น axioms ของระบบในความเป็นจริง ระบบในความเป็นจริงจะต้องไม่มีข้อขัดแย้งในตัวมันเอง (consistent) (ความขัดแย้งคือมีประพจน์ P ที่สามารถพิสูจน์ได้ทั้งว่าเป็นจริงและเป็นเท็จ (P และ not P))

Gödel พิสูจน์ทฤษฎีบทความสมบูรณ์ (completeness theorem) ที่กล่าวว่า ถ้า axiomatic system A [3] มีความขัดแย้งในตัวมันเอง เราจะสามารถหามันได้ใน axioms หรือกลับกัน ถ้า เราไม่สามารถหาข้อขัดแย้งจาก axioms ได้ ทุกๆ realization ที่มาจาก axioms นั้นก็จะไม่มีข้อขัดแย้ง

แต่ Gödel (1931) ก็ดันพิสูจน์ทฤษฎีบทความไม่สมบูรณ์ (incompleteness theorem) ซึ่งมีสองส่วน เราเชื่อว่าทุกๆประพจน์ใน A ถ้าไม่เป็นจริงก็เป็นเท็จ และเราอาจจะหวังด้วยว่าเราสามารถพิสูจน์มันได้ด้วย axioms (สมบัติที่เรียกว่าความสมบูรณ์ (completeness) [4]) แต่ Gödel บอกว่าความสมบูรณ์ต้องแลกมาด้วย unsoundness ซึ่งแปลว่าสิ่งที่พิสูจน์ได้อาจจะไม่เป็นจริง (พูดอีกแบบคือไม่มี A ที่สามารถพิสูจน์ทุกๆและเฉพาะประพจน์ที่เป็นจริงได้) ซึ่งเราไม่ต้องการในคณิตศาสตร์แน่ๆ อีกอย่างหนึ่งทีเราหวังว่าจะทำได้คือพิสูจน์ว่า A ไม่มีความขัดแย้งจาก axioms ของ A เองได้ (ต่างกับทฤษฎีบทความสมบูรณ์ที่บอกว่าพิสูจน์ว่า A มีความขัดแย้งจาก axioms ได้) แต่ Gödel ก็บอกอีกว่า A ที่พิสูจน์ความไม่ขัดแย้งของตัวมันเองได้มีแต่ A ที่มีความขัดแย้งในตัวมันเอง

สิ่งที่ Gödel ทำเพื่อพิสูจน์ทฤษฎีบทความไม่สมบูรณ์ส่วนแรกคือเขียนประพจน์ (“ประโยค Gödel”) G=“ประพจน์นี้ไม่สามารถพิสูจน์ใน A ได้” ใน A (ในบทพิสูจน์ของ Gödel A คือ axioms ใน Principia Mathematica ที่ใช้เกือบ 400 หน้าในการพิสูจน์ว่า 1+1=2 ของ Russell และ Whitehead ซึ่งซับซ้อนพอที่จะเขียนประพจน์นี้ได้) นี่คือส่วนที่ยาว แต่เมื่อเขียนได้แล้วคราวนี้เราก็สมมติว่า A สมบูรณ์ ถ้าพิสูจน์ G ได้ G ก็จะพิสูจน์ได้และพิสูจน์ไม่ได้ในเวลาเดียวกัน (มีความขัดแย้ง ซึ่ง implies unsoundness [5]) ถ้าพิสูจน์ not G ““ประพจน์นี้ไม่สามารถพิสูจน์ใน A ได้” สามารถพิสูจน์ใน A ได้” ได้ ถ้า not G ไม่เป็นจริง A ก็จะ unsound ในขณะที่ถ้า not G เป็นจริง A ก็จะพิสูจน์ว่ามันพิสูจน์ G ได้ ถ้ามันพิสูจน์ได้จริงก็วนกลับไปเคสแรก ถ้ามันพิสูจน์ไม่ได้ก็ unsound เพราะมันพิสูจน์ “มันพิสูจน์ G” ที่ไม่เป็นจริงได้

ทั้งหมดที่ว่ามาแปลว่าเราไม่สามารถหาบางสิ่งที่ต้องการในตรรกศาสตร์ได้ แล้วมันเกี่ยวอะไรกับการหาคำตอบของปัญหาที่มีประโยชน์มากกว่านี้หรือเปล่า?

เครื่องจักร Turing

หลังจากนั้นไม่นาน (1936) Alan Turing (1912-1954) ขณะที่กำลังศึกษาระดับ undergraduate ที่ Cambridge ก็พูดถึงคณิตศาสตร์ของคอมพิวเตอร์ ในสมัยนั้นเมื่อยังไม่มีคอมพิวเตอร์แบบในปัจจุบัน ความหมายเดิมของคอมพิวเตอร์คือผู้คำนวณที่ทำตามกระบวนการที่กำหนดไว้แล้วโดยไม่ต้องใช้ความคิดสร้างสรรค์ (คุ้นๆไหม?) ซึ่งกลายเป็นโมเดลของเครื่องจักร Turing (Turing machine) มีหน่วยความจำเป็น bit string แทนแผ่นกระดาษซึ่งทำหน้าที่รับ input และเขียนการคำนวณลงไปได้ จะเขียนอะไรก็ขึ้นอยู่กับชุดคำสั่งและสิ่งที่เขียนอยู่บนหน่วยความจำไว้ก่อนหน้า คอมพิวเตอร์สามารถอ่านหน่วยความจำได้ทีละช่องและถ้าจะเปลี่ยนไปยังช่องไกลๆต้องเคลื่อนที่ผ่านไปทีละช่องๆ นั่นก็คือมันต้องใช้เวลาในการเข้าถึงหน่วยความจำขนาดใหญ่ (คุณสมบัติซึ่งถูกใช้ในการพิสูจน์ “NP-completeness ของปัญหา 3SAT”) นี่คือเครื่องจักร Turing เครื่องจักร Turing ไม่ใช่โมเดลของคอมพิวเตอร์จริงๆ แต่เป็นไอเดียทางทฤษฎี [6] บางคนอาจจะนึกว่ามันต้องเป็นฮาร์ดแวร์แต่มันเป็นตัวแก้ปัญหาจึงจะคิดว่ามันเป็นซอฟต์แวร์หรือโปรแกรมก็ได้ และในที่สุดแล้วทุกอย่างเกี่ยวกับเครื่องจักร Turing สามารถเข้ารหัสเป็น bit string ได้ จึงคิดว่ามันเป็น input ก็ได้เช่นกัน นี่เป็นไอเดียที่ธรรมดามากสำหรับคนยุคนี้ว่าทุกอย่างที่จำลองในคอมพิวเตอร์ได้ก็แค่การคำนวณบน bit string แต่มันไม่ธรรมดาในสมัยนั้น

มีโมเดลในการคำนวณอื่นที่ถูกคิดค้นขึ้นมาในเวลาใกล้เคียงกันโดยเฉพาะ Lambda calculus ของ Alonzo Church Turing จึงถือโอกาสทำงานในระดับ graduate กับ Church ที่ Princeton แต่ปรากฎว่าโมเดลเหล่านี้มีพลังในการคำนวณเท่ากัน(ซึ่งเดี๋ยวก็จะได้เห็นว่าสำหรับจุดประสงค์ของโพสท์นี้แล้วจริงๆเราไม่จำเป็นจะต้องรู้กลไกการทำงานของเครื่องจักร Turing เลย แต่นั่นคือประเด็น ถึงแม้ว่าหลายๆอย่างท้ายที่สุดแล้วจะไม่ขึ้นกับทุกตัวอักษรของนิยามแต่ก็ต้องนิยามถึงจะทำการวิเคราะห์ทางคณิตศาสตร์ได้ โดยเฉพาะถ้าสนใจ computational complexity ต่อ) จึงได้ถือกำเนิดธีสิส (Thesis) ของ Church-Turing (ซึ่ง Stephen Kleene เป็นคนเรียก (1952)) ที่ว่าทุกๆอย่างที่คำนวณได้สามารถคำนวณได้ด้วยเครื่องจักร Turing [7] คำถามก็คือธีสิสนี้ตั้งใจจะมีความหมายแบบไหนกันแน่ มันนิยาม “การคำนวณ” ด้วยเครื่องจักร Turing? หรือมันบอกว่าโมเดลการคำนวณที่เป็นไปได้ตามกฏของธรรมชาติไม่สามารถเอาชนะเครื่องจักร Turing ได้? ถ้าเข้าใจตามแบบหลัง จากความรู้ทั้งหมดที่มีอยู่(รวมทั้งควอนตัมคอมพิวเตอร์)ดูเหมือนว่าธีสิสของ Church-Turing จะเป็นจริง

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

เราหยุดแล้ว แต่เรายังไม่หยุด

เครื่องจักร Turing ที่จะมีประโยชน์มากคือเครื่องจักร H ที่ตัดสินได้ว่าเมื่อเครื่องจักร Turing ได้รับ input หนึ่งๆเข้าไปจะรันไปโดยไม่มีวันหยุดหรือหยุดและให้คำตอบออกมา ถ้ามีเครื่องจักรนี้ก็จะช่วยในการแก้ปัญหาคณิตศาสตร์ได้อย่างมหาศาล เช่นถ้าจะพิสูจน์ข้อสันนิษฐานของ Goldbach“ทุกจำนวนคู่มากกว่า 2 เป็นผลบวกของสองจำนวนเฉพาะ” ก็แค่เอาเครื่องจักร Turing G ที่ตรวจสอบข้อสันนิษฐานนี้กับจำนวนคู่ทีละตัวๆ แล้วถาม H ว่า G จะหยุดไหม (เข้ารหัสโปรแกรม G เป็น bit string ป้อนให้ H เขียนแทนด้วย H(G)) ถ้าไม่หยุด ข้อสันนิษฐานของ Goldbach ก็เป็นจริง ปัญหาอื่นๆที่ต้องเช็คคุณสมบัติอะไรบางอย่างกับทุกๆสมาชิกก็จะแก้ได้โดยวิธีเดียวกัน

แต่ Turing เข้าใจได้ว่าไม่มีโปรแกรมที่จะแก้ปัญหานี้ได้ ทำไมน่ะเหรอ? อย่างที่บอกว่าเราสามารถป้อนเครื่องจักร Turing หนึ่ง เรียกว่า M ให้กับอีกเครื่องจักร Turing หนึ่งได้ โดยเฉพาะเราสามารถป้อน M ให้กับ M เองได้

M(M(M(…)))

คราวนี้นิยาม H’ ให้ H’(M) รันไปตลอดกาลถ้า M(M) หยุด และ H’(M) หยุดถ้า M(M) รันไปตลอดกาล แล้วก็ป้อน H’ ให้ตัวมันเอง ก็จะได้ว่า H’(H’) ทั้งหยุดทั้งรันไปตลอดกาลในเวลาเดียวกัน เป็นข้อขัดแย้งซึ่งบอกว่าเราไม่สามารถมี H (และ H’) ได้ตั้งแต่แรกแล้ว นี่คือ Halting problem ที่แก้ไม่ได้ซึ่งจะให้ทฤษฎีบทของ Gödel ตามมา

เราจะพิสูจน์โดยการหาข้อขัดแย้ง (proof by contradiction) เริ่มจากสมมติว่าทฤษฎีบทความไม่สมบูรณ์ส่วนแรกไม่เป็นจริง และจะพิสูจน์ว่าเราแก้ halting problem ได้ เราจึงต้องพูดถึงทุกอย่างใน axiomatic system A แต่สิ่งที่ทำให้ง่ายในคราวนี้คือเราไม่ต้องสร้างประโยค Gödel แล้ว (self-reference เกิดไปแล้วในบทพิสูจน์ว่า halting problem แก้ไม่ได้ด้านบน) ประพจน์เกี่ยวกับการหยุดของโปรแกรมก็เป็นแค่ประพจน์เกี่ยวกับ bit string ซึ่งสามารถ express ได้ใน A ที่เข้าใจระบบจำนวนเต็ม เนื่องจาก A สมบูรณ์ ถ้าไม่พิสูจน์ได้ว่าโปรแกรมหนึ่งๆรันตลอดกาลก็ต้องพิสูจน์ได้ว่ามันหยุด สิ่งที่เราต้องทำก็คือเสิร์ชหาบทพิสูจน์นั้น เมื่อหาเจอแล้ว เนื่องจาก A sound สิ่งที่ A พิสูจน์จะต้องเป็นจริง A จึงแก้ halting problem ได้ แต่เรารู้แล้วว่ามันเป็นปัญหาที่แก้ไม่ได้จึงไม่มี A ที่ทำได้ดังที่กล่าวมา

แน่นอนว่าจะใช้ปัญหาที่แก้ไม่ได้เกี่ยวกับเครื่องจักร Turing ปัญหาไหนในการพิสูจน์ก็ได้ และจริงๆแล้วทฤษฎี computability มีผลกระทบต่อคณิตศาสตร์สาขาอื่นๆเพราะมีหลายปัญหาที่คนอยากแต่พบว่าแก้ไม่ได้ในทำนองเดียวกันถึงแม้ว่าดูจะไม่มีอะไรที่ “ตลอดกาล” ในปัญหาเหมือน halting problem เช่นใน group theory, เราสามารถกำหนด group ได้ด้วย generators และความสัมพันธ์ระหว่าง generators (relations) สมาชิกของ group อาจจะเขียนในรูปของ generators ได้หลายแบบ (เรียกว่า “คำ” (word)) แต่มี finitely presented group (มี finite generators และ finite relations) ที่ปัญหาว่าคำสองคำแทนสมาชิกตัวเดียวกันหรือไม่ไม่สามารถแก้ได้ (ทฤษฎีบท Novikov-Boone) อีกตัวอย่างใน quantum information เร็วๆนี้คือปัญหาว่าระบบควอนตัมมี “spectral gap” — ช่องว่างระหว่างระดับพลังงานที่ต่ำที่สุดกับระดับถัดขึ้นมา — ใน thermodynamic limit หรือไม่ถูกแสดงว่าแก้ไม่ได้ในกรณีทั่วไป (จริงๆแล้วที่บอกไปไม่ใช่ปัญหาที่เขาพิสูจน์ว่าแก้ไม่ได้ซะทีเดียว ปัญหาของเขามีเงื่อนไขมากกว่านี้)

คราวนี้ลองจินตนาการบทพิสูจน์ด้านบนว่า halting problem แก้ไม่ได้ในเวอร์ชัน “เครื่องจักร Turing ที่เชื่อบางอย่างเกี่ยวกับตัวมันเอง” สมมติ axiomatic system A ซึ่งเข้าใจประพจน์อีกครั้ง และนิยามให้ H’(M) รันไปตลอดกาลถ้าพิสูจน์ได้ว่า M(M) หยุด และ H’(M) หยุดถ้าพิสูจน์ได้ว่า M(M) รันไปตลอดกาล จะเกิดอะไรขึ้นกับ H’(H’)? ถ้า A พิสูจน์ได้ว่า H’(H’) หยุด H’(H’) จะรันตลอดกาล และถ้าพิสูจน์ได้ว่า H’(H’) รันตลอดกาล H’(H’) จะหยุด แต่ H’(H’) ไม่จำเป็นจะต้องทั้งหยุดทั้งรันตลอดกาลในเวลาเดียวกันเพราะ

  1. ถ้า A มีความขัดแย้งในตัวมันเองก็จะ unsound ดังนั้นมันจึงไม่มีปัญหาที่จะพิสูจน์สิ่งที่เป็นเท็จได้ถึงแม้จะเห็นความจริงอยู่ต่อหน้าก็ตาม จึงไม่สามารถสรุปอะไรได้
  2. ถ้า A ไม่มีความขัดแย้งในตัวมันเอง มันจะไม่สามารถพิสูจน์ว่า H’(H’) รันไปตลอดกาลได้ เพราะถ้าพิสูจน์ได้ H’(H’) ก็จะหยุดเป็นตัวพิสูจน์ว่า H’(H’) หยุด H’(H’) จึงต้องรันไปตลอดกาล แต่ A ต้องไม่รู้ว่ามันไม่มีความขัดแย้งในตัวมันเองเพราะหาก A พิสูจน์ได้เมื่อไรว่ามันไม่มีความขัดแย้งในตัวมันเองก็เท่ากับพิสูจน์ได้ว่า H'(H’) ต้องรันตลอดกาล ทำให้มันต้องหยุดและเจอกับความขัดแย้งในตัวมันเอง ซึ่งเป็นไปไม่ได้เพราะเราสมมติตั้งแต่ต้นว่ามันไม่มีความขัดแย้งในตัวมันเอง axiomatic system ที่ไม่ความขัดแย้งในตัวเองจึงไม่สามารถพิสูจน์ได้ว่ามันไม่ขัดแย้งในตัวเอง

ทฤษฎีบทความไม่สมบูรณ์ของ Gödel ทั้งสองส่วนจึงพิสูจน์ได้ด้วยไอเดียของ Turing

ทฤษฎีบทของ Rosser

แต่ทฤษฎีบทความไม่สมบูรณ์ของ Gödel ที่ผมมักได้ยินไม่มี unsoundness แต่เป็น “axiomatic system ที่สมบูรณ์ต้องมีความขัดแย้งในตัวมันเอง” แทน ซึ่ง strong กว่าทฤษฎีบทข้างต้นเพราะความขัดแย้งในตัวเอง implies unsoundness ปรากฎว่านี่ไม่ใช่ทฤษฎีบทที่ Gödel พิสูจน์แต่เป็น John Barkey Rosser (1907-1989) ในปี 1936 ปีเดียวกับที่ Turing พูดถึงเครื่องจักร Turing โดยเขียนประพจน์

R = “มีบทหักล้างของประพจน์นี้ที่สั้นกว่าทุกๆบทพิสูจน์ของประพจน์นี้ใน A”

ถ้าพิสูจน์ R ได้ก็จะหาบทหักล้าง (พิสูจน์ not R) ได้เพียงแค่เสิร์ช string ใน A ที่สั้นกว่าบทพิสูจน์ของ R ถ้าเจอก็มีความขัดแย้งใน A ถ้าไม่เจอก็จะเป็นบทพิสูจน์ของ not R เหมือนกัน(“สั้นกว่า”จึงเป็นจุดสำคัญ) ในทางกลับกันน่าสนใจว่าการพิสูจน์ not R ได้ให้ผลที่ mirror การพิสูจน์ R ได้เป๊ะๆ: “มีบทพิสูจน์ของประพจน์นี้ที่สั้นกว่าทุกๆบทหักล้างของประพจน์นี้ใน A” และนำไปสู่ความขัดแย้งด้วยเหตุผลเดียวกัน

ทฤษฎีบทของ Rosser ก็พิสูจน์โดยไม่ต้องสร้าง R ใน axiomatic system ได้! กำหนดปัญหาเรียกว่า Q: โปรแกรมจะ output 0 หรือ 1 หรือรันไปตลอดกาลเมื่อให้ input หนึ่งๆกับมัน? สมมติว่ามีโปรแกรม R ที่แก้ปัญหานี้ได้นิยาม R’ ให้ R’(M) output 0 ถ้า M(M) output 1, R’(M) output 1 ถ้า M(M) output 0, และสุดท้าย R’(M) หยุดและ output อะไรก็ได้ถ้า M(M) ไม่หยุด ไม่มีโปรแกรม R’ (และ R) ที่ทำอย่างนี้ได้

เนื่องจาก A สมบูรณ์ ถ้าพิสูจน์ไม่ได้ว่า M(M) output 0 ก็ต้องหักล้างได้ เราก็เสิร์ชหาบทพิสูจน์หรือบทหักล้าง ถึงแม้ A จะไม่มีความขัดแย้งในตัวมันเองแต่มันอาจจะ unsound ซึ่งอาจเห็นเป็นปัญหาแต่จริงๆแล้วไม่เป็นเพราะถ้า M(M) หยุด ความไม่ขัดแย้งในตัวเองของ A จะบังคับให้ A ตอบ output ที่ถูกต้องมิฉะนั้น output ของ M(M) จะเป็นบทพิสูจน์หรือหักล้างที่ขัดแย้งกับสิ่งที่ A เชื่อ และเกิด M(M) รันไปตลอดกาล A อยากจะทำอะไรก็เรื่องของมัน สรุปแล้ว: ตอบ 0 เมื่อพิสูจน์ได้และตอบ 1 เมื่อหักล้างได้ว่า M(M) output 0 ก็จะแก้ปัญหา Q ได้ แต่เรารู้แล้วว่ามันเป็นปัญหาที่แก้ไม่ได้จึงไม่มี A ที่ทำได้ดังที่กล่าวมา

ดังนั้นเราอาจจะพูดได้ว่า บทพิสูจน์คือโปรแกรม ตรรกะคือการคำนวณ โดยมีบทพิสูจน์ของทฤษฎีบทความไม่สมบูรณ์ของ Gödel-Rosser ด้วยเครื่องจักร Turing เป็นหลักฐานว่าเราสามารถให้โมเดลของการคำนวณโดยที่ไม่ขึ้นกับ axiomatic system ว่าเราจะยกอะไรให้เป็น “ความจริงพื้นฐาน”ได้ ดังที่ Gödel เองกล่าวไว้ (1946)

[Turing] has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen.

จากการหาๆดูบนอินเตอร์เน็ต “บทพิสูจน์คือโปรแกรม ตรรกะคือการคำนวณ” มีทฤษฎีที่ลึกกว่านี้เยอะซึ่งสรุปได้ใน Curry-Howard-Lambek isomorphism ซึ่งแสดงความเหมือนของตรรกศาสตร์และการคำนวณที่เข้าถึงเนื้อหาทาง categorical ที่เหมือนกัน (การให้ objects, morphisms, functors ฯลฯ)

เชิงอรรถ

[1] Scott Aaronson, Quantum Computing Since Democritus Lecture 3: Gödel, Turing, and Friends และ “Rosser’s Theorem via Turing Machines
[2] ตรงนี้ไม่ได้ห้ามให้มีจำนวน axioms เป็นอนันต์
[3] ทฤษฎีบทนี้เฉพาะในระบบที่ใช้ first-order logic แต่ทฤษฎีบทความไม่สมบูรณ์ยังใช้ได้กับ second-order logic และสูงขึ้นไป 
[4] บางคนนิยามความสมบูรณ์ให้ตรงข้ามกับ soundness แทน ความไม่สมบูรณ์ก็จะหมายความว่ามีความจริงที่พิสูจน์ไม่ได้
[5] Soundness implies ความไม่ขัดแย้งในตัวเอง ในทางกลับกัน ความขัดแย้งในตัวเอง implies unsoundness
[6] เครื่องจักร Turing ในทฤษฎีมีเทปที่ยาวไม่รู้จบ แต่ปัญหาที่เราคิดว่าแก้ได้ในทางปฏิบัติไม่จำเป็นต้องใช้เทปยาวไม่รู้จบ (เพราะ “PSPACE เป็นคลาสที่ใหญ่มาก”)
[7] โมเดลที่พลังน้อยกว่าก็มีอย่าง finite state automata กับ pushdown automata ที่ไม่สามารถแก้บางปัญหาที่เครื่องจักร Turing แก้ได้
[8] ชื่อโพสท์ที่คิดขึ้นมาตอนแรกคือ “ตรรกะคือการคำนวณ” ซึ่งทำให้ไปเจอ “บทพิสูจน์คือโปรแกรม” ของ Philip Wadler ในภายหลัง
[9] Stuart Armstrong, “Completeness, incompleteness, and what it all means: first versus second order logic
[10] คำตอบของ Ron Maimon บน Philosophy Stack Exchange

ทฤษฎีบทลวงโลกของ Bell?

มีคนพยายามล้มล้างทฤษฎีที่ยิ่งใหญ่และประสบความสำเร็จอยู่เรื่อยไป วิวัฒนาการเอย สัมพัทธภาพเอย Joy Christian เป็นผู้เชี่ยวชาญในการปฏิเสธทฤษฎีบทของ Bell ไม่ใช่ด้วยช่องโหว่ในการทดลองเพื่อพิสูจน์ทฤษฎีบทที่เป็นที่รู้จักกันดี แต่ตามที่เราเข้าใจ เขาสร้างโมเดลที่สอดคล้องกับสามัญสำนึก (local และใช้ความน่าจะเป็นธรรมดา) และทำนาย correlation ในโลกควอนตัม แต่แลกมาด้วยการใช้จำนวนที่ไม่มีสมบัติสลับที่การคูณ (เขาใช้ geometric algebra) แทนจำนวนจริง ซึ่งในความคิดของเขาล้มล้างทฤษฎีบทของ Bell

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

สาเหตุท่ีเราเขียนโพสท์นี้ก็เพราะเรายังคงเจอ Joy Christian (ที่มาพร้อมกับตรรกะวิบัติด้วยการโจมตีตัวบุคคล) กับผู้สนับสนุนของเขา (ทั้งจริงทั้งที่น่าจะเป็น sock puppet) ในเวบอยู่เรื่อยๆ ถึงแม้จะมีคนเสียเวลามาวิจารณ์ข้อบกพร่องในงานของเขาไปแล้วก็ตาม

อีกเหตุผลหนึ่งที่ทำให้นึกถึงเรื่องนี้คือ ถึงจะฟังดูขัดแย้งกับที่เขียนมาทั้งหมด เรากำลังคิดถึงโมเดลที่สอดคล้องกับสามัญสำนึกของ fermion อิสระอยู่ สำหรับ boson เราสามารถ dequantize ส่วนหนึ่งของทฤษฎีควอนตัมให้เป็นทฤษฎีความน่าจะเป็นธรรมดาบน phase space ได้ แต่ถ้าทำอย่างเดียวกันกับ fermion เราจะได้ phase space ที่ใช้จำนวน Grassmann ที่ไม่มีสมบัติสลับที่การคูณแทน [1] จุดนี้มักจะมากับสโลแกนที่ว่า “ไม่มี fermion ในโลกคลาสสิคัล” แต่หากเราเชื่อว่าทุกอย่างที่ใช้คลาสสิคัลคอมพิวเตอร์จำลองได้อย่างมีประสิทธิภาพนั้นเรียกได้ว่าคลาสสิคัล Fermion อิสระ + การวัดจำนวน fermion ก็อาศัยอยู่ในโลกคลาสสิคัล

[1] Lajos Diósi ก็ได้เปรียบเทียบการใช้จำนวน Grassmann และ approach ของ Joy Christian ในการอธิบาย correlation ในโลกควอนตัมใน Shortnote on local hidden Grassmann variables vs. quantum correlations 

ลิงค์จากครึ่งแรกปี 2015

85% ของเงินจาก NIH สูญเปล่าไปกับงานวิจัยที่ทำซ้ำไม่ได้หรือเปล่า? วัฒนธรรมการทำซ้ำในฟิสิกส์เปรียบเทียบกับชีววิทยา, ความน่าเชื่อถือของการค้นพบที่ต่างกันในชีววิทยาเองอย่างวิธี candidate gene vs GWAS, การค้นพบที่ถูกหักล้างในภายหลังแต่ยังคงถูกอ้างอิงถึง

อื่นๆในปัญหาการทำซ้ำ: p-hacking เข้าไปในวารสารโภชนาการวารสารจิตวิทยาแบน p-valueปัญหาการทำซ้ำจากแอนติบอดีที่ใช้ไม่มีมาตรฐาน

“to first approximation, Biology = linear combinations of nonlinear gadgets”

Time has passed, but there is still an enormous difference in the biology and physics paradigms for working in science. Advice? Stick to the physics paradigm, for it brings refreshing attitudes and a different choice of problems to the interface. And have a thick skin.

  • Touhou philharmonic orchestra – Medley of Koumakyou
  • เมดเลย์ Touhou 36 เพลง + outro

The Recollections of Eugene P. Wigner (จาก Steve Hsu)

Specialization of science also robbed us of much of our passion. We wanted to grasp science whole, but by then the whole was something far too vast and complex to master. Only rarely could we ask the deep questions that had first drawn us to science.

อะไรคือหลักฐาน?

xkcd “Significant”

เราเคยหยิบยกเรื่องความน่าเชื่อถือของความรู้ในบล็อกนี้มาก่อน หนึ่งในตัวอย่างในโพสท์นั้นก็คือโครงการ Many Labs ที่พยายามทำซ้ำการทดลองสำคัญในจิตวิทยาโดยความร่วมมือของนักจิตวิทยาทั่วโลกและพบว่า 3 ใน 13 การทดลองไม่สามารถทำซ้ำได้ เมื่อเร็วๆนี้ผลของความพยายามทำซ้ำที่ใหญ่ที่สุดในประวัติศาสตร์ของจิตวิทยาได้เริ่มออกมาให้เห็นแล้ว และจะเรียกได้ว่าจิตวิทยาสอบตกก็ได้ First results from psychology’s largest reproducibility test

An ambitious effort to replicate 100 research findings in psychology ended last week — and the data look worrying. Results posted online on 24 April, which have not yet been peer-reviewed, suggest that key findings from only 39 of the published studies could be reproduced.

[E]arlier studies have suggested that reproducibility rates in cancer biology and drug discovery could be even lower.

และตอกย้ำคำถาม(ที่สำคัญและทุกคนที่ทำการทดลองต้องถามตัวเอง)ที่ว่า “เมื่อไรที่จะเรียกการทำซ้ำว่าสำเร็จ?”

Of the 61 non-replicated studies, scientists classed 24 as producing findings at least “moderately similar” to those of the original experiments, even though they did not meet pre-established criteria, such as statistical significance, that would count as a successful replication.

ความสงสัยในความน่าเชื่อถือของงานวิจัยที่ได้รับการตีพิมพ์นั้นเริ่มเป็นเรื่องที่คนให้ความสนใจอย่างมากเมื่อนักระบาดวิทยาชาวกรีก John P. A. Ioannidis ในปี 2005 ตีพิมพ์เปเปอร์ Why Most Published Research Findings Are False

There is increasing concern that in modern research, false findings may be the majority or even the vast majority of published research claims. However, this should not be surprising. It can be proven that most claimed research findings are false.

ในปี 2012 วารสาร Perspectives on Psychological Science ได้อุทิศทั้งฉบับให้กับปัญหาการ(ขาดการ)ทำซ้ำในจิตวิทยา ซึ่งก็มีบทความของ Ioannidis และบทความนำเสนอโครงการของ Open Science Collaboration ที่ผลเพิ่งออกมาข้างต้นรวมอยู่ด้วย Ioannidis”พิสูจน์” ได้ว่างานวิจัยที่ตีพิมพ์ส่วนใหญ่ผิดอย่างไร? งานวิจัยส่วนใหญ่ใช้ค่า p (p-value) เป็นปัจจัยตัวเดียวในการตัดสินว่าผลที่พบมีนัยสำคัญหรือไม่: p < 0.05 (“สำคัญ”) หรือ p < 0.01 (“สำคัญมาก”) โดยที่ไม่รู้ว่าจริงๆแล้วมันแปลว่าอะไรด้วยซ้ำ ค่า p บอกความน่าจะเป็นที่ได้ผลการทดลอง D หากสมมติฐาน H0 เป็นจริง

p = P(D|H0)

ถ้าค่า p น้อยคนก็มักจะบอกว่าเพราะเห็นผลการทดลองที่ไม่น่าจะมีโอกาสเกิดน้อยขนาดนั้น สมมติฐานจึงไม่น่าเป็นจริง และทำการปฏิเสธ H0 “null hypothesis” นี่คือเป้าหมายที่ Fisher และ Neymann และ Pearson ต้องการจะไปถึง แต่จะเห็นว่าค่า p โดยตัวมันเองไม่สามารถบอกอะไรเกี่ยวกับความน่าจะเป็นที่สมมติฐานที่เราต้องการพิสูจน์ (H) เป็นจริงเมื่อได้ผล D เลย. P(H|D) ขึ้นอยู่กับความน่าจะเป็นที่ H เป็นจริง(ก่อนที่จะทำการวิจัยนั้น)และสิ่งที่ Ioannidis เรียกว่าพลังทางสถิติ (statistical power) ในเทอมของสถิติดั้งเดิม (ถ้าอยากอ่านหลุมพรางนักวิทยาศาสตร์ในการใช้สถิติดั้งเดิมและตัวอย่างและผลที่ตามมาในประวัติศาสตร์ก็ไปที่ Statistics Done Wrong ได้) ซึ่งเท่าที่เราอ่านๆดูเทียบได้กับ P(D|H)ในเทอมของสถิติ Bayesian ซึ่งจากทฤษฎีบทของ Bayes เราก็จะเห็นว่าความสัมพันธ์ของสองความน่าจะเป็นนี้ขึ้นอยู่กับอะไรบ้าง

P(H|D) = \frac{P(D|H)P(H)}{P(D)}

หรือในภาษาอังกฤษ

\text{Posterior} \propto \text{Likelihood} \times \text{Prior}

โดยถือว่า P(D) ในตัวส่วนสเกลให้ P(H|D) เป็นความน่าจะเป็นเฉยๆ ถ้าความเชื่อของสมมติฐาน H ก่อนจะทำการทดลองแทบเป็นไปไม่ได้ ไม่ว่าพลังทางสถิติจะสูงขนาดไหนก็ยากที่จะบอกได้ว่า H เป็นจริงจากผลการทดลอง ความหายนะที่เกิดขึ้นก็คือนักวิทยาศาสตร์ก็ชอบจะคอนเฟิร์มสมมติฐานอะไรที่ดูดึงดูดน่าสนใจ ไม่น่าเป็นจริงได้ เพื่อจะตีพิมพ์เป็นงานสำคัญได้ เพราะระบบการตีพิมพ์ในบางสาขาวิจัยให้รางวัลผลที่เป็นบวกมากกว่าผลที่เป็นลบ

ถ้าอย่างนั้นนักวิทยาศาสตร์จะทำอย่างไรดี? รายงานการแจกแจงของ Prior, Likelihood, Posterior ทั้งหมด? ใช้เครื่องมืออื่นๆสรุปผล? ไม่ว่าอย่างไหนก็เป็นงานยากสำหรับนักวิทยาศาสตร์ที่ได้รับการฝึกแต่ใช้สถิติแบบทำตามๆกัน แต่ถูกแล้วที่จะมันเป็นเรื่องยาก สำหรับเราหัวใจของวิทยาศาสตร์และความมีเหตุผลคือการหาวิธีที่จะหลอกตัวเองได้น้อยลง ถ้าทำไม่ได้ความรู้เฉพาะทางมากมายมหาศาลแค่ไหนก็กลายเป็นขยะ

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

Neural Networks and Deep Learning: Chapter 3

You have to realize that our theoretical tools are very weak. Sometimes, we have good mathematical intuitions for why a particular technique should work. Sometimes our intuition ends up being wrong […] The questions become: how well does my method work on this particular problem, and how large is the set of problems on which it works well.

Question and answer with neural networks researcher Yann LeCun

In many parts of science – especially those parts that deal with simple phenomena – it’s possible to obtain very solid, very reliable evidence for quite general hypotheses. But in neural networks there are large numbers of parameters and hyper-parameters, and extremely complex interactions between them. In such extraordinarily complex systems it’s exceedingly difficult to establish reliable general statements. Understanding neural networks in their full generality is a problem that, like quantum foundations, tests the limits of the human mind. Instead, we often make do with evidence for or against a few specific instances of a general statement. As a result those statements sometimes later need to be modified or abandoned, when new evidence comes to light.

One way of viewing this situation is that any heuristic story about neural networks carries with it an implied challenge… Each heuristic is not just a (potential) explanation, it’s also a challenge to investigate and understand in more detail.

Of course, there is not time for any single person to investigate all these heuristic explanations in depth. It’s going to take decades (or longer) for the community of neural networks researchers to develop a really powerful, evidence-based theory of how neural networks learn. Does this mean you should reject heuristic explanations as unrigorous, and not sufficiently evidence-based? No! In fact, we need such heuristics to inspire and guide our thinking. It’s like the great age of exploration: the early explorers sometimes explored (and made new discoveries) on the basis of beliefs which were wrong in important ways. Later, those mistakes were corrected as we filled in our knowledge of geography. When you understand something poorly – as the explorers understood geography, and as we understand neural nets today – it’s more important to explore boldly than it is to be rigorously correct in every step of your thinking. And so you should view these stories as a useful guide to how to think about neural nets, while retaining a healthy awareness of the limitations of such stories, and carefully keeping track of just how strong the evidence is for any given line of reasoning. Put another way, we need good stories to help motivate and inspire us, and rigorous in-depth investigation in order to uncover the real facts of the matter.

เคลื่อนย้ายไร้สัมผัสเชิงควอนตัม (quantum teleportation)ในรูปภาพ

อะไรจะเกิดขึ้นถ้านักวิทยาศาสตร์ใช้แผนภาพเทนเซอร์ (tensor diagram) แทนที่พีชคณิตเชิงเส้นในการทำความเข้าใจทฤษฎีควอนตัมแทน? การค้นพบการเคลื่อนย้ายไร้สัมผัสอาจจะง่ายกว่านี้ก็ได้

คำเตือน: โพสท์นี้สำหรับคนที่รู้จักทฤษฎีควอนตัมและเทนเซอร์อยู่แล้ว

หนึ่งในสิ่งแรกๆที่จะเจอถ้าศึกษาวิทยาการข้อมูลเชิงควอนตัมก็คือ ถ้ามีหนึ่งใน Bell state |\Phi^+ \rangle = |00\rangle + |11\rangle , เราสามารถส่งหนึ่งคิวบิต (qubit) แทนสองบิตและในทางกลับกันส่งสองบิตแทนหนึ่งคิวบิตได้ เป็นที่รู้จักกันในนามของการเข้ารหัสอย่างหนาแน่น (dense coding) และการเคลื่อนย้ายไร้สัมผัส (teleportation) ตามลำดับ จึงสามารถมองการเข้ารหัสอย่างหนาแน่นและการเคลื่อนย้ายไร้สัมผัสเป็นวิธีการสื่อสารที่ตรงข้ามกันได้

การเข้ารหัสอย่างหนาแน่นนั้นเข้าใจได้ไม่ยากเพราะ Hilbert space ของสองคิวบิตมีสี่มิติและสิ่งที่ผู้ส่งทำก็คือเข้าหนึ่งในสี่รหัสในหนึ่งในสี่มิตินั้น ซึ่งผู้รับสามารถแยะแยะแต่ละมิติได้อย่างแน่นอน ในขณะที่คำอธิบายปกติของการเคลื่อนย้ายไร้สัมผัสเชิงควอนตัมเป็นดังต่อไปนี้ (ให้ I เป็นเมทริกซ์เอกลักษณ์และ X,Z เป็นเมทริกซ์ Pauli และการวัดแบบ Bell คือที่มีสี่ Bell states เป็นผลที่เป็นไปได้: |\Phi^+ \rangle,X\otimes I|\Phi^+ \rangle,Z\otimes I|\Phi^+ \rangle,XZ\otimes I|\Phi^+ \rangle ):

การเคลื่อนย้ายไร้สัมผัสเชิงควอนตัม

1. ผู้ส่งกับผู้รับแชร์หนึ่ง Bell state |\Phi^+ \rangle ผู้ส่งต้องการส่ง state ของหนึ่งคิวบิต |\psi \rangle ที่ตนเองถืออยู่นอกเหนือจาก Bell state
2. ผู้ส่งทำการวัดแบบ Bell กับสองคิวบิตที่ตนเองถืออยู่
3. ผู้ส่งส่งผลการวัดสองบิตที่ได้ให้ผู้รับ
4. สองบิตนั้นบอกผู้รับว่า state ของคิวบิตที่ตนเองมีอยู่เป็น |\psi\rangle, X|\psi\rangle,Z|\psi\rangle หรือ XZ|\psi\rangle ทำให้ผู้รับสามารถแปลง state ของคิวบิตของตนเองเป็น |\psi \rangle ที่ต้องการได้

คุณสามารถนั่งเขียนทุกขั้นตอนที่ว่ามาเป็นคณิตศาสตร์และตรวจสอบว่ามันทำงานได้ตามที่โฆษณา แต่ก็อาจจะยังมีคำถามในใจว่า “ใครมันคิดขึ้นมาวะ”  ในโพสท์นี้เราจะเสนอการเคลื่อนย้ายไร้สัมผัสเชิงควอนตัมในรูปแบบของแผนภาพเทนเซอร์ที่อาจจะให้ความกระจ่างตรงนี้มากขึ้น

แผนภาพเทนเซอร์

แผนภาพเทนเซอร์เป็นวิธีการทำการคำนวณกับเทนเซอร์ของ Roger Penrose นักฟิสิกส์เชิงคณิตศาสตร์และนักคณิตศาสตร์ชาวอังกฤษ (1931-) ด้วยการวาดรูป

หน้าตาของแผนภาพเทนเซอร์จาก Roger Penrose The Road to Reality หน้า 241

หน้าตาของแผนภาพเทนเซอร์จาก Roger Penrose, The Road to Reality หน้า 241

ขาเส้นๆคือดัชนี (indices) ของเทนเซอร์ที่รอไปจับกับขาอื่นเพื่อการย่อของดัชนี (contraction)  ในที่นี้เราไม่ต้องการเทนเซอร์ซับซ้อนอะไรไปกว่าเวกเตอร์และเมทริกซ์  เราจะใช้ข้อตกลงของ Einstein ที่ละการเขียนเครื่องหมาย \sum_i เมื่อมีดัชนี i ซ้ำกันมากกว่าหนึ่งตัว (เพื่อไม่ให้ยุ่งยากเราจะไม่มีการแยกแยะดัชนีบนหรือล่าง)

กำหนดให้ (1) ขาเปิดด้านล่างเป็นเวกเตอร์ |\psi \rangle ใน Hilbert space \mathcal{H} (2) ขาเปิดด้านบนเป็นดูอัลเวกเตอร์ \langle \varphi| ใน \mathcal{H}^* การเอาขาของมันมาต่อกันก็คือการคำนวณ inner product นั่นเอง ซึ่งเป็นการย่อดัชนีด้วยการคูณด้วย Kronecker delta \delta_{ij} ดังนั้นขาเปล่าๆในรูป (3) ด้านล่างก็คือ \delta_{ij} |i\rangle \langle j| = I อย่างที่มันควรจะเป็น คราวนี้จะเกิดอะไรขึ้นถ้าเรางอขา? (4) คือ \delta_{ij} |ij\rangle = |\Phi^+ \rangle Bell state นั่นเอง! และ (5) เป็นดูอัล \langle \Phi^+|

tensor00

(1) |\psi \rangle (2) \langle \varphi| (3) \delta_{ij} |i\rangle \langle j| (4) \delta_{ij} |ij\rangle (5) \delta_{ij} \langle ij|

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

teleportation

แต่แผนภาพทางด้านขวาก็ไม่ใช่อะไรนอกจากการเคลื่อนย้ายไร้สัมผัสในกรณีที่การวัดแบบ Bell ของผู้ส่งได้ผล |\Phi^+ \rangle ! ส่วนในกรณีที่ได้ผลการวัดอื่นเราก็แค่เติมเมทริกซ์ Pauli เข้าไปและใช้เอกลักษณ์

transpose

T หมายถึง transpose

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

วิธีอื่นๆก็มีการแปลงวงจรควอนตัม (quantum circuit) ที่สลับสองคิวบิตเป็นวงจรควอนตัมของการเคลื่อนย้ายไร้สัมผัส หรือใช้ stabilizer formalism ก็ได้เพราะการเคลื่อนย้ายไร้สัมผัสใช้แต่ตัวกระทำการ Clifford (normalizer ของ Pauli group) แต่แผนภาพเทนเซอร์เป็นวิธีที่ทำให้เห็นว่าเกิดอะไรขึ้นชัดที่สุดแล้วที่เรารู้

การเข้ารหัสอย่างหนาแน่นหรือสลับ entanglement ก็วาดได้

dense_coding_ent_swap
(1) เข้ารหัสอย่างหนาแน่น (2) การสลับ entanglement คิวบิตซ้ายและขวาที่ไม่เคยเจอกันเลยสามารถ entangle กันได้เมื่อคนกลางทำการวัดแบบ Bell จริงๆมันก็คือ teleportation ของคิวบิตที่ entangle กับคิวบิตอื่นอยู่นั่นเอง

ถ้าเติมการส่งบิตไปด้วย (แสดงด้วยเส้นสีแดง) ก็จะเห็นความคล้ายกันของการเข้ารหัสอย่างหนาแน่นและการเคลื่อนย้ายไร้สัมผัส

dual_protocol

Kindergarten Quantum Mechanics ของ Bob Coecke เสนอว่าสาเหตุที่นักวิทยาศาสตร์ใช้เวลากว่า 60 ปีก่อนที่จะถามคำถามซึ่งนำไปสู่การค้นพบการเคลื่อนย้ายไร้สัมผัสเชิงควอนตัมเป็นเพราะภาษาที่เราใช้ในทฤษฎีควอนตัมตามปกติไม่ดีพอและเสนอการวาดรูปแบบนี้แทน (ซึ่งสามารถโยงกับภาษาในทฤษฎี category ได้)

บันไดสู่ความซับซ้อน

หลังจากเราเรียนวิชา Quantum Information Theory ตอนปริญญาตรีและ Quantum Computation ตอนเทอมแรกของปริญญาเอกจบ ซึ่งพูดถึงทั้งการประมวลผลข้อมูลง่ายๆที่ใช้ไม่กี่ qubits อย่าง superdense coding, teleportation และการเข้ารหัสลับ (quantum cryptography) และกระบวนการที่ซับซ้อนอย่างอัลกอริธึมแยกตัวประกอบของ Peter Shor หรือ อัลกอริธึมใช้ในการค้นหาของ Lov Grover ที่เร็วกว่าทุกๆอัลกอริธึมที่รู้จักบนคอมพิวเตอร์ธรรมดา และการแก้ความผิดพลาด (quantum error correction) ของควอนตัมคอมพิวเตอร์ ถึงแม้ประสบการณ์การเรียนรู้ในคลาสจะตื่นเต้นแต่คำถามใหญ่ที่ยังหลงเหลืออยู่ก็คือ ทำไม? ทำไมต้องเป็น superdense coding, teleportation, การเข้ารหัสลับ, อัลกอริธึม? อะไรกันแน่ที่เป็นหลักการที่เชื่อมโยงตัวอย่างที่แปลกแยกเหล่านี้เข้าด้วยกัน?

รู้จัก Game of Life ของ John H. Conway หรือเปล่า? มันเป็นโลกสองมิติที่ตีเป็นตารางสี่เหลี่ยมและมีกฎง่ายๆเพียงสี่ข้อเท่านั้นที่บอกว่าตารางสี่เหลี่ยมนี้จะเปลี่ยนสีอย่างไรขึ้นอยู่กับสี่เหลี่ยมที่อยู่ติดกัน แต่ด้วยกฎง่ายๆนี้ก็ให้กำเนิดแพทเทิร์นที่ซับซ้อนและสวยงามดั่งกับมีชีวิตออกมาได้

เราสามารถเข้าใจการกำเนิดของความซับซ้อนจากกฎที่เรียบง่ายนี้ได้หรือเปล่า?

ในฟิสิกส์อนุภาค นักวิทยาศาสตร์อยู่ที่พรมแดนทางความรู้เกี่ยวกับสิ่งที่เล็กที่สุด ในจักรวาลวิทยา นักวิทยาศาสตร์อยู่ที่พรมแดนทางความรู้เกี่ยวกับสิ่งที่ใหญ่ที่สุด ใน quantum information science นักวิทยาศาสตร์อยู่ที่พรมแดนทางความรู้เกี่ยวกับสิ่งที่ซับซ้อนที่สุดที่เกินกว่าสิ่งมีชีวิตคลาสสิคัลจะเข้าใจได้ (ถ้าเชื่อว่าสมองไม่ใช่ควอนตัมคอมพิวเตอร์) เราจะคิดถึงหน่วยเล็กๆของการประมวลผลข้อมูลอย่าง superdense coding หรือ teleportation เป็นหน่วยย่อยพื้นฐาน เบสิกที่สุดของ quantum information science ได้หรือไม่? และอะไรที่เรายังจะต้องค้นพบเพื่อเป็นบันไดจากหน่วยพื้นฐานไปยังปฏิบัติการที่ซับซ้อน?

Simple rules for a complex quantum world

Scientists’ current understanding of quantum mechanics is like that of a slow-learning student of chess. We’ve known the rules for more than 70 years, and we have a few clever moves that work in some special situations, but we’re only gradually learning the high-level principles that are needed to play a skillful overall game.

The discovery of these principles is the goal of quantum information science, a fundamental field that is opening up in response to a new way of comprehending the world. Many articles about quantum information science focus on technological applications: research groups “teleport” quantum states from one location to another. Other physicists use quantum states to create cryptographic keys that are absolutely secure from eavesdropping. Information scientists devise algorithms for hypothetical quantum-mechanical computers, much faster than the best known algorithms for conventional, or classical, computers.

These technologies are fascinating, but they obscure the fact that they are a by-product of investigations into deep new scientific questions.

พออ่านบทความนี้ เราก็ อ๋อ นี่คือสิ่งที่รู้สึกขาดไปจากคลาสนี่เอง และเป็นอะไรที่ค่อยๆมาซึมซับเอาเองภายหลังจากการคลุกคลีอยู่กับสังคมนักวิจัยในสาขา แม้แต่บทความของ Nielsen เอง (ที่เขียนเมื่อสิบกว่าปีที่แล้ว) ก็หยุดอยู่แค่ที่จุดเริ่มต้น ทฤษฎีการสร้าง entanglement ต่อยอดคุณสมบัติที่เรียบง่ายไปยังซับซ้อน ในทางกลับกันกระบวนการซับซ้อนก็ถูกถอดแยกชิ้นส่วนเพื่อทำความใจ อย่างอัลกอริธึมแยกตัวประกอบสามารถตีความเป็นอัลกอริธึมในการประมาณ phase (หรือพลังงาน) ได้

ปัจจุบันนักวิจัยมีความเข้าใจของบันไดสู่ความซับซ้อนนี้มากขึ้น Contextuality ที่เคยกล่าวถึงเป็นหนึ่งในปัจจัยของความซับซ้อนในการคำนวณ (computation complexity) แต่วิธีอื่นในการทำความเข้าใจก็มีหลากหลาย อย่างทฤษฎีความซับซ้อนในการสื่อสาร (communication complexity) หรือ quantum Shannon theory แต่สิ่งที่เหมือนๆกันในทุกๆวิธีก็คือต้องมีวิธีจัดการบัญชีนับทรัพยากร (resource) ที่ใช้ในการประมวลผลข้อมูล เราก็สามารถถามคำถามได้หลายแบบเกี่ยวกับธรรมชาติของแหล่งทรัพยากรเหล่านี้ แต่คำถามที่กว้างและลึกและน่าสนใจสำหรับเราที่สุดก็คืออะไรคือทรัพยากรที่หาได้เฉพาะจากทฤษฎีควอนตัม (กลศาสตร์ควอนตัม, ทฤษฎีสนามควอนตัม, ทฤษฎีแรงโน้มถ่วงควอนตัม)? อะไรคือทรัพยากรที่ทฤษฎีคลาสสิคัลก็มี? (อ่าน The Entanglement Frontier โดย John Preskill [สไลด์]) คำถามนี้ไม่ใช่คำถามที่ว่างเปล่าเพราะจากความรู้ในปัจจุบันเชื่อว่าคลาสสิคัลฟิสิกส์เป็นส่วนหนึ่งของควอนตัมฟิสิกส์ เพราะฉะนั้นไม่ใช่ทุกอย่างในทฤษฎีควอนตัมจะเป็นเชื้อเพลิงให้เทคโนโลยีทางควอนตัมที่แท้จริงได้ (อ่าน มหากาพย์ D-Wave กับข่าววิทยาศาสตร์)

สร้างเวบไซต์ส่วนตัวด้วย TiddlyWiki

ก่อนหน้านี้เราเคยเขียนถึง TiddlyWiki 5 ไปแล้ว ตอนนี้เรารู้แล้วว่าสามารถใช้มันสร้างเวบไซต์แบบ(เกือบ) static—คือ(เกือบ)เอาไว้แสดงผลอย่างเดียวอย่างที่เวบไซต์รวบรวมผลงานควรจะเป็น—ออกมาได้ดูดีพอสมควร

ทำยังไง? ก่อนอื่นเราอัพเกรด TiddlyWiki ของเราเป็นเวอร์ชัน 5.1.7 ก่อน (กรณีเราเพื่อใช้มาโครสารบัญ) การอัพโหลดขึ้น TiddlySpot ก็ยังง่ายและฟรี แต่จะมีปัญหาแปลกๆกับ MathJax ซึ่งมีคนบอกวิธีแก้ไว้ให้แล้ว จากนั้นก็เริ่มสร้างเวบไซต์

คราวนี้ก็เจอปัญหาหลักก็คือใครๆที่เข้ามาดูก็แก้ไข tiddler (แต่ละหน้าต่างใน TiddlyWiki) ได้! แต่มันไม่ใช่ปัญหาจริงๆเพราะถึงทุกคนจะแก้ไข tiddler และเซฟลงเครื่องตัวเองได้ แต่ถ้าไม่มีพาสเวิร์ดก็ไม่สามารถเซฟ TiddlyWiki ที่ถูกแก้ไขบนเวบได้

ปัญหาที่เหลือก็คือปุ่มเปิ่มต่างๆที่ใช้แก้ไขมันดูไม่สวยงามเลยและจะทำให้คนที่เข้ามาชมงงว่ามันเอาไว้ทำอะไร เราต้องการจะให้ tiddler กว้างเต็มจออย่างในรูปข้างบน (ด้วยลูกศรมุมบนขวา) จะได้ซ่อนแถบเครื่องมือด้านขวา แต่ปัญหาที่ตามมาก็คือเราไม่สามารถเซฟได้เพราะปุ่มเซฟมันอยู่ในแถบข้างๆที่ถูกซ่อนไปแล้ว วิธีที่เราใช้ก็คือเปิดการเซฟโดยอัตโนมัติและเหลือแค่ปุ่มแก้ไขที่เป็นไอคอนรูปปากกาอยู่มุมบนขวาของแต่ละ tiddler ดังในภาพข้างบน แล้วพอจะเซฟก็กดปุ่มแก้ไขแล้วกดออก TiddlyWiki ก็จะเซฟสู่ Tiddlyspot โดยอัตโนมัติ ไม่ต้องใช้ปุ่มเซฟ

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

ป.ล. ได้รับแรงบันดาลใจจากการไปเห็นเวบไซต์ของ Steve Flammia มา