ทฤษฎีการคำนวณ (Theory of Computation)

ทฤษฎีการคำนวณ (Theory of Computation) เป็นหนึ่งในเนื้อหาที่สําคัญของทั้งทางด้านวิทยาการคอมพิวเตอร์ และด้านวิศวกรรมคอมพิวเตอร์ย้อนกลับไปในสมัยเริ่มแรกประมาณปีคริสต์ศักราช 1960 ที่มีการนําคอมพิวเตอร์มาประยุกต์ใช้งานในการแก้ปัญหาที่มีความซับซ้อน ซึ่งต้องใช้เวลา นานในการแก้ตัวอย่างเช่น การคํานวณเส้นโคจรของกระสวยอวกาศ การควบคุมการวัด และการส่งข้อมูลทางไกล คําถามที่เกิดขึ้นในสมัยนั้นคือ ปัญหาลักษณะไหนที่ไม่สามารถใช้ คอมพิวเตอร์แก้ปัญหาได้ ได้มีการนําเสนอรูปแบบการจําลองการคํานวณเพื่ออธิบาย การทํางานของคอมพิวเตอร์แล้วได้ใช้รูปแบบการจําลองนั้นในการตอบปัญหาว่าปัญหาใด สามารถแก้ได้หรือแก้ไม่ได้โดยการใช้คอมพิวเตอร์ ดังนั้นทฤษฎีการคํานวณจะประกอบไปด้วย

เนื้อหาสองส่วนหลักคือ รูปแบบการคํานวณ และความซับซ้อนของการคํานวณ โดยเนื้อหา ในส่วนหลังจะกล่าวถึงลักษณะของปัญหาที่แก้ได้และแก้ไม่ได้ความยากง่ายในการแก้ปัญหา เวลาและปริมาณพื้นที่ที่จําเป็นต้องใช้ในการแก้ปัญหา ซึ่งต้องอาศัยรูปแบบจําลองการคํานวณ ในส่วนแรกในการอธิบาย ดังนั้นเนื้อหาในส่วนหลังจะมีการจัดสอนในระดับบัณฑิตศึกษา ในสาขาวิชาที่เกี่ยวข้องเนื้อหาในหนังสือเล่มนี้จะกล่าวถึง รูปแบบการคํานวณซึ่งประกอบไปด้วย เครื่องสถานะจํากัด เครื่องสถานะจํากัดแบบดันลง และเครื่องจักรทัวร์ริ่ง ซึ่งในแต่ละรูปแบบ จะมีลักษณะที่เป็นทั้งแบบเชิงกําหนดและเชิงไม่กําหนด การอธิบายความสามารถของ แต่ละรูปแบบการคํานวณจะอาศัยการรู้จักภาษา หรือความสามารถในการตรวจสอบการ เป็นสมาชิกของคําในภาษา ซึ่งภาษาดังกล่าวจะเป็นภาษาที่อธิบายได้ใน ทฤษฎีภาษารูปนัย (Formal languagetheory) ซึ่งแบ่งแยกความซับซ้อนของภาษาตามลักษณะและรูปแบบ ของคําในภาษารูปนัยที่จะกล่าวถึงในเนื้อหาจะประกอบไปด้วย ภาษาพื้นฐาน ภาษาที่ไม่มี บริบท ภาษาที่เครื่องจักรทัวร์ริ่งรู้จัก และภาษาที่เครื่องจักรทัวร์ริ่งตัดสินได้เนื่องจากภาษาเป็นแบบรูปนัย จึงสามารถแสดงในรูปแบบสัญลักษณ์หรือนิพจน์ได้ตัวอย่างของนิพจน์ หรือสัญลักษณ์ในการแสดงแทนภาษาได้แก่นิพจน์พื้นฐาน ไวยากรณ์ที่ไม่มีบริบท เป็นต้น

บทที่ 1 พื้นฐาน

เนื้อหาในบทนี้เราจะอธิบายพื้นฐานทางคณิตศาสตร์ที่จำเป็นในการทำความเข้าใจเนื้อหาในบทต่อ ๆ ไป เรื่องที่จะศึกษาในส่วนนี้จะครอบคลุมในเรื่องของเซต ลำดับและคู่ลำดับ ฟังก์ชันและความสัมพันธ์กราฟ คำและภาษา การพิสูจน์ในแบบต่าง ๆ โดยเฉพาะการพิสูจน์แบบอุปนัยเชิงคณิตศาสตร์ซึ่งเป็นเครื่องมือสำคัญในการพิสูจน์ทฤษฎีต่อ ๆ ไป

