Halting problem เป็นชื่อปัญหาที่ classic มากทางด้าน algorithm

Halt หมายถึง การหยุด ดังนั้น Halting problem คือ ปัญหาเกี่ยวกับการหยุด ปัญหาข้อนี้มีที่มาจาก มีผู้ตั้งปัญหาว่า เราสามารถสร้างเครื่องที่สามารถบอกได้ว่า algorithm ใดๆ จะสามารถให้คำตอบได้หรือไม่ ตัวอย่างของการไม่ได้คำตอบ เช่น ติด loop, หาไปเรื่อยๆไม่มีที่สิ้นสุด เป็นต้น การให้คำตอบแปลว่า algorithm จบการทำงาน (halt) นั่นเอง

Alan Turing เป็นผู้ prove ว่า ไม่สามารถทำเครื่องนี้ขึ้นมาได้ โดยใช้วิธี contradiction

นิยามเบื้องต้น
halt คือ algorithm ให้คำตอบได้ ว่า จริง หรือ เท็จ
loop คือ algorithm ให้คำตอบไม่ได้

1. สมมติ ให้เครื่องนี้มีอยู่จริง โดยรับ input เป็น "algorithm" กับ "input ของ algorithm" แล้วให้ผลลัพธ์เป็น จริง หรือ เท็จ หรือเขียนเป็น function ได้ว่า f(a,b) เมื่อ f แทนเครื่อง, a แทน algorithm, b แทน input สำหรับ algorithm
   ตัวอย่าง ให้ input เป็น algorithm A และ input สำหรับ algorithm เป็น B
   เครื่องจะตอบว่า "จริง" เมื่อ ใส่ input B ให้ algorithm A แล้ว ได้คำตอบ (halt)
   เครื่องจะตอบว่า "เท็จ" เมื่อ ใส่ input B ให้ algorithm A แล้ว ไม่ได้คำตอบ (loop)
   
2. สมมติเพิ่มใหม่ ให้มี เครื่อง g ที่รับ input เป็น algorithm x ให้ output เป็น จริง เมื่อ f(x,x) ให้ output เป็น เท็จ นอกจากนั้น เครื่องจะวน loop
   ตัวอย่าง ให้ input เป็น algorithm A
   เครื่องจะตอบว่า "จริง" เมื่อ ใส่ A ให้ algorithm A แล้ว ไม่ได้คำตอบ (f(A,A) = false)
   เครื่องจะตอบว่า "loop" เมื่อ ใส่ A ให้ algorithm A แล้ว ได้คำตอบ (f(A,A) = true)
   
   จะเห็นได้ว่า เครื่อง g นี้ ทำงานคล้ายๆกับเครื่อง f แต่จำกัดตัว "input ของ algorithm x" ให้เป็นตัว algorithm x เองเท่านั้น และให้ผลตรงข้ามกับ เครื่อง f
   
3. การทำงานของทั้งเครื่อง f และ g เขียนแทนได้ด้วย algorithm f และ g ตามลำดับ
   เราจะทดลองให้ input ของเครื่อง g เป็น algorithm g เอง
   ถ้า f(g,g) เป็น เท็จ เครื่อง g จะตอบว่า จริง แต่ จากนิยามของเครื่อง f บอกว่า เครื่อง f จะตอบผลออกมาเป็นเท็จ เมื่อ algorithm ซึ่งในที่นี้ คือ g เป็น loop ในขณะที่ g ตอบเราออกมาได้ว่า จริง แสดงว่า g นั้น halt ดังนั้น เกิดการขัดแย้งขึ้นที่ g
   ถ้า f(g,g) ให้ผลเป็น จริง เครื่อง g จะ loop แต่ จากนิยามของเครื่อง f บอกว่า เครื่อง f จะตอบผลออกมาเป็นจริง เมื่อ algorithm ซึ่งในที่นี้คือ g นั้น halt แต่ g กลับวน loop จึงเกิดการขัดแย้งขึ้นที่ g
   
   เนื่องจากเกิดการขัดแย้งขึ้นทั้ง f(g,g) เป็นเท็จ และ f(g,g) เป็นจริง แสดงว่าที่สมมติข้างต้นว่ามี เครื่อง f นั้น ไม่เป็นจริง จึงสรุปได้ว่า "ไม่สามารถสร้าง algorithm ที่แก้ปัญหานี้ (halting problem ได้"

ปัญหาใดๆ ที่เข้าในลักษณะของ halting problem จะเป็นปัญหาที่ไม่สามารถหา algorithm มาแก้ได้ ซึ่งหมายถึงว่า เราไม่สามารถเขียนโปรแกรมให้แก้ปัญหาเหล่านี้ได้นั่นเอง

