ในทฤษฎีความสามารถในการคำนวณ เซตSของจำนวนธรรมชาติเรียกว่าสามารถแจงนับได้ด้วยการคำนวณ (ce)สามารถแจงนับได้แบบเวียนซ้ำ (re)สามารถตัดสินได้ บางส่วน สามารถตัดสินได้บางส่วนสามารถแสดง รายการ ได้สามารถพิสูจน์ได้หรือสามารถจดจำได้ด้วยเครื่องจักรทัวริงถ้า:

• มีอัลกอริทึมหนึ่งซึ่งเซตของตัวเลขป้อนเข้าที่ทำให้อัลกอริทึมหยุดทำงานคือSพอดี

หรือกล่าวอีกนัยหนึ่งคือ

• มี อัลกอริทึม _{หนึ่ง}ที่ใช้แจกแจงสมาชิกของSนั่นหมายความว่าผลลัพธ์ที่ได้คือรายการของสมาชิกทั้งหมดในSได้แก่ s₁ , s₂ _, s₃ _, ... ถ้าS เป็นอนันต์ อัลก อริทึมนี้จะทำงานไปเรื่อยๆ แต่สมาชิกแต่ละตัวของ S จะถูกส่งคืนหลังจากช่วงเวลาจำกัด โปรดทราบว่าสมาชิกเหล่านี้ไม่จำเป็นต้องเรียงลำดับตามความสำคัญ เช่น จากเล็กสุดไปใหญ่สุด

เงื่อนไขแรกแสดงให้เห็นว่าทำไมบางครั้งจึงใช้คำว่า "ตัดสินได้บางส่วน" (semidecidable) กล่าวคือ ถ้าตัวเลขอยู่ในเซต เราสามารถ ตัดสินได้โดยการเรียกใช้อัลกอริทึม แต่ถ้าตัวเลขไม่อยู่ในเซต อัลกอริทึมอาจทำงานไปเรื่อยๆ โดยไม่มีข้อมูลใดๆ กลับมา เซตที่ "ตัดสินได้อย่างสมบูรณ์" (completely decidable) เรียกว่าเซตที่คำนวณได้ (computable set ) เงื่อนไขที่สองแสดงให้เห็นว่าทำไม จึงใช้ คำว่า "แจงนับได้แบบคำนวณได้" (computably enumerable ) มักใช้ ตัวย่อceและreแม้กระทั่งในงานพิมพ์ แทนที่จะใช้คำเต็ม

ในทฤษฎีความซับซ้อนของการคำนวณกลุ่มความซับซ้อนที่ประกอบด้วยเซตที่แจงนับได้ด้วยการคำนวณทั้งหมดคือREในทฤษฎีการเรียกซ้ำ แลตทิซของเซต ce ภายใต้การรวมจะถูกแทนด้วย ${\displaystyle {\mathcal {E}}}$

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

ต่อไปนี้เป็นคุณสมบัติที่เทียบเท่ากันทั้งหมดของเซตSของจำนวนธรรมชาติ:

ความสามารถในการตัดสินใจแบบกึ่งเด็ดขาด:

• เซตSเป็นเซตที่สามารถแจงนับได้ด้วยการคำนวณ กล่าวคือSเป็นโดเมน (โคเรนจ์) ของฟังก์ชันที่คำนวณได้บางส่วน
• เซตSคือ(อ้างอิงถึงลำดับชั้นทางคณิตศาสตร์ ) ^{[ 1 ]}${\displaystyle \Sigma _{1}^{0}}$
• มีฟังก์ชันที่คำนวณได้บางส่วนfอยู่ ซึ่งมีคุณสมบัติดังนี้:$${\displaystyle f(x)={\begin{cases}1&{\mbox{ถ้า}}\ x\in S\\{\mbox{ไม่นิยาม/ไม่หยุดทำงาน}}\ &{\mbox{ถ้า}}\ x\notin S\end{cases}}}$$

ความสามารถในการนับ:

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

ไดโอแฟนไทน์:

