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

ตามหลักการแล้ว วิธีการจะเรียกว่ามีประสิทธิภาพสำหรับปัญหาเฉพาะกลุ่มใดกลุ่มหนึ่งก็ต่อเมื่อเป็นไปตามเกณฑ์ต่อไปนี้:

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

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

วิธีการที่มีประสิทธิภาพในการคำนวณค่าของฟังก์ชันเรียกว่า " อัลกอริทึม "

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

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

• ความสามารถในการตัดสินใจ (ตรรกศาสตร์)
• ปัญหาการตัดสินใจ
• ผลลัพธ์ที่มีประสิทธิภาพในทฤษฎีจำนวน
• ปัญหาฟังก์ชัน
• แบบจำลองการคำนวณ
• เซตแบบเรียกซ้ำ
• ปัญหาที่ไม่สามารถตัดสินได้