การคำนวณ คือ การคำนวณทางคณิตศาสตร์หรือที่ไม่ใช่คณิตศาสตร์ใดๆที่มีการกำหนดไว้อย่างชัดเจน^{[ 1 ] [ 2 ]}ตัวอย่างทั่วไปของการคำนวณ ได้แก่ การแก้ สมการทางคณิตศาสตร์และการดำเนินการอัลกอริทึมของคอมพิวเตอร์

อุปกรณ์เชิงกลหรืออิเล็กทรอนิกส์ (หรือในอดีตคือคน) ที่ทำการคำนวณเรียกว่าคอมพิวเตอร์วิทยาการคอมพิวเตอร์เป็นสาขาวิชาการที่เกี่ยวข้องกับการศึกษาเกี่ยวกับการคำนวณ

แนวคิดที่ว่าข้อความทางคณิตศาสตร์ควรจะ "กำหนดไว้อย่างดี" ได้รับการถกเถียงกันโดยนักคณิตศาสตร์มาอย่างน้อยตั้งแต่ศตวรรษ^ที่ 1600 [ ^{3 ]}แต่การตกลงกันเกี่ยวกับคำจำกัดความที่เหมาะสมนั้นกลับเป็นเรื่องยาก^{[ 4 ]}นักคณิตศาสตร์หลายคนได้เสนอคำจำกัดความที่เป็นไปได้ขึ้นมาโดยอิสระในช่วงทศวรรษที่ 1930 ^{[ 5 ]}รูปแบบที่เป็นที่รู้จักมากที่สุดได้รับการกำหนดเป็นทางการโดยนักคณิตศาสตร์Alan Turingซึ่งได้นิยามข้อความหรือการคำนวณที่กำหนดไว้อย่างดีว่าเป็นข้อความใดๆ ที่สามารถแสดงออกมาได้ในรูปของพารามิเตอร์เริ่มต้นของเครื่อง Turing [ ^{6 ]}คำจำกัดความอื่นๆ (ที่เทียบเท่ากันทางคณิตศาสตร์) ได้แก่ความสามารถในการกำหนดแลมบ์ดาของAlonzo Church ความ ^{สามารถ ในการ เรียก}ซ้ำทั่วไปของHerbrand - Gödel - Kleeneและ ความสามารถ ในการกำหนด 1ของEmil Post [ ^{5 ]}

ในปัจจุบัน ข้อความหรือการคำนวณที่เป็นทางการใดๆ ที่แสดงคุณลักษณะของการกำหนดไว้อย่างชัดเจนนี้ เรียกว่า"คำนวณได้"ในขณะที่ข้อความหรือการคำนวณนั้นเองเรียกว่า " การคำนวณ "

คำจำกัดความของ Turing ได้แบ่ง "ความชัดเจน" ให้กับกลุ่มข้อความทางคณิตศาสตร์ขนาดใหญ่มาก ซึ่งรวมถึงข้อความพีชคณิต ที่มีรูปแบบดีทั้งหมด และข้อความทั้งหมดที่เขียนในภาษาการเขียนโปรแกรมคอมพิวเตอร์สมัยใหม่^{[ 7 ]}

แม้ว่าคำจำกัดความนี้จะถูกนำไปใช้อย่างแพร่หลาย แต่ก็ยังมีแนวคิดทางคณิตศาสตร์บางอย่างที่ไม่มีลักษณะเฉพาะที่ชัดเจนภายใต้คำจำกัดความนี้ ซึ่งรวมถึงปัญหาการหยุดทำงานและเกมบีเวอร์ที่ยุ่งวุ่นวายยังคงเป็นคำถามที่เปิดกว้างว่ามีคำจำกัดความของ 'กำหนดไว้อย่างดี' ที่ทรงพลังกว่าซึ่งสามารถครอบคลุมทั้งข้อความที่คำนวณได้และ 'คำนวณไม่ได้' หรือไม่^{[หมายเหตุ 1 ] [ 8 ]}

ตัวอย่างของข้อความทางคณิตศาสตร์ที่สามารถคำนวณได้ ได้แก่:

• คำสั่งทั้งหมดมีลักษณะเฉพาะในภาษาการเขียนโปรแกรมสมัยใหม่ รวมถึงC++ , PythonและJava ^{[ 7 ]}
• การคำนวณทั้งหมดที่ดำเนินการโดยคอมพิวเตอร์ อิเล็กทรอนิกส์ เครื่อง คิดเลขหรือลูกคิด
• การคำนวณทั้งหมดดำเนินการโดยใช้เครื่องวิเคราะห์เชิงวิเคราะห์
• การคำนวณทั้งหมดดำเนินการบนเครื่องจักรทัวริง
• ข้อความและการคำนวณทางคณิตศาสตร์ส่วนใหญ่ที่ปรากฏในตำราเรียนคณิตศาสตร์

ตัวอย่างของข้อความทางคณิตศาสตร์ที่ไม่สามารถคำนวณได้ ได้แก่:

• การคำนวณหรือข้อความที่ไม่ชัดเจน ทำให้ไม่สามารถเข้ารหัสลงในเครื่องจักรทัวริงได้อย่างชัดเจน: ("พอลรักฉันเป็นสองเท่าของโจ")
• ปัญหาที่ดูเหมือนจะกำหนดไว้อย่างชัดเจน แต่สามารถพิสูจน์ได้ว่าไม่มีเครื่องจักรทัวริงใดที่สามารถแก้ปัญหาเหล่านั้นได้ (เช่นปัญหาการหยุดทำงาน )

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