• มีพหุนามpที่มีสัมประสิทธิ์เป็นจำนวนเต็มและตัวแปรอยู่ในช่วงของจำนวนธรรมชาติ โดยที่(จำนวนตัวแปรที่ถูกผูกไว้ในนิยามนี้เป็นจำนวนที่ทราบดีที่สุดในขณะนี้ อาจเป็นไปได้ว่าสามารถใช้จำนวนที่น้อยกว่านี้ในการกำหนดเซตไดโอแฟนไทน์ทั้งหมดได้)${\displaystyle x,a_{1},a_{2},a_{3},\dots ,a_{9}}$$${\displaystyle x\in S\Leftrightarrow \exists a_{1},a_{2},a_{3},\dots ,a_{9}\ (p(x,a_{1},a_{2},a_{3},\dots ,a_{9})=0).}$$
• มีพหุนามจากจำนวนเต็มไปยังจำนวนเต็ม โดยที่เซตSประกอบด้วยจำนวนที่ไม่เป็นลบที่อยู่ในช่วงของพหุนามนั้นพอดี

ความเท่าเทียมกันระหว่างความสามารถในการตัดสินใจแบบกึ่งๆ และความสามารถในการนับได้ สามารถหาได้โดยใช้เทคนิคการเชื่อมต่อแบบหางนกพิราบ

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

• เซตที่คำนวณได้ทุก เซต สามารถแจงนับได้ด้วยการคำนวณ แต่ไม่ใช่ว่าทุกเซตที่สามารถแจงนับได้ด้วยการคำนวณจะคำนวณได้ทุกเซต สำหรับเซตที่คำนวณได้ อัลกอริทึมจะต้องระบุด้วยว่าอินพุตนั้นไม่ อยู่ ในเซตหรือไม่ ซึ่งไม่จำเป็นสำหรับเซตที่สามารถแจงนับได้ด้วยการคำนวณ
• ภาษาที่สามารถแจงนับได้แบบเรียกซ้ำคือเซตย่อยที่สามารถแจงนับได้ด้วยการคำนวณของ ภาษา เชิงรูปธรรม
• เซตของประโยคที่พิสูจน์ได้ทั้งหมดในระบบสัจพจน์ที่นำเสนออย่างมีประสิทธิภาพ คือเซตที่สามารถแจงนับได้ด้วยการคำนวณ
• ทฤษฎีบทของมาติยาเซวิชกล่าวว่า เซตที่สามารถนับได้ด้วยการคำนวณทุกเซตเป็นเซตไดโอแฟนไทน์ (ส่วนกลับนั้นเป็นจริงอย่างเห็นได้ชัด)
• เซตแบบง่ายนั้นสามารถแจงนับได้โดยการคำนวณ แต่ไม่สามารถคำนวณได้
• เซตสร้างสรรค์นั้นสามารถแจงนับได้ด้วยการคำนวณ แต่ไม่สามารถคำนวณได้โดยตรง
• เซตที่มีประสิทธิภาพใดๆ ก็ไม่สามารถแจงนับได้ด้วยการคำนวณ
• เมื่อกำหนดหมายเลข Gödel ให้ กับฟังก์ชันที่คำนวณได้ เซต(โดยที่คือฟังก์ชันการจับคู่ของ Cantorและบ่งชี้ว่าถูกกำหนดไว้แล้ว) สามารถแจงนับได้ด้วยการคำนวณ (ดูภาพสำหรับx ที่กำหนดไว้ ) เซตนี้เข้ารหัสปัญหาการหยุดทำงานเนื่องจากอธิบายพารามิเตอร์อินพุตที่ทำให้เครื่อง Turing แต่ละเครื่อง หยุดทำงาน${\displaystyle \phi }$${\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}}$${\displaystyle \langle i,x\rangle }$${\displaystyle \phi _{i}(x)\downarrow }$${\displaystyle \phi _{i}(x)}$
• เมื่อกำหนดหมายเลข Gödel ให้กับฟังก์ชันที่คำนวณได้ เซตนั้นจะสามารถแจงนับได้ด้วยการคำนวณ เซตนี้เข้ารหัสปัญหาของการตัดสินใจค่าของฟังก์ชัน${\displaystyle \phi }$${\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}}$
• กำหนดให้ fเป็นฟังก์ชันบางส่วนจากจำนวนธรรมชาติไปยังจำนวนธรรมชาติfจะเป็นฟังก์ชันที่คำนวณได้บางส่วนก็ต่อเมื่อกราฟของfซึ่งก็คือเซตของคู่ทั้งหมดที่f ( x ) ถูกกำหนดไว้ เป็นเซตที่แจงนับได้ด้วยการคำนวณ${\displaystyle \langle x,f(x)\rangle }$

