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

การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น
ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation)
ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทางฟังก์ชันเวียนบังเกิด ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลแลมดาแคลคูลัสใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น ขั้นตอนวิธีของมาคอฟและระบบของโพสต์ที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ
นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง  ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้
ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ปัญหาความสัมพันธ์ของโพสต์) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ
นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ไม่พึ่งบริบท  ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง  เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด
โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ไม่พึ่งบริบทได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky
ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้. ถ้ากลุ่ม X เป็นซับเซ็ตแท้ของ Y เราจะแสดง X ด้านล่าง Y และมีเส้นทึบเชื่อมระหว่างสองกลุ่ม. ถ้า X เป็นซับเซ็ตแต่ไม่ทราบแน่นอนว่าจะเท่ากันหรือไม่ เราจะเชื่อมด้วยเส้นที่บางกว่าและเป็นเส้นประ.
<table cellpadding="0" cellspacing="0" border="0" align = "center">
<tr align = "center">
<td colspan = 2></td>
<td colspan = 4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center">ปัญหาการตัดสินใจ</td></tr></table></td>
</tr>
<tr align = "center">
<td colspan = 2></td>
<td></td>
<td colspan = 2></td>
<td></td>
</tr>
<tr align = "center">
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
<td></td>
<td colspan = 4><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
</tr>
<tr align = "center">
<td colspan = 3></td>
</tr>
<tr align = "center">
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
</tr>
<tr align = "center">
<td colspan = 3></td>
</tr>
<tr align = "center">
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
</tr>
<tr align = "center">
<td colspan = 3></td>
</tr>
<tr align = "center">
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
</tr>
<tr align = "center">
<td colspan = 3></td>
</tr>
<tr align = "center">
<td colspan = 8><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">พีสเปซ</td></tr></table></td>
</tr>
<tr align = "center">
<td></td>
<td width = 40></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr align = "center">
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
<td></td>
<td></td>
<td border="1"></td>
<td></td>
<td></td>
<td></td>
<td colspan = 1><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">พีสเปซบริบูรณ์</td></tr></table></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">โค-เอ็นพี</td></tr></table></td>
<td></td>
<td></td>
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">เอ็นพี</td></tr></table></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
<td width = 10></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
<td width = 10></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">เอ็นพีบริบูรณ์</td></tr></table></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
<td></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td colspan = 6><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">พี</td></tr></table></td>
</tr>
<tr align = "center">
<td></td>
<td></td>
<td></td>
<td colspan = 4></td>
<td></td>
</tr>
<tr align = "center">
<td></td>
<td colspan = 2><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
<td colspan = 4></td>
<td><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width = "100%" height="100%"><tr><td align = "center">พีบริบูรณ์</td></tr></table></td>
</tr>
<tr align = "center">
<td></td>
<td colspan = 2></td>
</tr>
<tr align = "center">
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
</tr>
<tr align = "center">
<td colspan = 3></td>
</tr>
<tr align = "center">
<td colspan = 3><table cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width = "100%" height="100%"><tr><td align = "center"></td></tr></table></td>
</tr>
</table>