ในทฤษฎีความสามารถในการคำนวณและทฤษฎีความซับซ้อนของการคำนวณRE ( recursively enumerable ) คือคลาสของปัญหาการตัดสินใจที่สามารถตรวจสอบคำตอบ 'ใช่' ได้โดยเครื่องจักรทัวริงภายในระยะเวลาที่จำกัด^{[ 1 ]}อย่างไม่เป็นทางการ หมายความว่าหากคำตอบของตัวอย่างปัญหาคือ 'ใช่' ก็จะมีขั้นตอนบางอย่างที่ใช้เวลาจำกัดในการตรวจสอบ และขั้นตอนดังกล่าวจะไม่รายงาน 'ใช่' อย่างผิดพลาดเมื่อคำตอบที่แท้จริงคือ 'ไม่ใช่' อย่างไรก็ตาม เมื่อคำตอบที่แท้จริงคือ 'ไม่ใช่' ขั้นตอนไม่จำเป็นต้องหยุดทำงาน อาจเข้าสู่ " วงวนอนันต์ " สำหรับบางกรณีที่เป็น 'ไม่ใช่' ขั้นตอนดังกล่าวบางครั้งเรียกว่ากึ่งอัลกอริธึมเพื่อแยกความแตกต่างจากอัลกอริธึมซึ่งกำหนดเป็นวิธีแก้ปัญหาที่สมบูรณ์สำหรับปัญหาการตัดสินใจ^{[ 2 ]}

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

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

เพื่อแสดงให้เห็นว่าสิ่งนี้เทียบเท่ากัน โปรดสังเกตว่าหากมีเครื่องจักร${\displaystyle E}$ซึ่งจะแสดงรายการอินพุตที่ยอมรับทั้งหมด จากนั้นเครื่องอีกเครื่องที่รับสตริงเข้ามาสามารถทำงานได้${\displaystyle E}$และยอมรับหากสตริงนั้นอยู่ในรายการ ในทางกลับกัน หากเครื่องจักร${\displaystyle M}$ยอมรับเมื่ออินพุตอยู่ในภาษาหนึ่ง จากนั้นเครื่องอื่นสามารถแจงนับสตริงทั้งหมดในภาษานั้นได้โดยการสลับการจำลอง${\displaystyle M}$ในทุกๆ อินพุตและเอาต์พุตสตริงที่ยอมรับได้ (มีลำดับการดำเนินการที่จะไปถึงทุกขั้นตอนการดำเนินการในที่สุด เนื่องจากมีคู่ลำดับของอินพุตและขั้นตอนจำนวนนับได้)

เซตของภาษาเรียกซ้ำ ( R ) เป็นเซตย่อยของทั้งREและco-RE [ ^{3 ] ใน}ความเป็นจริง มันคือจุดตัดของคลาสทั้งสองนั้น เพราะเราสามารถตัดสินปัญหาใดๆ ที่มีตัวรับรู้และตัวรับรู้ร่วมได้โดยการสลับกันไปเรื่อยๆ จนกว่าจะได้ผลลัพธ์ ดังนั้น:

${\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}$.

ในทางกลับกัน เซตของภาษาที่ไม่ใช่ทั้งREและco-REเรียกว่าNRNCเซตนี้เป็นภาษาที่ไม่สามารถพิสูจน์ได้ว่าอยู่ในกลุ่ม RE หรือ co-RE ภายในระยะเวลาที่จำกัด และประกอบด้วยภาษาอื่นๆ ทั้งหมดที่ไม่ได้อยู่ในกลุ่มREหรือco-REกล่าวคือ:

${\displaystyle {\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})}$.

ปัญหาเหล่านี้ไม่เพียงแต่ไม่สามารถหาคำตอบได้เท่านั้น แต่ทั้งปัญหาเหล่านี้และส่วนเติมเต็มของปัญหาเหล่านี้ก็ไม่สามารถแจงนับได้แบบเวียนซ้ำอีกด้วย