ข้อมูลเพิ่มเติม http://en.wikipedia.org/wiki/Halting_problem

文部科学省 อ่านว่า Monbukagakusho หมายถึง Ministry of Education, Culture, Sports, Science and Technology (MEXT) เป็นกระทรวงของญี่ปุ่นที่รับผิดชอบดูแลการให้ทุนนี้

วัตถุประสงค์
Monbugakusho Scholarship คือทุนที่เดิมเรียกกันว่า ทุนมอนบุโช หรือ ทุนรัฐบาลญี่ปุ่นนั่นเอง ทุนนี้เป็นทุนให้เปล่ากับประเทศต่างๆ ใ็ห้นักศึกษาไปเรียนที่มหาวิทยาลัยในญี่ปุ่น เพื่อส่งเสริมการแลกเปลี่ยนระหว่างประเทศ ในด้านการศึกษา วิทยาศาสตร์และวัฒนธรรม อันจะช่วยส่งเสริมความเข้าใจดีต่อกันและกระชับความสัมพันธ์ระหว่างประเทศต่างๆ และญี่ปุ่นให้แน่นแฟ้นยิ่งขึ้น

ประเภทของทุน
ทุนมอนบุโช แบ่งเป็น 7 ประเภท แต่ที่นักเรียนสายสามัญทั้งหลายสอบๆกันมากๆคือ Undergraduate (ปริญญาตรี) กับ Research Student (ปริญญาโท-เอก)

Undergraduate
ว่ากันว่า เมื่อก่อน ระดับปริญญาตรี ทุนนี้ให้ประมาณ 15 ทุน แต่เนื่องจากเด็กสละสิทธิ์กันมาก หรือไม่ก็นโยบายเปลี่ยน ทำให้ทุนระดับปริญญาตรีลดลงเหลือราวๆ 7-8 ทุน แบ่งเป็น 2 สายหลัก คือ ศิลป์ และ วิทย์ วิชาที่ต้องสอบคือ ภาษาอังกฤษ, คณิตศาสตร์ และวิชาแล้วแต่สาขาที่เลือก

Research Student
สำหรับระดับ Research Student จริงๆแล้วคำว่า Research Student คือ สถานะนักศึกษาที่ยัีงไม่ใช่นักศึกษาปริญญา (non-degree) สำหรับนักเรียนที่ได้ทุนมอนบุโช จะได้ไปเรียนภาษาที่ญี่ปุ่น และเข้าสังกัด lab โดยมีสถานะเป็น research student ก่อน แล้วจึงสอบเข้ามหาวิทยาลัย อย่างไรก็ตาม บางมหาวิทยาลัย ก็ยกเว้นให้ไม่ต้องสอบ รายละเอียดหาได้จากเวบของมหาวิทยาลัย หลังจากเข้าได้จึงจะมีสถานภาพเป็นนักศึกษาปริญญาโท หรือ เอก

ในระดับนี้ ก็มีการแบ่งสาขาเช่นกัน แต่แบ่งเป็น 3 สาขา โดยมีวิทยาศาสตร์ และแยกสังคมศาสตร์กับมนุษยศาสตร์ออกจากัน วิชาที่สอบก็ขึ้นกับสาขาที่เรียน และ้ ไม่อนุญาตให้เปลี่ยนสาขาในการศึกษาต่อ (คือ จบมาด้านใด ก็ต้องต่อด้านนั้น)

การสมัคร
การได้รับทุนมอนบุโชของ Research Student มี 2 วิธี คือ ได้ recommendation จากสถานทูตญี่ปุ่นในประเทศของตน หรือ ได้ recommendataion จากมหาวิทยาลัยในญี่ปุ่น

วิธีแรก ขึ้นกับสถานทูตในประเทศจะดำเนินการ ซึ่ง สำหรับประเทศไทย ใช้การสอบคัดเลือก
วิธีที่สอง โดยปกติแล้ว มหาวิทยาลัยจะให้ advisor ส่งรายชื่อคนที่จะขอทุนมา แล้วส่งไปให้ MEXT อนุมัติ ดังนั้น คนที่ได้ก็มักจะเป็นนักศึกษาที่อยู่ที่ญี่ปุ่นอยู่แล้ว และ prof. รู้จักฝีมือดี เ่ช่น เป็น Research Student ของ lab

Note : สถานทูตญี่ปุ่นประกาศรับสมัครผู้รับทุนสำหรับปีการศึกษา 2006 แล้ว ติดตามข้อมูลเพิ่มเติมได้ที่ http://embjp-th.org/th/jics/study.htm