2008/Jun/17

*เนื้อหาในเอ็นทรี่นี้สำหรับผู้มีความสนใจด้านคอมพิวเตอร์และคณิตศาสตร์ 

วันนี้ไปฟังบรรยายของ Prof. Mark Hall ที่จุฬาฯ เป็นเรื่องเกี่ยวกับ Equivalence ของ Turung Machine กับ Recursive Functions

คนที่เรียนคอมมาจะมีความรู้พื้นฐานอยู่แล้วว่า Turing Machine เป็นโมเดลต้นแบบของการสร้างคอมพิวเตอร์ ในการแก้ปัญหาใดๆ ก็ตาม คอมพิวเตอร์จะสามารถทำได้ ก็ต่อเมื่อ ทัวริ่งแมชชีนสามารถทำได้ แต่ในทางคณิตศาสตร์ การนิยามสิ่งต่างๆ โดยใช้ทัวริ่งแมชชีนยังถือว่าเป็น Informal Language อยู่ นิยามของทัวริ่งแมชชีนยังไม่มีความ rigorous เท่าที่ควร จึงมีความพยายามที่จะหาโมเดลที่ใช้ Formal Language ที่ Equivalent กับ Turing Machine มาใช้แทน และสิ่งนั้นก็คือ Recursive Function

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

จะขออนุญาต assume ว่าคนอ่านรู้จักทัวริ่งแมชชีนแล้ว หรือน่าจะหาข้อมูลเบื้องต้นเกี่ยวกับมันได้ไม่ยาก เพราะคงจะวุ่นวายน่าดู....ถ้าจะอธิบายทัวริ่งแมชชีนด้วยตัวหนังสือล้วนๆ 555

เทปที่เราจะป้อนให้กับทัวริงแมชชีนในที่นี้ จะใช้ลำดับของเลข 1 ติดกัน n+1 ตัวแทนจำนวนนับ n ยกตัวอย่างเช่น 3 จะแทนด้วย 1111 คือหนึ่งสี่ตัว 0 ก็จะแทนด้วย 1 เป็นต้น หากต้องการป้อนข้อมูลมากกว่าหนึ่งตัว ก็จะคั่นด้วย blank

ต่อไปเราจะมาทำความรู้จักกับ Partial function ซึ่งนิยามจาก Nk -> N ซึ่งจะต่างจากฟังก์ชันธรรมดาๆ ตรงที่ฟังก์ชันธรรมดาๆ นั้น ถ้าหยิบสมาชิกตัวใดใน Nk มาแทนในพาร์เชียลฟังก์ชัน จะต้องได้ผลลัพธ์ออกมาเป็นสมาชิกใน N แต่ Partial Function นั้นไม่จำเป็น อาจมีสมาชิกบางตัวใน Nk ที่แทนค่าในพาร์เชียลฟังก์ชันแล้วไม่ออกมาเป็นสมาชิกใน N

เราจะมอง TM เป็นพาร์เชียลฟังก็ชัน โดยมีอินพุทในเทปเป็นจำนวนนับ k ตัว อาจจะมีอินพุทบางชุดที่ผ่านกระบวนการใน TM แล้วไม่ออกมาเป็นสมาชิกใน N หรือวนอยู่ใน Infinite Loop ก็ได้

ส่วนที่สองที่จะพูดถึงคือ Recursive Function on N โดยเราจะเริ่มนิยามจากฟังก์ชันและโอเปอเรชันพื้นฐานก่อน

Initial functions มีสามตัว นั่นคือ

Successor function : S (คือการบวกเข้าไปอีก 1)

Projection function : Ink(m1,...,mn)=mk

Constant Function : Cpn(m1,...,mn)=p

Operations มีสามตัวเช่นกัน

Composition : ถ้าเรามี m-ary ฟังก์ชัน g และ k-ary ฟังก์ชัน f1,...,fn Composition of g with f1,...,fn คือ
f(n1,...,nk)=g(f1(n1,...,nk),...,fm(n1,...,nk))