ถ้าAและBเป็นเซตที่นับได้ด้วยการคำนวณแล้วA ∩ B , A ∪ BและA × B (โดยที่คู่ลำดับของจำนวนธรรมชาติถูกแปลงเป็นจำนวนธรรมชาติเดียวด้วยฟังก์ชันการจับคู่ของแคนเตอร์ ) ก็เป็นเซตที่นับได้ด้วยการคำนวณเช่นกันภาพผกผันของเซตที่นับได้ด้วยการคำนวณภายใต้ฟังก์ชันที่คำนวณได้บางส่วนก็เป็นเซตที่นับได้ด้วยการคำนวณเช่นกัน

เซตจะเรียกว่า เซตที่สามารถแจงนับได้ด้วย การคำนวณ (co-computably-enumerable ) หรือco-ceถ้าเซตส่วนเติมเต็ม ของมันสามารถแจงนับได้ด้วยการคำนวณ เช่นกัน หรือกล่าวอีกนัยหนึ่ง เซตจะเป็น co-re ก็ต่อเมื่อมันอยู่ในระดับของลำดับชั้นทางคณิตศาสตร์ ชั้นความซับซ้อนของเซตที่สามารถแจงนับได้ด้วยการคำนวณจะใช้สัญลักษณ์ co-RE ${\displaystyle T}$${\displaystyle \mathbb {N} \setminus T}$${\displaystyle \Pi _{1}^{0}}$

เซตAจะเรียกว่าเซตที่คำนวณได้ก็ต่อเมื่อทั้งAและส่วนเติมเต็มของAเป็นเซตที่นับได้โดยการคำนวณ

บางคู่ของเซตที่สามารถแจงนับได้ด้วยคอมพิวเตอร์นั้นสามารถแยกออกจากกันได้อย่างมีประสิทธิภาพในขณะที่บางคู่ไม่สามารถ แยกออกจากกันได้

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

ช่วง ของ แลตทิซนี้เป็นพีชคณิตบูลีนหรือทฤษฎีอันดับแรกของพวกมันก็ไม่สามารถตัดสินได้เช่นกัน^{[ 2 ]}โครงสร้างที่เป็นไปได้ของช่วงของแลตทิซนี้ยังไม่เป็นที่เข้าใจดีนัก^{[ 2 ]}

ส่วนเติมเต็มของฟังก์ชันที่แจงนับเซตที่แจงนับได้แบบเรียกซ้ำสูงสุดใดๆ จะครอบงำฟังก์ชันเรียกซ้ำทั่วไป ทุก ฟังก์ชัน^{[ 5 ]}มีเซตที่แจงนับได้แบบเรียกซ้ำสูงสุดที่มีดีกรีทัวริงไม่เกิน0′ [ ^{5 ] สำหรับ}เซตที่แจงนับได้แบบเรียกซ้ำสูงสุดสองเซตใดๆAและBจะมีออโตมอร์ฟิซึมลำดับของแลตทิซของเซตที่แจงนับได้แบบเรียกซ้ำที่แมปAไปยังBอย่างไรก็ตาม ออโตมอร์ฟิซึมนี้อาจไม่สามารถคำนวณได้เสมอไป^{[ 6 ]}

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

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

• RE (ความซับซ้อน)
• ภาษาที่สามารถแจงนับได้แบบเรียกซ้ำ
• ลำดับชั้นทางคณิตศาสตร์