เซต

เซต คือกลุ่มของสิ่งต่าง ๆ ที่รวมกันเป็นหน่วยเดียวกัน ซึ่งสิ่งที่อยู่ในกลุ่มจะถูกเรียกว่า สมาชิกของเซต การแสดงหรืออธิบายเซตมีอยู่ด้วยกันสองวิธีที่เป็นมาตรฐาน แบบแรก คือ แบบแจกแจงสมาชิก (Roster form หรือ Tabular form) พิจารณาตัวอย่างเซต S ของตัวเลข จํานวนเต็มคู่ที่มากกว่า 2 แต่น้อยกว่า 17 สามารถแสดงแบบแจกแจงสมาชิกได้ดังนี้

S = {4, 6, 8, 10, 12, 14, 16}

แบบที่สองคือ แบบแสดงนิยาม (Rule form หรือ Set builder form) ซึ่งจะแสดงเซตในรูป แบบแสดงการเป็นสมาชิกโดยอาศัยนิยามการเป็นสมาชิกแทน สําหรับเซต S สามารถแสดง ในรูปแบบแสดงนิยามได้ดังนี้

S = {x เป็นจํานวนเต็มคู่ 12 < x < 17}

ลำดับและคู่ลำดับ

ลำดับ (Sequence) ของสิ่งต่าง ๆ คือ รายการของสิ่งของที่ถูกเรียงลำดับ ตามคุณลักษณะบางอย่างของสิ่งของ ตัวอย่างเช่น เซตของตัวเลข {3, 7, 4, 5, 1} สามารถเขียนเป็นลำดับสมาชิก

บทที่ 2 เครื่องสถานะจำกัด

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

บทที่ 3 ภาษาพื้นฐาน

ในบทนี้เราจะกล่าวถึงคุณสมบัติต่าง ๆ ของภาษาพื้นฐานโดยเริ่มที่ นิพจน์พื้นฐาน (Regularexpression) ซึ่งเป็นนิพจน์สำหรับอธิบายภาษาพื้นฐาน (Regular language) นิพจน์ดังกล่าวจะมีความสามารถในการอธิบายภาษาได้เช่นเดียวกันกับเครื่องสถานะจำกัด ซึ่งเนื้อหาในส่วนนี้ก็จะครอบคลุมเรื่องการพิสูจน์การเท่าเทียมกันของนิพจน์พื้นฐานกับเครื่องสถานะจำกัดด้วยต่อมาเราจะศึกษาภาษาที่ทั้งนิพจน์พื้นฐานและเครื่องสถานะจำกัดไม่สามารถอธิบายได้หรืออีกนัยหนึ่งคือภาษาที่ไม่ใช่ภาษาพื้นฐาน การพิสูจน์ว่าภาษาที่กำหนดให้เป็นภาษาพื้นฐานหรือไม่เราจะอาศัยทฤษฎีPumping lemma ช่วยในการพิสูจน์นอกจากนั้นเราจะศึกษาตัวดำเนินการปิดสำหรับภาษาพื้นฐานเพื่อนำไปใช้ประโยชน์สำหรับตีความว่าภาษาที่พิจารณาเป็นภาษาพื้นฐานหรือไม่ด้วยเช่นกัน ในส่วนสุดท้ายของบทนี้ เราจะศึกษาการลดทอนเครื่องสถานะจำกัด (State minimization) ซึ่งจะมีประโยชน์ในการทดสอบว่า ภาษาพื้นฐานสองภาษาเป็นภาษาเดียวกันหรือไม่เนื่องจากถ้าภาษาสองภาษามีเครื่องสถานะจำกัดเหมือนกันแสดงว่าเป็นภาษาเดียวกัน ดังนั้นถ้าเราลดทอนเครื่องสถานะจำกัดของสองภาษาแล้วมีลักษณะเหมือนกันแสดงว่าภาษาทั้งสองเป็นภาษาเดียวกัน

บทที่ 4 ภาษาที่ไม่มีบริบท