ในเดือนมกราคม พ.ศ. 2563 เอกสารฉบับร่างได้ประกาศการพิสูจน์ว่าREเทียบเท่ากับคลาสMIP* (คลาสที่ผู้ตรวจสอบแบบคลาสสิกโต้ตอบกับผู้พิสูจน์ควอนตัมที่ทรงพลังหลายคนซึ่งแบ่งปันการพัวพัน ) ^{[ 4 ]}การพิสูจน์ที่แก้ไขแล้ว แต่ยังไม่ได้รับการตรวจสอบอย่างสมบูรณ์ ได้รับการตีพิมพ์ในCommunications of the ACMในเดือนพฤศจิกายน พ.ศ. 2564 การพิสูจน์นี้บ่งชี้ว่าปัญหาการฝังตัวของ Connesและปัญหาของ Tsirelsonเป็นเท็จ^{[ 5 ]}

RE-completeคือเซตของปัญหาการตัดสินใจที่สมบูรณ์สำหรับREในแง่หนึ่ง ปัญหาเหล่านี้เป็นปัญหาที่นับได้แบบเรียกซ้ำที่ "ยากที่สุด" โดยทั่วไปแล้ว จะไม่มีข้อจำกัดใด ๆ เกี่ยวกับการลดรูปที่ใช้ ยกเว้นว่าการลดรูปเหล่านั้นจะต้องเป็นการลดรูปหลายต่อหนึ่ง

ตัวอย่างของปัญหาที่ต้องแก้ไขให้สมบูรณ์ (RE-complete):

1. ปัญหาการหยุดทำงาน : โปรแกรมที่ได้รับข้อมูลป้อนเข้าจำนวนจำกัด จะทำงานจนจบ หรือจะทำงานไปเรื่อยๆ อย่างไม่มีที่สิ้นสุด
2. ตามทฤษฎีบทของไรซ์การตัดสินว่า a เป็นสมาชิกในเซตย่อยที่ไม่ใช่เซตว่างของเซตของฟังก์ชันเวียนเกิด บางส่วนนั้นยาก ใน ระดับ REและจะเป็นเซตที่สมบูรณ์เมื่อใดก็ตามที่เซตนั้นสามารถแจงนับได้แบบเวียนเกิด
3. John Myhill ( 1955 ) ^{[ 6 ]} พิสูจน์แล้วว่า ชุดสร้างสรรค์ทั้งหมดเป็นRE -complete 
4. โจทย์ปัญหาที่เป็นเอกภาพสำหรับกลุ่มหรือกลุ่มย่อย (อันที่จริงโจทย์ปัญหาสำหรับกลุ่มย่อยบางกลุ่มก็ สมบูรณ์แบบ RE ด้วย )
5. การตัดสินว่าไวยากรณ์ใดเป็นสมาชิก ของไวยากรณ์ที่เป็นทางการทั่วไปที่ไม่จำกัด (อีกครั้ง ไวยากรณ์เฉพาะบางประเภทมี ปัญหาเรื่องการเป็นสมาชิกที่สมบูรณ์แบบตามหลักการ RE )
6. ปัญหาความถูกต้องของตรรกะลำดับที่หนึ่ง
7. ปัญหาเกี่ยวกับการจับคู่ข้อความ : กำหนดให้รายการคู่ของสตริง จงตรวจสอบว่ามีการเลือกคู่สตริงเหล่านี้ (โดยอนุญาตให้มีคู่ซ้ำได้) ใดบ้างที่เมื่อนำสตริงตัวแรกของคู่สตริงมาต่อกันแล้วจะได้ผลลัพธ์เท่ากับเมื่อนำสตริงตัวที่สองมาต่อกันแล้ว
8. Determining if a Diophantine equation has any integer solutions.

co-RE-complete is the set of decision problems that are complete for co-RE. In a sense, these are the complements of the hardest recursively enumerable problems.

Examples of co-RE-complete problems:

1. The domino problem for Wang tiles.
2. The satisfiability problem for first-order logic.

• Knuth–Bendix completion algorithm
• List of undecidable problems
• Polymorphic recursion
• Risch algorithm
• Semidecidability