Primitive Recursion : ถ้าเรามี k-ary ฟังก์ชัน g และ (k+2)-ary ฟังก์ชัน h เรานิยาม (k+1)-ary ฟังก์ชัน f โดย
f(0,n1,...,nk)=g(n1,...,nk)
f(m+1,n1,...,nk)=h(f(m,n1,...,nk),m,n1,...,nk)

Minimalization : ให้ (k+1)-ary ฟังก์ชัน g มา เราจะนิยาม k-ary ฟังก์ชัน f โดย
f(n1,...,nk)=min{ l | g(l,n1,...,nk)=0}

หลังจากนิยามทั้งสองอย่างนี้แล้ว เราก็จะนิยาม Recursive function ได้ดังนี้

"Partial functions f:Nk -> N จะ Recursive ก็ต่อเมื่อ f สามารถ construct จาก Initial functions โดยใช้เพียง Operations ที่กำหนดเอาไว้เท่านั้น (นั่นคือใช้เพียง Composition, Primitive Recursion, Minimalization)"

สำหรับตัวอย่างในการแสดงว่าฟังก์ชันซักตัวเป็น Recursive นั้นค่อนข้างวุ่นวายทีเดียว ยกตัวอย่างเช่นฟังก์ชัน "การบวก" ก็ต้องนิยามฟังก์ชันต่อเนื่องกันลงมาถึง 5 ตัวกว่าจะแสดงได้ = = จึงขอละเอาไว้ก็แล้วกัน ถ้าตัวไหนในพรู้ฟเค้าบอกว่ามัน Recursive ก็เชื่อๆ ไปละกันว่ามัน Recursive เพราะมันแสดงยาก (อยากกว่าทัวริ่งอ้ะ...- -")

ต่อไปเราก็จะมาดูไอเดียในการพรู้ฟประเด็นหลักในการบรรยายครั้งนี้ นั่นก็คือ

"Turing Machine Computable iff Recursive Function"

นั่นก็คือ..ปัญหาอะไรก็ตามที่สร้าง TM มาแก้ได้ ก็จะสร้าง Recursive Function มาแก้ได้เช่นกัน และในแง่กลับกัน ถ้ามี Recursive Function ก็จะสร้าง Turing Machine ที่ให้ผลแบบเดียวกันได้ด้วย

แรกสุดเราก็ต้องแสดงขาไปก่อน ว่า Recursive Function เป็น TM-computable ซึ่งตรงนี้ผู้บรรยายบอกว่าไม่ยาก เราสามารถสร้าง TM ที่ทำงานเหมือนๆ กับ Initial functions ทั้งสามตัวได้ง่ายๆ (อันนี้ง่ายจริง พอมองเห็นอยู่) จากนั้นเราก็สามารถ construct TM ตัวใหม่จาก TM ทั้งสามแบบนี้ โดยใช้เพียง operations Composition, Primitive Recursion, Minimalization ได้โดยง่ายเช่นกัน (อันนี้ลองส่องๆ ดูแล้ว...Composition ยังพอว่า ส่วนอีกสองอันคงง่ายสำหรับเขา...แต่ไม่ง่ายสำหรับเรา = =)

ส่วนขากลับจะยากกว่า นั่นคือการแสดงว่า TM-computable function จะ Recursive ไอเดียของเขาก็คือจะ encode ทุกสิ่งทุกอย่างใน TM ออกมาเป็นจำนวนนับ โดยมีรีเคอร์ซีฟฟังก์ชันสามตัวช่วยในการ encode (เชื่อๆ ไปเถอะว่ามัน Recursive) นั่นคือ

f1(m,n)=mn

f2(n)=nth prime number เราจะแทน ด้วย pn

f3(n,m)=เลขชี้กำลังของ pm ใน Prime factorization ของ n

*เผื่อใครลืม Prime factorization ก็คือการแยกตัวประกอบให้ทุกตัวอยู่ในรูปของจำนวนเฉพาะยกกำลัง มีทบ.ในทางคณิตศาสตร์ที่แสดงว่าสำหรับระบบจำนวนนับแล้ว จำนวนนับจำนวนหนึ่งๆ จะมี Prime Factorization อยู่เพียงรูปแบบเดียวเท่านั้น ไม่ซ้ำซ้อนกัน

TM ของเรานั้นจะประกอบด้วย Transition ต่างๆ ที่มีอยู่เป็นจำนวนจำกัด และ Transitions เหล่านั้นจะเป็น Quintuple ประกอบไปด้วย สถานะเริ่มต้น, ข้อมูลที่อ่าน, ข้อมูลที่เขียนทับ, ทิศทาง, สถานะที่เปลี่ยนไป ให้แทนทั้งหมดนี้ด้วยจำนวนนับทั้งหมด สมมติว่าออกมาเป็นจำนวนนับ a,b,c,d,e ตามลำดับ 

เราจะแทน Transitions แต่ละอันด้วยจำนวนนับ 2a3b5c7d11e สิ่งที่ได้ก็คือจำนวนนับที่ไม่ซ้ำกัน k ตัวที่แทน Transitions ทั้งหมด k Transitions เรียกว่า n1,...,nk (สันนิษฐานว่า n1,...,nk จะมีการเรียงลำดับเฉพาะบางอย่าง อาจจะเรียงจากน้อยไปมากหรือมากไปน้อย หรือใช้ลำดับอื่นๆ เพื่อให้ลำดับที่เกิดขึ้นใน TM ตัวหนึ่งๆ unique)

จากนั้น เราก็จะสร้างจำนวนนับที่สอดคล้องกับ TM เป็น 2n1 3n2...pknk

จะเห็นได้ว่ากระบวนการต่างๆ เพื่อให้ได้มาซึ่งการสร้างเลขที่ Encode มาจาก TM นั้น ใช้เพียง Recursive functions 3 ตัวที่กล่าวไว้ข้างต้นเท่านั้น TM-computable จึง Recursive.

ผลจากทฤษฎีนี้ อาจจะช่วยในการพิสูจน์ว่าปัญหาบางปัญหาว่าเป็น Machine Computable หรือไม่ โดยพิสูจน์ว่ามันเป็น Recursive Function แทนการสร้าง TM ขึ้นมารองรับ ซึ่งบางปัญหาอาจจะพิสูจน์ในแนวนี้ได้ง่ายกว่า ^ ^ 

Comment

Comment:

Tweet


#84 by (74.79.39.10|74.79.39.10) At 2014-06-28 01:20,
#83 by (190.148.136.210|95.211.218.103, 190.148.136.210) At 2014-06-28 01:19,
#82 by (91.232.12.90|95.211.218.103, 91.232.12.90) At 2014-06-28 01:19,
#81 by (109.202.15.100|95.211.218.103, 109.202.15.100) At 2014-06-26 19:02,
#80 by (110.232.82.132|95.211.218.103, 110.232.82.132) At 2014-06-26 19:00,
#79 by (177.137.136.10|95.211.218.103, 177.137.136.10) At 2014-06-26 18:58,
Very nice site! cheap goods
#78 by (200.50.170.2|200.50.170.2) At 2014-06-26 13:28,
#77 by (178.207.153.66|95.211.218.103, 178.207.153.66) At 2014-06-26 13:22,
#76 by (105.236.123.7|95.211.218.103, 105.236.123.7) At 2014-06-25 07:08,
#75 by (79.113.114.6|95.211.218.103, 79.113.114.6) At 2014-06-25 07:07,
#74 by (201.50.27.9|95.211.218.103, 201.50.27.9) At 2014-06-25 07:06,
#73 by (177.136.172.7|95.211.218.103, 177.136.172.7) At 2014-06-25 07:04,
#72 by (192.69.133.40|192.69.133.40) At 2014-06-24 00:53,
#71 by (54.201.112.7|95.211.218.103, 54.201.112.7) At 2014-06-24 00:52,
#70 by (189.82.131.84|95.211.218.103, 189.82.131.84) At 2014-06-24 00:51,
#69 by (41.220.28.51|95.211.218.103, 127.0.0.1, 41.220.28.51) At 2014-06-24 00:50,
#68 by (177.91.169.4|177.91.169.4) At 2014-06-22 18:12,
#67 by (162.253.111.5|95.211.218.103, 162.253.111.5) At 2014-06-22 18:11,
Very nice site! cheap goods http://oixypea2.com/oxovqxr/4.html
#66 by (85.185.42.3|95.211.218.103, 85.185.42.3) At 2014-06-22 12:28,
Very nice site! cheap goods
#65 by (195.49.151.78|195.49.151.78) At 2014-06-22 12:21,
#64 by (91.224.70.5|95.211.218.103, 91.224.70.5) At 2014-06-22 12:20,
#63 by (197.210.252.44|95.211.218.103, 197.210.252.44) At 2014-06-22 06:27,
#62 by (147.52.9.2|95.211.218.103, 147.52.9.2) At 2014-06-22 06:25,
#61 by (119.10.177.2|95.211.218.103, 119.10.177.2) At 2014-06-20 06:28,
Very nice site! cheap goods
#60 by (181.64.9.4|95.211.218.103, 181.64.9.4) At 2014-06-20 06:25,
#59 by (101.255.75.38|95.211.218.103, 101.255.75.38) At 2014-06-20 06:22,
#58 by (85.28.10.73|85.28.10.73) At 2014-06-19 18:03,
#57 by (175.111.91.19|192.168.11.77, 175.111.91.19) At 2014-06-19 18:00,
#56 by (103.11.35.5|103.11.35.5) At 2014-06-19 17:54,
#55 by (90.147.55.2|90.147.55.2) At 2014-06-19 17:53,
#54 by (192.237.212.15|95.211.218.103, 192.237.212.15) At 2014-06-19 12:25,
Very nice site!
#53 by (190.128.149.34|95.211.218.103, 190.128.149.34) At 2014-06-18 05:20,
#52 by (188.138.154.86|95.211.218.103, 188.138.154.86) At 2014-06-18 05:19,
#51 by (203.190.55.46|95.211.218.103, 203.190.55.46) At 2014-06-18 05:17,
Very nice site!
#50 by (204.228.129.46|95.211.218.103, 204.228.129.46) At 2014-06-17 23:23,
#49 by (110.173.49.18|95.211.218.103, 110.173.49.18) At 2014-06-17 23:19,
#48 by (213.125.163.138|213.125.163.138) At 2014-06-17 23:16,
Very nice site! <a href="http://yieapxo2.com/qoqsrx/1.html">cheap goods</a>
#47 by (218.108.242.108|95.211.218.103, 218.108.242.108) At 2014-06-17 17:21,
Very nice site! cheap goods http://aieypxo2.com/tovqrs/4.html
#46 by (103.242.2.24|95.211.218.103, 103.242.2.24) At 2014-06-17 05:36,
#45 by (177.21.238.94|95.211.218.103, 177.21.238.94) At 2014-06-17 05:34,
I'm seeking weblogs which all have fantastic guidance on what's popular and specifically what the top rated makeup is.. kdgdbgddcegaeceb
#44 by (193.67.216.241|193.67.216.241) At 2014-06-16 13:02,
#43 by (201.221.133.86|148.251.91.38, 201.221.133.86) At 2014-06-13 17:06,
#42 by (103.244.31.66|148.251.92.48, 103.244.31.66) At 2014-06-12 15:31,
#41 by (203.190.55.46|148.251.91.38, 203.190.55.46) At 2014-06-11 15:21,
#40 by (177.83.241.79|148.251.91.38, 177.83.241.79) At 2014-06-09 13:23,
#39 by (191.240.136.35|148.251.92.48, 191.240.136.35) At 2014-06-08 13:20,
#38 by (191.240.136.35|148.251.92.48, 191.240.136.35) At 2014-06-08 13:18,
#37 by (119.252.160.34|178.63.0.194, 119.252.160.34) At 2014-06-06 13:44,
#36 by (192.99.11.98|148.251.92.48, 192.99.11.98) At 2014-06-02 16:38,
#35 by (199.119.123.44|199.119.123.44) At 2014-06-01 17:42,