ในบทนี้เราจะศึกษาภาษาที่ไม่มีบริบท (Context-free language) ซึ่งเป็นภาษาที่ซับซ้อนมากกว่าภาษาพื้นฐาน กล่าวคือมีภาษาที่ไม่อยู่ในภาษาพื้นฐานแต่อยู่ในภาษาที่ไม่มีบริบท เราจะเริ่มต้นแนะนำไวยากรณ์สำหรับภาษา (Language grammar) การสร้างคำจากไวยากรณ์ในรูปแบบการสร้างที่แตกต่างกัน ความสับสนของไวยากรณ์(Ambiguity of grammar) จากนั้นจะอธิบายภาษาพื้นฐานในรูปแบบไวยากรณ์ที่เรียกว่า ไวยากรณ์สำหรับภาษาพื้นฐาน (RegularGrammar) ต่อด้วยการอธิบายภาษาที่ไม่มีบริบทโดยอาศัยภาษาพื้นฐานก่อน เพื่อพิสูจน์ว่าทุกภาษาที่เป็นภาษาพื้นฐานก็คือภาษาที่ไม่มีบริบท

บทที่ 5 เครื่องสถานะจำกัดแบบดันลง

เช่นเดียวกันกับนิพจน์พื้นฐานซึ่งเท่าเทียมกันกับเครื่องสถานะจำกัดในเรื่องการเป็นสมาชิกของคำในภาษา ไวยากรณ์ที่ไม่มีบริบทก็จะมีเครื่องจักรที่มีความเท่าเทียมกันในเรื่องการอธิบายความหมายของภาษา ซึ่งในที่นี้คือภาษาที่ไม่มีบริบท โดยที่เครื่องจักรดังกล่าวที่จะศึกษาในบทนี้คือ เครื่องสถานะจำกัดแบบดันลง (Push-Down automata) [Schützenberger, 1963]เช่นเดียวกันกับเครื่องสถานะจำกัดซึ่งมีสองแบบคือแบบเชิงกำหนด (Deterministic) และแบบเชิงไม่กำหนด (Nondeterministic) เครื่องสถานะจำกัดแบบดันลงก็จะมีทั้งแบบเชิงกำหนดและเชิงไม่กำหนด แต่ที่แตกต่างกันคือทั้งสองแบบจะมีความสามารถไม่เท่ากัน

บทที่ 6 เครื่องจักรทัวร์ริ่ง

เครื่องจักรทัวร์ริ่ง (Turing machine) [Turing, 1937] เป็นรูปแบบจําลองเครื่องจักรที่ คิดค้นและนําเสนอขึ้นในปีคริสต์ศักราช 1936 โดย อลัน ทัวร์ริ่ง นักคณิตศาสตร์และ นักวิทยาการคอมพิวเตอร์ชาวอังกฤษ มีลักษณะการทํางานเหมือนกับเครื่องจักรสถานะจํากัด (Finite Automata) แต่มีความสามารถมากกว่าตรงที่มีขนาดในการเก็บของข้อมูล ที่ไม่จํากัด และวิธีการอ่านหรือบันทึกข้อมูลลงในที่เก็บข้อมูลไม่ได้ถูกจํากัดให้เป็น แบบลักษณะใดลักษณะหนึ่ง เช่น เดียวกันกับเครื่องจักรสถานะจํากัดแบบดันลง (Push-Down automata) ซึ่งจํากัดให้การเข้าถึงข้อมูลต้องเป็นแบบเรียงซ้อนทับกันเท่านั้น

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

หนังสือเล่มนี้จะเน้นความเข้าใจในเรื่องทฤษฎีรูปแบบการคํานวณจึงครอบคลุม การพิสูจน์ในทฤษฎีที่เกี่ยวข้องและจําเป็นแทบทุกทฤษฎี จึงเหมาะสําหรับนักศึกษาใน ระดับปริญญาเพื่อใช้ในการประกอบการเรียนในรายวิชาที่เกี่ยวข้อง สําหรับนักศึกษาใน ระดับบัณฑิตศึกษาในการเป็นพื้นฐานสําหรับการศึกษาเรื่องทฤษฎีความซับซ้อน และผู้สนใจ ในการเป็นหนังสืออ้างอิงในการศึกษาและเข้าใจในทฤษฎีการคํานวณสั่งซื้อหนังสือ

ผู้เขียน

รองศาสตราจารย์ ดร.พงศ์พันธ์ กิจสนาโยธิน

อาจารย์ประจำภาควิศวกรรมไฟฟ้าและคอมพิวเตอร์ คณะวิศวกรรมศาสตร์
มหาวิทยาลัยนเรศวร

Soraya S.

Writer

Graphic Design และ Content Creator ที่หลงใหลในการเขียน Content และเชื่อว่า Content เป็นสิ่งสำคัญในการสื่อสารกับทุก ๆ คน