ทฤษฎีการคำนวณ

การศึกษาเกี่ยวกับ **ทฤษฎีการคำนวณ** เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น

ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation)

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

นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้

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

นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ไม่พึ่งบริบท (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด

โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ไม่พึ่งบริบทได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky

ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้. ถ้ากลุ่ม **X** เป็นซับเซ็ตแท้ของ **Y** เราจะแสดง **X** ด้านล่าง **Y** และมีเส้นทึบเชื่อมระหว่างสองกลุ่ม. ถ้า **X** เป็นซับเซ็ตแต่ไม่ทราบแน่นอนว่าจะเท่ากันหรือไม่ เราจะเชื่อมด้วยเส้นที่บางกว่าและเป็นเส้นประ.




ปัญหาการตัดสินใจ



ไฟล์:solidLine.png

ไฟล์:solidLine.png


Type 0 (Recursively enumerable)

Undecidable


ไฟล์:solidLine.png


Decidable


ไฟล์:solidLine.png


EXPSPACE


ไฟล์:dottedLine.png


EXPTIME


ไฟล์:dottedLine.png


พีสเปซ


ไฟล์:solidLine.png
ไฟล์:solidLine.png
ไฟล์:dottedLine.png
ไฟล์:dottedLine.png

ไฟล์:dottedLine.png

ไฟล์:dottedLine.png


Type 1 (Context Sensitive)
ไฟล์:solidLine.png
ไฟล์:dottedLine.png
ไฟล์:dottedLine.png

ไฟล์:dottedLine.png

พีสเปซบริบูรณ์


ไฟล์:solidLine.png
ไฟล์:solidLine.png
ไฟล์:dottedLine.png
ไฟล์:dottedLine.png

ไฟล์:dottedLine.png


ไฟล์:solidLine.png
ไฟล์:solidLine.png
โค-เอ็นพี
ไฟล์:dottedLine.png

เอ็นพี


ไฟล์:solidLine.png
ไฟล์:solidLine.png
ไฟล์:dottedLine.png
ไฟล์:dottedLine.png

ไฟล์:dottedLine.png

ไฟล์:dottedLine.png


ไฟล์:solidLine.png
ไฟล์:solidLine.png
ไฟล์:dottedLine.png
BPP

BQP

เอ็นพีบริบูรณ์


ไฟล์:solidLine.png
ไฟล์:solidLine.png
ไฟล์:dottedLine.png
ไฟล์:dottedLine.png

ไฟล์:dottedLine.png


ไฟล์:solidLine.png
ไฟล์:solidLine.png
พี


ไฟล์:solidLine.png
ไฟล์:solidLine.png
ไฟล์:dottedLine.png

ไฟล์:dottedLine.png


ไฟล์:solidLine.png
NC

พีบริบูรณ์


ไฟล์:solidLine.png
ไฟล์:solidLine.png


Type 2 (Context Free)


ไฟล์:solidLine.png


Type 3 (Regular)



## อ้างอิง

* Garey, Michael R., and David S. Johnson: *Computers and Intractability: A Guide to the Theory of NP-Completeness.* New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
* Hein, James L: *Theory of Computation.* Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
* Hopcroft, John E., and Jeffrey D. Ullman: *Introduction to Automata Theory, Languages, and Computation.* Reading, MA: Addison-Wesley, 1979. One of the standard references in the field.
* Taylor, R. Gregory: *Models of Computation.* New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
* The Complexity Zoo : A huge list of complexity classes, as reference for experts.
* Computability Logic : A theory of interactive computation. The main web source on this new subject.

## ดูเพิ่ม
* Computability logic
* Interactive computation
* Important publications in computability
* Open problems in computability
* Calculation

ทฤษฎีการคำนวณ