ทฤษฎีการคำนวณและสัจพจน์

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ทฤษฎีการคำนวณและสัจพจน์

ทฤษฎีการคำนวณ vs. สัจพจน์

การศึกษาเกี่ยวกับ ทฤษฎีการคำนวณ เริ่มขึ้นเมื่อต้นศตวรรษที่ยี่สิบ ก่อนจะมีการคิดค้นคอมพิวเตอร์อิเล็กทรอนิกส์ขึ้น ในช่วงเวลาดังกล่าว นักคณิตศาสตร์ได้เริ่มศึกษาว่า ปัญหาทางคณิตศาสตร์ใดบ้างที่สามารถแก้ได้ด้วยวิธีพื้นฐาน และปัญหาใดที่ไม่สามารถแก้ได้ ขั้นตอนแรกก็คือการนิยามให้ได้ว่าวิธีพื้นฐานในการแก้ปัญหานั้นคืออะไรบ้าง นั่นคือ พวกเขาต้องการโมเดลอย่างเป็นทางการของการคำนวณ (formal model of computation) ได้มีการสร้างโมเดลในรูปแบบต่างๆ มากมาย โมเดลเครื่องจักรทัวริงมองการคำนวณเป็นการทำงานของเครื่องจักรที่ทำงานบนเทปเก็บตัวอักษรที่มีความยาวไม่จำกัด โดยมีหัวอ่าน/เขียนที่จะทำงานกับช่องบนเทปทีละช่อง อีกโมเดลหนึ่งพิจารณาการคำนวณผ่านทางฟังก์ชันเวียนบังเกิด ซึ่งใช้ฟังก์ชันและการประกอบกัน (composition) ของฟังก์ชันที่ทำงานบนตัวเลข โมเดลแลมดาแคลคูลัสใช้วิธีคล้ายๆกัน นอกจากนี้ยังมีโมเดลอื่นๆ เช่น ขั้นตอนวิธีของมาคอฟและระบบของโพสต์ที่ใช้ไวยากรณ์บนสตริง โมเดลทางการต่างๆเหล่านี้ได้รับการแสดงว่ามีความสามารถเทียบเท่ากัน นั่นคือ การคำนวณใดๆที่กระทำได้โดยโมเดลหนึ่งจะสามารถทำได้ในอีกโมเดลด้วยเช่นกัน โมเดลเหล่านี้ยังมีความสามารถเท่ากันกับเครื่องคอมพิวเตอร์ทั่วไปที่เราใช้อยู่ ถ้าเราสมมติว่าเครื่องคอมพิวเตอร์นั้นมีหน่วยความจำไม่รู้จบ นอกจากนี้ ยังเป็นที่เชื่อกันอีกว่า ทุกๆ โมเดลการคำนวณที่ "สมเหตุสมผล" จะมีความสามารถเทียบเท่ากับเครื่องจักรทัวริ่ง ซึ่งความเชื่อนี้เรียกว่า ข้อปัญหาของเชิร์ช-ทัวริง (Church-Turing thesis) ศาสตร์ที่ศึกษาเกี่ยวกับขอบเขตของปัญหาที่คำนวณได้ด้วยโมเดลของเครื่องจักรแบบต่างๆนั้นคือ ทฤษฎีการคำนวณได้ ทฤษฎีการคำนวณศึกษาโมเดลการคำนวณ พร้อมๆกับขีดจำกัดของการคำนวณ เช่น ปัญหาใดที่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ได้ด้วยคอมพิวเตอร์? (ดู ปัญหาการยุติการทำงาน หรือ ปัญหาความสัมพันธ์ของโพสต์) ปัญหาใดบ้างที่สามารถแก้ไขได้ด้วยคอมพิวเตอร์ แต่ต้องการเวลามหาศาลจนทำให้การหาคำตอบนั้นเป็นไปไม่ได้ (ดู:en:Presburger arithmetic) การหาคำตอบยากกว่าการตรวจคำตอบของปัญหาหรือไม่ (ดู กลุ่มความซับซ้อน พี และ เอ็นพี) ศาสตร์ที่ศึกษาเกี่ยวกับเวลาและเนื้อที่ที่ต้องการสำหรับปัญหาต่างๆ คือ ทฤษฎีความซับซ้อนในการคำนวณ นอกจากโมเดลในการคำนวณทั่วไปแล้ว ยังมีรูปแบบในการคำนวณอื่นๆ ที่ง่ายกว่านั้น เช่น โมเดลของนิพจน์ปรกติ ที่เป็นวิธีที่ใช้กำหนดรูปแบบของสตริงในยูนิกซ์ และในบางภาษาคอมพิวเตอร์ เช่น ภาษาเพิร์ล โดยมีโมเดล เช่น เครื่องจักรสถานะจำกัดที่มีความสามารถเทียบเท่ากัน โมเดลที่มีความสามารถกว่าโมเดลนิพจน์ regular เช่น โมเดลที่อธิบายการคำนวณผ่านทางไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้าง (context-free grammar) ใช้สำหรับระบุไวยากรณ์ของภาษาโปรแกรม โดยที่มีเครื่องจักรกดลง (pushdown automata) เป็นอีกรูปแบบที่เทียบเท่ากัน ฟังก์ชันเวียนบังเกิดพื้นฐานก็เป็นโมเดลย่อยของฟังก์ชันเวียนบังเกิด โมเดลที่แตกต่างกันอาจมีความสามารถที่แตกต่างกันได้ อีกวิธีหนึ่งที่จะวัดความสามารถของโมเดลต่างๆ ก็คือการศึกษากลุ่มของภาษาทางการ (formal language) ที่โมเดลเหล่านั้นสามารถสร้างได้ ยกตัวอย่างเช่น เครื่องจักรสถานะจำกัดสามารถสร้างได้เพียงภาษาที่เทียบเท่ากับนิพจน์ regular ส่วนเครื่องจักรกดลงนั้นสามารถสร้างภาษาที่ระบุด้วยไวยากรณ์ที่ไม่ขึ้นกับสภาพรอบข้างได้ด้วย ระดับความสามารถทางภาษาทางการของโมเดลเหล่านี้เป็นที่มาของระดับชั้นของ Chomsky ตารางด้านล่างแสดงกลุ่มของปัญหา (หรือภาษา หรือไวยากรณ์) ที่พิจารณาในทฤษฎีการคำนวณได้. ัจพจน์ หรือ มูลบท เป็นคำศัพท์ที่ใช้ในวิชา คณิตศาสตร์ และวิทยาศาสตร์ หมายถึงข้อความที่ยอมรับว่าเป็นจริงโดยไม่ต้องพิสูจน์ ซึ่งตรงข้ามกับคำว่า "ทฤษฎีบท" ซึ่งจะถูกยอมรับว่าเป็นจริงได้ก็ต่อเมื่อมีการพิสูจน์ ดังนั้นสัจพจน์จึงถูกใช้เป็นจุดเริ่มต้นในการพิสูจน์ทางคณิตศาสตร์ และทฤษฎีบททุกอัน จะต้องอนุมาน (inference) มายังสัจพจน์ได้.