แนวคิดการคำนวณทางเลือกอื่นพบได้ในงานเขียนของฮิลารี พัตนัมและคนอื่นๆปีเตอร์ ก็อดฟรี-สมิธเรียกแนวคิดนี้ว่า "แนวคิดการแมปแบบง่าย" ^{[ 9 ]}กัวลติเอโร ปิคชินินีสรุปแนวคิดนี้ว่า ระบบทางกายภาพสามารถกล่าวได้ว่าทำการคำนวณเฉพาะเมื่อมีการแมประหว่างสถานะของระบบนั้นกับการคำนวณ โดยที่ "สถานะจุลกายภาพ [ของระบบ] สะท้อนการเปลี่ยนสถานะระหว่างสถานะการคำนวณ" ^{[ 10 ]}

นักปรัชญาเช่นJerry Fodor ^{[ 11 ]}ได้เสนอแนวคิดต่างๆ เกี่ยวกับการคำนวณโดยมีข้อจำกัดว่า เนื้อหา เชิงความหมายเป็นเงื่อนไขที่จำเป็นสำหรับการคำนวณ (นั่นคือ สิ่งที่ทำให้ระบบทางกายภาพใดๆ แตกต่างจากระบบการคำนวณก็คือ ตัวดำเนินการของการคำนวณแสดงถึงบางสิ่ง) แนวคิดนี้พยายามป้องกันการสรุปเชิงตรรกะของแนวคิดการแมปของpancomputationalismซึ่งเป็นแนวคิดที่ว่าทุกสิ่งสามารถกล่าวได้ว่ากำลังคำนวณทุกสิ่ง

Gualtiero Piccininiเสนอแนวคิดเกี่ยวกับการคำนวณโดยอิงจากปรัชญาเชิงกลโดยระบุว่าระบบการคำนวณทางกายภาพเป็นกลไกประเภทหนึ่งที่ออกแบบมาเพื่อทำการคำนวณทางกายภาพ หรือการจัดการ (โดยกลไกการทำงาน) ของยานพาหนะที่ "ไม่ขึ้นกับสื่อ" ตามกฎ "การไม่ขึ้นกับสื่อ" กำหนดให้คุณสมบัตินั้นสามารถเกิดขึ้นได้โดยตัวรับรู้หลายตัวและกลไกหลายตัว และอินพุตและเอาต์พุตของกลไกนั้นก็ต้องสามารถเกิดขึ้นได้หลายแบบเช่นกัน กล่าวโดยสรุป การไม่ขึ้นกับสื่อทำให้สามารถใช้ตัวแปรทางกายภาพที่มีคุณสมบัติอื่นนอกเหนือจากแรงดันไฟฟ้า (เช่นเดียวกับในคอมพิวเตอร์ดิจิทัลทั่วไป) ซึ่งเป็นสิ่งจำเป็นในการพิจารณาการคำนวณประเภทอื่น เช่น การคำนวณที่เกิดขึ้นในสมองหรือในคอมพิวเตอร์ควอนตัมกฎในความหมายนี้จึงเป็นการแมประหว่างอินพุต เอาต์พุต และสถานะภายในของระบบการคำนวณทางกายภาพ^{[ 12 ]}

ในทฤษฎีการคำนวณมีการพัฒนาแบบจำลองทางคณิตศาสตร์ของการคำนวณที่หลากหลาย แบบจำลองทางคณิตศาสตร์ทั่วไปของการคำนวณมีดังต่อไปนี้:

• แบบจำลองสถานะต่างๆ ได้แก่เครื่องจักรทัวริง , ออโตมาตาแบบพุชดาวน์ , ออโตมาตาแบบสถานะจำกัดและPRAM
• แบบจำลองเชิงฟังก์ชันรวมถึงแคลคูลัสแลมบ์ดา
• แบบจำลองเชิงตรรกะ รวมถึงการเขียนโปรแกรมเชิงตรรกะ
• โมเดลแบบขนาน รวมถึงโมเดลแอคเตอร์และแคลคูลัสกระบวนการ

Giunti เรียกแบบจำลองที่ศึกษาโดยทฤษฎีการคำนวณว่าระบบการคำนวณและเขาโต้แย้งว่าทั้งหมดเป็นระบบพลวัตทาง คณิตศาสตร์ ที่มีเวลาไม่ต่อเนื่องและปริภูมิสถานะไม่ต่อเนื่อง^{[ 13 ] : บทที่ 1} เขายืนยันว่าระบบการคำนวณเป็นวัตถุที่ซับซ้อนซึ่งประกอบด้วยสามส่วน ส่วนแรกคือระบบพลวัตทางคณิตศาสตร์ที่มีเวลาไม่ต่อเนื่องและปริภูมิสถานะไม่ต่อเนื่อง ส่วนที่สองคือการตั้งค่าการคำนวณซึ่งประกอบด้วยส่วนทฤษฎีและส่วนจริงส่วนที่สามคือการตีความซึ่งเชื่อมโยงระบบพลวัตกับการตั้งค่า[ ^{14 ] :หน้า 179–80} ${\displaystyle DS}$${\displaystyle H=\left(F,B_{F}\right)}$${\displaystyle F}$${\displaystyle B_{F}}$${\displaystyle I_{DS,H}}$${\displaystyle DS}$${\displaystyle H}$

• การคำนวณ
• ปัญหาการคำนวณ
• ทฤษฎีความสามารถในการคำนวณ
• การคำนวณขั้นสูง
• ข้อจำกัดของการคำนวณ
• การคำนวณเชิงตัวเลข