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

คำถามพื้นฐานที่ทฤษฎีความสามารถในการคำนวณกล่าวถึง ได้แก่:

• ฟังก์ชันบนจำนวนธรรมชาติที่สามารถคำนวณได้หมายความว่าอย่างไร ?
• เราจะจัดประเภทฟังก์ชันที่ไม่สามารถคำนวณได้เป็นลำดับชั้นตามระดับความไม่สามารถคำนวณได้อย่างไร?

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

ทฤษฎีความสามารถในการคำนวณมีต้นกำเนิดในช่วงทศวรรษ 1930 โดยผลงานของKurt Gödel , Alonzo Church , Rózsa Péter , Alan Turing , Stephen KleeneและEmil Post ^{[ 4 ] [ b ]}

ผลลัพธ์พื้นฐานที่นักวิจัยได้รับนั้นได้พิสูจน์ให้เห็นว่าความสามารถในการคำนวณของทัวริงเป็นรูปแบบที่ถูกต้องของแนวคิดที่ไม่เป็นทางการเกี่ยวกับการคำนวณที่มีประสิทธิภาพ ในปี พ.ศ. 2495 ผลลัพธ์เหล่านี้ทำให้ Kleene บัญญัติชื่อสองชื่อคือ "วิทยานิพนธ์ของ Church" ^{[ 5 ] : 300} และ "วิทยานิพนธ์ของทัวริง" ^{[ 5 ] : 376} ปัจจุบันสิ่งเหล่านี้มักถูกพิจารณาว่าเป็นสมมติฐานเดียว คือวิทยานิพนธ์ Church–Turingซึ่งระบุว่าฟังก์ชันใดๆ ที่สามารถคำนวณได้ด้วยอัลกอริทึมถือเป็นฟังก์ชันที่คำนวณได้แม้ว่าในตอนแรก Gödel จะสงสัย แต่ในปี พ.ศ. 2489 เขาได้โต้แย้งสนับสนุนวิทยานิพนธ์นี้: ^{[ 6 ] : 84}

" ทาร์สกีได้เน้นย้ำในการบรรยายของเขา (และฉันคิดว่าถูกต้อง) ถึงความสำคัญอย่างยิ่งของแนวคิดเรื่องการเรียกซ้ำทั่วไป (หรือความสามารถในการคำนวณของทัวริง) ดูเหมือนว่าความสำคัญนี้ส่วนใหญ่เกิดจากข้อเท็จจริงที่ว่าด้วยแนวคิดนี้ เราประสบความสำเร็จเป็นครั้งแรกในการให้แนวคิดเชิงสัมบูรณ์แก่แนวคิดทางญาณวิทยาที่น่าสนใจ กล่าวคือ แนวคิดที่ไม่ขึ้นอยู่กับรูปแบบที่เลือก" ^{[ 6 ] : 84 [ 7 ]}

ด้วยนิยามของการคำนวณที่มีประสิทธิภาพ จึงมีการพิสูจน์ครั้งแรกว่ามีปัญหาในคณิตศาสตร์ที่ไม่สามารถตัดสินได้อย่างมีประสิทธิภาพในปี 1936 Church ^{[ 8 ] [ 9 ]}และ Turing ^{[ 10 ]} (ได้รับแรงบันดาลใจจากเทคนิคที่ Gödel ใช้ในการพิสูจน์ทฤษฎีบทความไม่สมบูรณ์ ของเขา ) ได้แสดงให้เห็นโดยอิสระว่าปัญหาEntscheidungsproblemไม่สามารถตัดสินได้อย่างมีประสิทธิภาพ ผลลัพธ์นี้แสดงให้เห็นว่าไม่มีขั้นตอนวิธีใดที่สามารถตัดสินได้อย่างถูกต้องว่าข้อเสนอทางคณิตศาสตร์ที่กำหนดขึ้นนั้นเป็นจริงหรือเท็จ

ปัญหาทางคณิตศาสตร์ หลายข้อ ได้รับการพิสูจน์แล้วว่าไม่สามารถ ตัดสินได้ หลังจากมีการสร้างตัวอย่างเบื้องต้นเหล่านี้^{[ c ]}ในปี 1947 Markovและ Post ได้ตีพิมพ์บทความอิสระที่แสดงให้เห็นว่าปัญหาคำสำหรับเซมิกรุปไม่สามารถตัดสินได้อย่างมีประสิทธิภาพPyotr NovikovและWilliam Boone ได้ขยายผลลัพธ์นี้ โดยอิสระในช่วงทศวรรษ 1950 ว่าปัญหาคำสำหรับกลุ่มไม่สามารถแก้ไขได้อย่างมีประสิทธิภาพ: ไม่มีขั้นตอนที่มีประสิทธิภาพใด ๆ ที่จะตัดสินได้ว่าองค์ประกอบที่แสดงโดยคำนั้นเป็นองค์ประกอบเอกลักษณ์ ของกลุ่มหรือไม่ เมื่อกำหนดคำใน กลุ่ม ที่นำเสนออย่างจำกัด ในปี 1970 Yuri Matiyasevichได้พิสูจน์ (โดยใช้ผลลัพธ์ของJulia Robinson ) ทฤษฎีบทของ Matiyasevichซึ่งหมายความว่าปัญหาที่สิบของ Hilbertไม่มีวิธีแก้ปัญหาที่มีประสิทธิภาพ ปัญหานี้ถามว่ามีขั้นตอนที่มีประสิทธิภาพในการตัดสินหรือไม่ว่าสมการไดโอแฟนไทน์เหนือจำนวนเต็มมีคำตอบในจำนวนเต็มหรือไม่

รูปแบบหลักของการคำนวณที่ศึกษาในสาขานี้ได้รับการแนะนำโดย Turing ในปี 1936 ^{[ 10 ]}เซตของจำนวนธรรมชาติเรียกว่าเซตที่คำนวณได้ (เรียกอีกอย่างว่าเซตที่ตัดสินได้ เซต แบบเรียกซ้ำหรือ เซต ที่คำนวณได้ด้วย Turing ) หากมีเครื่อง Turingที่เมื่อป้อนจำนวนnจะหยุดทำงานโดยมีเอาต์พุต 1 หากnอยู่ในเซต และจะหยุดทำงานโดยมีเอาต์พุต 0 หากnไม่อยู่ในเซต ฟังก์ชันfจากจำนวนธรรมชาติไปยังจำนวนธรรมชาติเป็นฟังก์ชันที่คำนวณได้ (Turing) หรือฟังก์ชันแบบเรียกซ้ำหากมีเครื่อง Turing ที่เมื่อป้อนnจะหยุดทำงานและส่งคืนเอาต์พุตf ( n ) การใช้เครื่อง Turing ในที่นี้ไม่จำเป็น มีแบบจำลองการคำนวณ อื่นๆ อีกมากมาย ที่มีกำลังการคำนวณเท่ากับเครื่อง Turing ตัวอย่างเช่นฟังก์ชัน μ-recursiveที่ได้จากการเรียกซ้ำแบบดั้งเดิมและ ตัวดำเนิน การ μ

คำศัพท์สำหรับฟังก์ชันและเซตที่คำนวณได้ยังไม่ได้รับการกำหนดมาตรฐานอย่างสมบูรณ์ คำจำกัดความในแง่ของฟังก์ชัน μ-recursive รวมถึงคำจำกัดความที่แตกต่างกันของ ฟังก์ชัน recursiveโดย Gödel นำไปสู่ชื่อดั้งเดิมว่าrecursiveสำหรับเซตและฟังก์ชันที่คำนวณได้โดยเครื่องจักร Turing คำว่าdecidableมาจากคำภาษาเยอรมันEntscheidungsproblemซึ่งใช้ในเอกสารต้นฉบับของ Turing และคนอื่นๆ ในการใช้งานปัจจุบัน คำว่า "ฟังก์ชันที่คำนวณได้" มีคำจำกัดความที่หลากหลาย: ตามที่Nigel J. Cutland [ ^{11 ] กล่าว}ไว้ มันคือฟังก์ชัน recursive บางส่วน (ซึ่งอาจไม่มีนิยามสำหรับอินพุตบางอย่าง) ในขณะที่ตามที่Robert I. Soare ^{[ 12 ]} กล่าวไว้ มันคือฟังก์ชัน recursive ทั้งหมด บทความนี้ยึดตามแบบแผนข้อที่สองนี้ ในปี 1996 Soare ^{[ 13 ]}ได้ให้ความเห็นเพิ่มเติมเกี่ยวกับคำศัพท์

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

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

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

ทฤษฎีความสามารถในการคำนวณในตรรกศาสตร์ทางคณิตศาสตร์โดยทั่วไปมุ่งเน้นไปที่ความสามารถ ในการคำนวณ เชิงสัมพัทธ์ ซึ่งเป็นการวางนัยทั่วไปของความสามารถในการคำนวณของทัวริงที่กำหนดโดยใช้เครื่องจักรทัวริงแบบออราเคิลซึ่งทัวริงได้แนะนำในปี 1939 ^{[ 14 ]}เครื่องจักรทัวริงแบบออราเคิลเป็นอุปกรณ์สมมติที่นอกเหนือจากการดำเนินการของเครื่องจักรทัวริงทั่วไปแล้ว ยังสามารถถามคำถามกับออราเคิลซึ่งเป็นเซตของจำนวนธรรมชาติที่เฉพาะเจาะจง เครื่องจักรออราเคิลสามารถถามคำถามได้เฉพาะในรูปแบบ " n อยู่ ในเซตออราเคิลหรือไม่" แต่ละคำถามจะได้รับคำตอบที่ถูกต้องทันที แม้ว่าเซตออราเคิลจะไม่สามารถคำนวณได้ก็ตาม ดังนั้นเครื่องจักรออราเคิลที่มีออราเคิลที่ไม่สามารถคำนวณได้จะสามารถคำนวณเซตที่เครื่องจักรทัวริงที่ไม่มีออราเคิลไม่สามารถทำได้

โดยทั่วไปแล้ว เซตของจำนวนธรรมชาติAสามารถลดรูปได้ด้วยเครื่องจักรทัวริง (Turing reducible)ไปเป็นเซตBหากมีเครื่องจักรทำนาย (oracle machine) ที่บอกได้อย่างถูกต้องว่ามีจำนวนใดอยู่ในA หรือไม่ เมื่อใช้งานโดยใช้Bเป็นเซตทำนาย (ในกรณีนี้ เซตAยังกล่าวได้ว่าสามารถคำนวณได้ ( relatively computable ) จากBและ เป็นแบบเวียนเกิด ( recursive) ในB ) หากเซตAสามารถลดรูปได้ด้วยเครื่องจักรทัวริงไปเป็นเซตBและBสามารถลดรูปได้ด้วยเครื่องจักรทัวริงไปเป็นA แล้ว เซตทั้งสองจะกล่าวได้ว่ามี ระดับทัวริง (Turing degree) เดียวกัน(หรือเรียกว่าระดับความไม่สามารถแก้ได้ (degree of unsolvability ) ระดับทัวริงของเซตจะให้ค่าที่แม่นยำว่าเซตนั้นไม่สามารถคำนวณได้มากน้อยเพียงใด

ตัวอย่างตามธรรมชาติของเซตที่ไม่สามารถคำนวณได้ ซึ่งรวมถึงเซตต่างๆ มากมายที่เข้ารหัสรูปแบบต่างๆ ของปัญหาการหยุดทำงานมีคุณสมบัติร่วมกันสองประการดังนี้:

1. พวกมันสามารถแจงนับได้ด้วยการคำนวณและ
2. แต่ละเซตสามารถแปลงเป็นเซตอื่นใดก็ได้ผ่านการลดรูปหลายต่อหนึ่งนั่นคือ เมื่อกำหนดเซตAและBแล้ว จะมีฟังก์ชันที่คำนวณได้ทั้งหมดfที่ทำให้A = { x  : f ( x ) ∈ B } เซตเหล่านี้เรียกว่าสมมูลกันแบบหลายต่อหนึ่ง (หรือสมมูลแบบ m )

ความสามารถในการลดรูปหลายหนึ่งนั้น "แข็งแกร่งกว่า" ความสามารถในการลดรูปทัวริง: ถ้าเซตAสามารถลดรูปหลายหนึ่งไปยังเซตBได้ เซต Aก็สามารถลดรูปทัวริงไปยังBได้ แต่ในทางกลับกันนั้นไม่เป็นจริงเสมอไป แม้ว่าตัวอย่างตามธรรมชาติของเซตที่ไม่สามารถคำนวณได้ทั้งหมดจะเทียบเท่ากันแบบหลายหนึ่ง แต่ก็เป็นไปได้ที่จะสร้างเซตที่นับได้แบบคำนวณได้AและBโดยที่AสามารถลดรูปทัวริงไปยังB ได้ แต่ไม่สามารถลดรูปหลายหนึ่งไปยังBได้ สามารถแสดงได้ว่าทุกเซตที่นับได้แบบคำนวณได้สามารถลดรูปหลายหนึ่งไปยังปัญหาการหยุดได้ ดังนั้นปัญหาการหยุดจึงเป็นเซตที่นับได้แบบคำนวณได้ที่ซับซ้อนที่สุดเมื่อพิจารณาจากความสามารถในการลดรูปหลายหนึ่งและเมื่อพิจารณาจากความสามารถในการลดรูปทัวริง ในปี พ.ศ. 2487 Post ^{[ 15 ]}ถามว่าทุกเซตที่นับได้แบบคำนวณได้นั้นสามารถคำนวณได้หรือเทียบเท่าทัวริงกับปัญหาการหยุดหรือไม่ นั่นคือไม่มีเซตที่นับได้แบบคำนวณได้ที่มีระดับทัวริงอยู่ระหว่างสองสิ่งนั้นหรือไม่

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

มีเซตจำนวนนับไม่ถ้วนที่ไม่สามารถนับได้ด้วยการคำนวณ และการตรวจสอบดีกรีทัวริงของเซตทั้งหมดมีความสำคัญในทฤษฎีความสามารถในการคำนวณพอๆ กับการตรวจสอบดีกรีทัวริงที่สามารถนับได้ด้วยการคำนวณ ดีกรีที่มีคุณสมบัติพิเศษหลายอย่างถูกสร้างขึ้น ได้แก่ดีกรีที่ปราศจากภูมิคุ้มกันขั้นสูงซึ่งทุกฟังก์ชันที่คำนวณได้สัมพันธ์กับดีกรีนั้นจะถูกครอบงำโดยฟังก์ชันที่คำนวณได้ (ที่ไม่สัมพันธ์กัน) ดีกรีสูงๆที่สามารถคำนวณฟังก์ชันfที่ครอบงำทุกฟังก์ชันg ที่คำนวณได้ ในแง่ที่ว่ามีค่าคงที่cที่ขึ้นอยู่กับgเช่นg(x) < f(x)สำหรับทุกx > cดีกรีสุ่มที่มีเซตสุ่มเชิงอัลกอริทึม ดีกรี ทั่วไป 1ของเซตทั่วไป 1 และดีกรีที่ต่ำกว่าปัญหาการหยุดของเซต ที่คำนวณได้ด้วยขีดจำกัด

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

งานวิจัยล่าสุดจำนวนมากเกี่ยวกับระดับทัวริงมุ่งเน้นไปที่โครงสร้างโดยรวมของเซตของระดับทัวริงและเซตของระดับทัวริงที่มีเซตที่นับได้ด้วยการคำนวณ ทฤษฎีบทเชิงลึกของ Shore และ Slaman ^{[ 16 ]}ระบุว่าฟังก์ชันที่แมปดีกรีxไปยังดีกรีของการกระโดดทัวริงนั้นสามารถกำหนดได้ในลำดับบางส่วนของระดับทัวริง การสำรวจโดย Ambos-Spies และ Fejer ^{[ 17 ]}ให้ภาพรวมของงานวิจัยนี้และความก้าวหน้าทางประวัติศาสตร์

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

ความสามารถในการลดทอนที่แข็งแกร่ง ได้แก่:

ความสามารถในการลดรูปหนึ่งต่อหนึ่ง : Aสามารถลดรูปหนึ่งต่อหนึ่ง (หรือลดรูป 1 ได้ ) ไปยังBได้ก็ต่อเมื่อมีฟังก์ชันฉีด แบบสมบูรณ์ที่คำนวณได้ fซึ่งแต่ละnอยู่ในAก็ต่อเมื่อf ( n ) อยู่ในB

ความสามารถในการลดรูปหลายต่อหนึ่ง : นี่คือความสามารถในการลดรูปหนึ่งต่อหนึ่งโดยไม่มีข้อจำกัดว่าf ต้อง เป็น ฟังก์ชันหนึ่งต่อหนึ่ง Aสามารถลดรูปหลายต่อหนึ่ง (หรือm-reducible ) ไปยังB ได้ถ้ามีฟังก์ชันคำนวณได้ทั้งหมดfที่ทำให้แต่ละnอยู่ในAก็ต่อเมื่อf ( n ) อยู่ในB

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

การลดรูปเพิ่มเติม (เชิงบวก แยกกัน เชื่อมต่อกัน เชิงเส้น และเวอร์ชันที่อ่อนและจำกัด) ได้รับการกล่าวถึงในบทความเรื่องการลดรูป (ทฤษฎีความสามารถในการคำนวณ )

งานวิจัยหลักเกี่ยวกับการลดทอนอย่างเข้มแข็ง (strong reduciability) คือการเปรียบเทียบทฤษฎีต่างๆ ทั้งสำหรับกลุ่มของเซตที่นับได้ด้วยการคำนวณทั้งหมด และสำหรับกลุ่มของเซตย่อยทั้งหมดของจำนวนธรรมชาติ นอกจากนี้ยังมีการศึกษาความสัมพันธ์ระหว่างการลดทอนต่างๆ ด้วย ตัวอย่างเช่น เป็นที่ทราบกันว่าดีกรีของทัวริงทุกตัวเป็นดีกรีของตารางความจริง หรือเป็นผลรวมของดีกรีของตารางความจริงจำนวนอนันต์

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

ไรซ์แสดงให้เห็นว่าสำหรับทุกคลาสC ที่ไม่ใช่คลาสพื้นฐาน (ซึ่งประกอบด้วยเซต ce บางส่วนแต่ไม่ใช่ทั้งหมด) เซตดัชนีE = { e : เซต ce ตัวที่e W _eอยู่ในC } มีคุณสมบัติที่ว่าปัญหาการหยุดหรือส่วนเติมเต็มของปัญหานั้นสามารถลดรูปได้แบบหลายต่อหนึ่งไปยังEกล่าวคือ สามารถแมปโดยใช้การลดรูปหลายต่อหนึ่งไปยังE ได้ (ดูทฤษฎีบทของไรซ์สำหรับรายละเอียดเพิ่มเติม) แต่เซตดัชนีเหล่านี้จำนวนมากมีความซับซ้อนมากกว่าปัญหาการหยุด เซตประเภทนี้สามารถจำแนกประเภทได้โดยใช้ลำดับชั้นทางเลขคณิตตัวอย่างเช่น เซตดัชนี FIN ของคลาสของเซตจำกัดทั้งหมดอยู่ในระดับ Σ ₂เซตดัชนี REC ของคลาสของเซตเวียนเกิดทั้งหมดอยู่ในระดับ Σ ₃เซตดัชนี COFIN ของเซตโคไฟไนต์ทั้งหมดก็อยู่ในระดับ Σ ₃ เช่นกัน และเซตดัชนี COMP ของคลาสของเซตที่สมบูรณ์แบบทัวริงทั้งหมด อยู่ในระดับ Σ ₄ระดับลำดับชั้นเหล่านี้ถูกกำหนดขึ้นโดยอุปนัย โดย Σ _{n +1}ประกอบด้วยเซตทั้งหมดที่สามารถแจงนับได้โดยการคำนวณเมื่อเทียบกับ Σ _nและ Σ ₁ประกอบด้วยเซตที่สามารถแจงนับได้โดยการคำนวณ เซตดัชนีที่ให้ไว้ในที่นี้สมบูรณ์แม้กระทั่งสำหรับระดับของมัน กล่าวคือ เซตทั้งหมดในระดับเหล่านี้สามารถลดรูปหลายต่อหนึ่งไปยังเซตดัชนีที่กำหนดให้

โปรแกรมคณิตศาสตร์ย้อนกลับถามว่าสัจพจน์การมีอยู่ของเซตใดบ้างที่จำเป็นต่อการพิสูจน์ทฤษฎีบทเฉพาะของคณิตศาสตร์ในระบบย่อยของเลขคณิตอันดับสองการศึกษานี้ริเริ่มโดยHarvey Friedmanและได้รับการศึกษาอย่างละเอียดโดยStephen Simpsonและคนอื่นๆ ในปี 1999 Simpson ^{[ 18 ]}ได้ให้การอภิปรายอย่างละเอียดเกี่ยวกับโปรแกรม สัจพจน์การมีอยู่ของเซตที่กล่าวถึงนั้นสอดคล้องอย่างไม่เป็นทางการกับสัจพจน์ที่กล่าวว่าเซตกำลังของจำนวนธรรมชาติปิดภายใต้แนวคิดการลดรูปต่างๆ สัจพจน์ที่อ่อนที่สุดที่ศึกษาในคณิตศาสตร์ย้อนกลับคือความเข้าใจแบบเรียกซ้ำซึ่งระบุว่าเซตกำลังของจำนวนธรรมชาติปิดภายใต้การลดรูปของ Turing

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

ปัญหาของโพสต์ได้รับการแก้ไขด้วยวิธีการที่เรียกว่า วิธีการจัดลำดับความสำคัญ (priority method ) การพิสูจน์โดยใช้วิธีนี้เรียกว่าการให้เหตุผลเชิงลำดับความสำคัญ (priority argument ) วิธีนี้ใช้เป็นหลักในการสร้างเซตที่สามารถแจงนับได้ด้วยคอมพิวเตอร์ (computably enumerable sets) ที่มีคุณสมบัติเฉพาะ ในการใช้วิธีนี้ คุณสมบัติที่ต้องการของเซตที่จะสร้างจะถูกแบ่งออกเป็นรายการเป้าหมายที่ไม่มีที่สิ้นสุด ซึ่งเรียกว่าข้อกำหนด (requirements ) เพื่อให้การปฏิบัติตามข้อกำหนดทั้งหมดจะทำให้เซตที่สร้างขึ้นมีคุณสมบัติที่ต้องการ แต่ละข้อกำหนดจะถูกกำหนดให้กับจำนวนธรรมชาติที่แสดงถึงลำดับความสำคัญของข้อกำหนด ดังนั้น 0 จะถูกกำหนดให้กับลำดับความสำคัญที่สำคัญที่สุด 1 ให้กับลำดับความสำคัญที่สำคัญรองลงมา และอื่นๆ จากนั้นเซตจะถูกสร้างขึ้นเป็นขั้นตอน โดยแต่ละขั้นตอนจะพยายามปฏิบัติตามข้อกำหนดอย่างน้อยหนึ่งข้อโดยการเพิ่มตัวเลขลงในเซตหรือห้ามตัวเลขออกจากเซต เพื่อให้เซตสุดท้ายเป็นไปตามข้อกำหนด อาจเกิดขึ้นได้ว่าการปฏิบัติตามข้อกำหนดหนึ่งข้อจะทำให้ข้อกำหนดอื่นไม่เป็นไปตามข้อกำหนด ลำดับความสำคัญจะถูกใช้เพื่อตัดสินใจว่าจะทำอย่างไรในกรณีเช่นนั้น

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

เมื่อ Post นิยามแนวคิดของเซตแบบง่ายว่าเป็นเซต ce ที่มีคอมพลีเมนต์อนันต์ซึ่งไม่มีเซต ce อนันต์ใดๆ เขาจึงเริ่มศึกษาโครงสร้างของเซตที่นับได้ด้วยการคำนวณภายใต้การรวม แลตทิซ นี้ กลายเป็นโครงสร้างที่ได้รับการศึกษาอย่างดี เซตที่คำนวณได้สามารถนิยามได้ในโครงสร้างนี้โดยผลลัพธ์พื้นฐานที่ว่าเซตจะคำนวณได้ก็ต่อเมื่อเซตและคอมพลีเมนต์ของเซตนั้นสามารถนับได้ด้วยการคำนวณทั้งคู่ เซต ce อนันต์จะมีเซตย่อยที่คำนวณได้เป็นอนันต์เสมอ แต่ในทางกลับกัน เซตแบบง่ายมีอยู่แต่ไม่ได้มีซูเปอร์เซตที่คำนวณได้เป็นอนันต์เสมอไป Post ^{[ 15 ]}ได้แนะนำเซตไฮเปอร์ซิมเพิลและไฮเปอร์ไฮเปอร์ซิมเพิลแล้ว ต่อมาได้มีการสร้างเซตสูงสุด ซึ่งเป็นเซต ce ที่ซูเปอร์เซต ce ทุกเซตเป็นได้ทั้งรูปแบบจำกัดของเซตสูงสุดที่กำหนดหรือเป็นโคไฟไนต์ แรงจูงใจดั้งเดิมของโพสต์ในการศึกษาแลตทิซนี้คือการค้นหาแนวคิดเชิงโครงสร้างที่ทำให้เซตทุกเซตที่ตรงตามคุณสมบัตินี้ไม่อยู่ในระดับทัวริงของเซตที่คำนวณได้และไม่อยู่ในระดับทัวริงของปัญหาการหยุดทำงาน โพสต์ไม่พบคุณสมบัติดังกล่าว และวิธีแก้ปัญหาของเขาใช้วิธีการจัดลำดับความสำคัญแทน ในปี 1991 ในที่สุดแฮร์ริงตันและโซอาร์^{[ 19 ]}ก็พบคุณสมบัติดังกล่าว

คำถามสำคัญอีกประการหนึ่งคือการมีอยู่ของออโตมอร์ฟิซึมในโครงสร้างเชิงทฤษฎีการคำนวณ โครงสร้างหนึ่งในนั้นคือเซตที่นับได้ด้วยการคำนวณภายใต้การรวมโมดูลผลต่างจำกัด ในโครงสร้างนี้Aอยู่ต่ำกว่าBก็ต่อเมื่อผลต่างของเซตB  −  Aเป็นค่าจำกัดเซตสูงสุด (ตามที่กำหนดไว้ในย่อหน้าก่อนหน้า) มีคุณสมบัติว่าไม่สามารถเป็นออโตมอร์ฟิกกับเซตที่ไม่ใช่เซตสูงสุดได้ กล่าวคือ หากมีออโตมอร์ฟิซึมของเซตที่นับได้ด้วยการคำนวณภายใต้โครงสร้างที่กล่าวถึงข้างต้น เซตสูงสุดทุกเซตจะถูกแมปไปยังเซตสูงสุดอีกเซตหนึ่ง ในปี 1974 Soare ^{[ 20 ]}แสดงให้เห็นว่าข้อความกลับก็เป็นจริงเช่นกัน กล่าวคือ เซตสูงสุดสองเซตใดๆ ก็เป็นออโตมอร์ฟิกกันได้ ดังนั้นเซตสูงสุดจึงก่อตัวเป็นวงโคจร กล่าวคือ ออโตมอร์ฟิซึมทุกตัวรักษาความเป็นเซตสูงสุดไว้ และเซตสูงสุดสองเซตใดๆ ก็สามารถแปลงเป็นกันและกันได้ด้วยออโตมอร์ฟิซึมบางอย่าง แฮร์ริงตันได้ยกตัวอย่างเพิ่มเติมของคุณสมบัติออโตมอร์ฟิก นั่นคือเซตสร้างสรรค์ ซึ่งเป็นเซตที่เทียบเท่ากับปัญหาการหยุดแบบหลายต่อหนึ่ง

นอกจากแลตติซของเซตที่นับได้ด้วยการคำนวณแล้ว ยังมีการศึกษาออโตมอร์ฟิซึมสำหรับโครงสร้างของดีกรีทัวริงของเซตทั้งหมด รวมถึงโครงสร้างของดีกรีทัวริงของเซต ce ด้วย ในทั้งสองกรณี คูเปอร์อ้างว่าได้สร้างออโตมอร์ฟิซึมที่ไม่ธรรมดาซึ่งแมปดีกรีบางส่วนไปยังดีกรีอื่นๆ อย่างไรก็ตาม การสร้างนี้ยังไม่ได้รับการตรวจสอบ และเพื่อนร่วมงานบางคนเชื่อว่าการสร้างนี้มีข้อผิดพลาด และคำถามที่ว่ามีออโตมอร์ฟิซึมที่ไม่ธรรมดาของดีกรีทัวริงหรือไม่ยังคงเป็นหนึ่งในคำถามหลักที่ยังไม่ได้รับการแก้ไขในสาขานี้^{[ 21 ] [ 17 ]}

สาขาความซับซ้อนของ Kolmogorovและความสุ่มเชิงอัลกอริทึมได้รับการพัฒนาในช่วงทศวรรษ 1960 และ 1970 โดย Chaitin, Kolmogorov, Levin, Martin-Löf และ Solomonoff (ชื่อเรียงตามลำดับตัวอักษร งานวิจัยส่วนใหญ่เป็นอิสระ และในขณะนั้นยังไม่เข้าใจถึงความเป็นเอกภาพของแนวคิดเรื่องความสุ่ม) แนวคิดหลักคือการพิจารณาเครื่องจักรทัวริงสากลUและวัดความซับซ้อนของตัวเลข (หรือสตริง) xเป็นความยาวของอินพุตที่สั้นที่สุดpที่ทำให้U ( p ) ส่งออกxวิธีการนี้ได้ปฏิวัติวิธีการก่อนหน้านี้ในการพิจารณาว่าลำดับอนันต์ (หรือเทียบเท่ากับฟังก์ชันลักษณะเฉพาะของเซตย่อยของจำนวนธรรมชาติ) เป็นแบบสุ่มหรือไม่ โดยการใช้แนวคิดเรื่องความสุ่มสำหรับวัตถุจำกัด ความซับซ้อนของ Kolmogorov ไม่เพียงแต่กลายเป็นหัวข้อของการศึกษาอิสระเท่านั้น แต่ยังถูกนำไปประยุกต์ใช้กับหัวข้ออื่น ๆ ในฐานะเครื่องมือในการพิสูจน์อีกด้วย ยังคงมีปัญหาที่ยังไม่ได้รับการแก้ไขอีกมากมายในสาขานี้^{[ d ]}

ทฤษฎีความสามารถในการคำนวณสาขานี้ได้วิเคราะห์คำถามต่อไปนี้: สำหรับค่าmและn ที่กำหนดไว้ โดยที่ 0 <  m  <  nฟังก์ชันAใดบ้างที่สามารถคำนวณได้สำหรับอินพุตx ₁ ,  x ₂ , ...,  x _n ที่แตกต่างกัน n ตัว ให้ได้ ทูเปิลของตัวเลขn ตัว y ₁ , y ₂ , ..., y _nโดยที่อย่างน้อยmสมการA ( x _k ) = y _kเป็นจริง เซตดังกล่าวเรียกว่าเซตแบบ ( m ,  n )-recursive ผลลัพธ์สำคัญแรกในทฤษฎีความสามารถในการคำนวณสาขานี้คือผลลัพธ์ของ Trakhtenbrot ที่ว่าเซตสามารถคำนวณได้หากเป็นเซตแบบ ( m , n  ) -recursive สำหรับm ,  n บางตัว โดยที่2m  >  nในทางกลับกัน เซต แบบกึ่งเรียกซ้ำ ของ Jockusch (ซึ่งเป็นที่รู้จักกันอย่างไม่เป็นทางการมาก่อนที่ Jockusch จะนำเสนอในปี 1968) เป็นตัวอย่างของเซตที่เป็น ( m ,  n )-เรียกซ้ำก็ต่อเมื่อ 2m <  n  +  1 เท่านั้น เซตเหล่านี้มีจำนวนนับไม่ถ้วน และยังมีเซตที่สามารถนับได้แต่ไม่สามารถคำนวณได้อีกหลายเซต ต่อมา Degtev ได้สร้างลำดับชั้นของเซตที่สามารถนับได้ซึ่งเป็น (1,  n  + 1)-เรียกซ้ำแต่ไม่ใช่ (1,  n )-เรียกซ้ำ หลังจากช่วงเวลาการวิจัยอันยาวนานโดยนักวิทยาศาสตร์ชาวรัสเซีย หัวข้อนี้ก็กลับมาได้รับความนิยมอีกครั้งในโลกตะวันตกโดยวิทยานิพนธ์ของ Beigel เกี่ยวกับการสอบถามแบบจำกัด ซึ่งเชื่อมโยงการคำนวณความถี่เข้ากับการลดทอนแบบจำกัดที่กล่าวถึงข้างต้นและแนวคิดอื่นๆ ที่เกี่ยวข้อง หนึ่งในผลลัพธ์ที่สำคัญคือทฤษฎีบทจำนวนสมาชิกของ Kummer ^{[ 22 ] [ 23 ]}ซึ่งระบุว่าเซตAสามารถคำนวณได้ก็ต่อเมื่อมีเครื่องจักร Turing ที่เมื่อได้รับอินพุตn ตัว x ₁ ,  x ₂ , ...,  x _nจะส่งคืนเอาต์พุตอย่างมากที่สุดnตัว ซึ่งหนึ่งในนั้นคือจำนวนสมาชิกของ { x ₁ ,  x ₂ , ...,  x _n }∩A (มี ค่าที่เป็นไปได้ของจำนวนสมาชิก เพียง n + 1 ค่าเท่านั้น: 0, ..., n )

นี่คือสาขาทฤษฎีการเรียนรู้เชิงคำนวณ โดยอิงจากแบบจำลองการเรียนรู้ในขีดจำกัดของE. Mark Gold ในปี 1967 และได้พัฒนาแบบจำลองการเรียนรู้เพิ่มเติมอีกมากมายนับตั้งแต่นั้นมา สถานการณ์ทั่วไปมีดังนี้: กำหนดให้คลาส Sของฟังก์ชันที่คำนวณได้ มีผู้เรียน (นั่นคือ ฟังก์ชันที่คำนวณได้) ที่สร้างสมมติฐานสำหรับอินพุตใดๆ ในรูปแบบ ( f (0),  f (1), ...,  f ( n )) หรือไม่ ผู้เรียนMเรียนรู้ฟังก์ชันf ถ้าสมมติฐานเกือบทั้งหมดมีดัชนี eเดียวกันกับfโดยสัมพันธ์กับการกำหนดหมายเลขที่ยอมรับได้ซึ่งตกลงกันไว้ก่อนหน้านี้สำหรับฟังก์ชันที่คำนวณได้ทั้งหมดMเรียนรู้Sถ้าMเรียนรู้ทุกfในSผลลัพธ์พื้นฐานคือ คลาสของฟังก์ชันที่แจงนับได้ทั้งหมดสามารถเรียนรู้ได้ ในขณะที่คลาส REC ของฟังก์ชันที่คำนวณได้ทั้งหมดไม่สามารถเรียนรู้ได้ มีการพิจารณาแบบจำลองที่เกี่ยวข้องมากมาย และการเรียนรู้คลาสของเซตที่แจงนับได้จากข้อมูลเชิงบวกก็เป็นหัวข้อที่ศึกษามาตั้งแต่บทความบุกเบิกของ Gold ในปี 1967 เป็นต้นมา

ทฤษฎีความสามารถในการคำนวณประกอบด้วยการศึกษาแนวคิดทั่วไปของสาขานี้ เช่นความสามารถในการลดรูปทางเลขคณิต ความสามารถ ในการลดรูปทางเลขคณิตขั้นสูงและทฤษฎีการเรียกซ้ำ αดังที่ Sacks อธิบายไว้ในปี 1990 ^{[ 24 ]}แนวคิดทั่วไปเหล่านี้รวมถึงความสามารถในการลดรูปที่ไม่สามารถดำเนินการโดยเครื่องจักรทัวริงได้ แต่ยังคงเป็นการวางนัยทั่วไปตามธรรมชาติของความสามารถในการลดรูปของทัวริง การศึกษาเหล่านี้รวมถึงแนวทางในการตรวจสอบลำดับชั้นเชิงวิเคราะห์ซึ่งแตกต่างจากลำดับชั้นทางเลขคณิตโดยอนุญาตให้มีการกำหนดปริมาณเหนือเซตของจำนวนธรรมชาติ นอกเหนือจากการกำหนดปริมาณเหนือจำนวนแต่ละจำนวน พื้นที่เหล่านี้เชื่อมโยงกับทฤษฎีของการจัดลำดับที่ดีและต้นไม้ ตัวอย่างเช่น เซตของดัชนีทั้งหมดของต้นไม้ที่คำนวณได้ (ไม่ใช่ไบนารี) ที่ไม่มีกิ่งอนันต์นั้นสมบูรณ์สำหรับระดับของลำดับชั้นเชิงวิเคราะห์ ทั้งความสามารถในการลดรูปของทัวริงและความสามารถในการลดรูปทางเลขคณิตขั้นสูงมีความสำคัญในสาขาทฤษฎีเซตเชิงพรรณนาที่มีประสิทธิภาพ แนวคิดที่ครอบคลุมยิ่งกว่านั้นเกี่ยวกับระดับของความสามารถในการสร้างนั้นได้รับการศึกษาในทฤษฎีเซต ${\displaystyle \Pi _{1}^{1}}$

ทฤษฎีความสามารถในการคำนวณสำหรับการคำนวณแบบดิจิทัลได้รับการพัฒนามาเป็นอย่างดี แต่ทฤษฎีความสามารถในการคำนวณสำหรับการคำนวณแบบอนาล็อกที่เกิดขึ้นในคอมพิวเตอร์อนาล็อกการประมวลผลสัญญาณอนาล็อกอิเล็กทรอนิกส์อนาล็อกเครือข่ายประสาทเทียม และ ทฤษฎีการควบคุมเวลาต่อเนื่องซึ่งจำลองโดยสมการเชิงอนุพันธ์และระบบพลวัต ต่อเนื่องนั้นยัง ไม่ ได้รับการพัฒนาเท่าที่ควร ^{[ 25 ] [ 26 ]}ตัวอย่างเช่น แบบจำลองการคำนวณ เช่น แบบจำลอง เครื่องจักร Blum–Shub–Smaleได้กำหนดรูปแบบการคำนวณบนจำนวนจริงอย่างเป็นทางการ

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

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

สาขาทฤษฎีการพิสูจน์ประกอบด้วยการศึกษาเลขคณิตอันดับสองและเลขคณิตของ Peanoรวมถึงทฤษฎีเชิงรูปธรรมของจำนวนธรรมชาติที่อ่อนแอกว่าเลขคณิตของ Peano วิธีหนึ่งในการจำแนกความแข็งแกร่งของระบบที่อ่อนแอเหล่านี้คือการกำหนดลักษณะเฉพาะของฟังก์ชันที่คำนวณได้ที่ระบบสามารถพิสูจน์ได้ว่าเป็นฟังก์ชันสมบูรณ์[ ^{27 ] ตัวอย่าง}เช่น ในเลขคณิตแบบเรียกซ้ำดั้งเดิมฟังก์ชันที่คำนวณได้ใดๆ ที่พิสูจน์ได้ว่าเป็นฟังก์ชันสมบูรณ์นั้นเป็นเลขคณิตแบบเรียกซ้ำดั้งเดิมในขณะที่เลขคณิตของ Peanoพิสูจน์ว่าฟังก์ชันเช่นฟังก์ชัน Ackermannซึ่งไม่ใช่เลขคณิตแบบเรียกซ้ำดั้งเดิมนั้นเป็นฟังก์ชันสมบูรณ์ อย่างไรก็ตาม ไม่ใช่ทุกฟังก์ชันที่คำนวณได้ที่เป็นฟังก์ชันสมบูรณ์จะพิสูจน์ได้ว่าเป็นฟังก์ชันสมบูรณ์ในเลขคณิตของ Peano ตัวอย่างของฟังก์ชันดังกล่าวมีอยู่ในทฤษฎีบทของ Goodstein

สาขาตรรกศาสตร์ทางคณิตศาสตร์ที่เกี่ยวข้องกับการคำนวณได้และการสรุปทั่วไปของมันนั้นถูกเรียกว่า "ทฤษฎีการเรียกซ้ำ" มาตั้งแต่ยุคแรกเริ่มโรเบิร์ต ไอ. โซอาเรนักวิจัยที่มีชื่อเสียงในสาขานี้ ได้เสนอ^{[ 13 ]}ว่าควรเรียกสาขานี้ว่า "ทฤษฎีการคำนวณได้" แทน เขาให้เหตุผลว่าคำศัพท์ของทัวริงที่ใช้คำว่า "คำนวณได้" นั้นเป็นธรรมชาติและเข้าใจได้ง่ายกว่าคำศัพท์ที่ใช้คำว่า "เรียกซ้ำ" ที่คลีนนำมาใช้ นักวิจัยร่วมสมัยหลายคนเริ่มใช้คำศัพท์ทางเลือกนี้^{[ e ]}นักวิจัยเหล่านี้ยังใช้คำศัพท์เช่นฟังก์ชันที่คำนวณได้บางส่วนและเซตที่แจงนับได้ ( ce ) แทนฟังก์ชันเรียกซ้ำบางส่วนและเซต ที่แจงนับได้ แบบเรียกซ้ำ ( re ) อย่างไรก็ตาม นักวิจัยบางส่วนยังไม่เห็นด้วย ดังที่ฟอร์ทนอว์ ^{[ 28 ]}และซิมป์สันได้อธิบายไว้^{[ 29 ]} นักวิจารณ์บางคนโต้แย้งว่าทั้งชื่อทฤษฎีการเรียกซ้ำและทฤษฎีความสามารถในการคำนวณไม่สามารถสื่อถึงข้อเท็จจริงที่ว่าวัตถุส่วนใหญ่ที่ศึกษาในทฤษฎีความสามารถในการคำนวณนั้นไม่สามารถคำนวณได้^{[ 30 ]}

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

องค์กรวิชาชีพหลักด้านทฤษฎีความสามารถในการคำนวณคือสมาคมตรรกศาสตร์เชิงสัญลักษณ์ (Association for Symbolic Logic ) ซึ่งจัดการประชุมวิจัยหลายครั้งในแต่ละปี นอกจากนี้ สมาคมวิจัยสหวิทยาการด้านความสามารถ ในการคำนวณในยุโรป ( Association Computability in Europe หรือ CiE ) ก็จัดการประชุมประจำปีหลายครั้งเช่นกัน

• การเรียกซ้ำ (วิทยาการคอมพิวเตอร์)
• ตรรกะการคำนวณ
• ปัญหาการประมวลผลข้ามระบบ

ตำราเรียนระดับปริญญาตรี

• คูเปอร์, เอส. แบร์รี (2004). ทฤษฎีความสามารถในการคำนวณ . แชปแมน แอนด์ ฮอลล์ /CRC. ISBN 1-58488-237-9.
• มาติยาเซวิช, ยูริ วลาดิมิโรวิช (1993) ปัญหาที่สิบของฮิลเบิร์ตสำนักพิมพ์เอ็มไอทีไอเอสบีเอ็น 0-262-13295-8.

ตำราขั้นสูง

• Jain, Sanjay; Osherson, Daniel Nathan ; Royer, James S.; Sharma, Arun (1999). ระบบที่เรียนรู้: บทนำสู่ทฤษฎีการเรียนรู้ (ฉบับที่ 2). Bradford Book / MIT Press . ISBN 0-262-10077-0. ลคซีเอ็น 98-34861 .
• เลอร์แมน, มานูเอล (1983). ระดับของความไม่สามารถแก้ปัญหาได้ . มุมมองในตรรกศาสตร์ทางคณิตศาสตร์. สปริงเกอร์-เวอร์แลก . ISBN 3-540-12155-2.
• Nies, André (2009). ความสามารถในการคำนวณและความสุ่ม . สำนักพิมพ์มหาวิทยาลัยออกซ์ฟอร์ ด . ISBN 978-0-19-923076-1.
• Odifreddi, Piergiorgio (1989). ทฤษฎีการเรียกซ้ำแบบคลาสสิก . นอร์ทฮอลแลนด์ . ISBN 0-444-87295-7.
• โอดิเฟรดดี้, ปิแอร์จิออร์จิโอ (1999) ทฤษฎีการเรียกซ้ำแบบคลาสสิก ฉบับที่ ครั้งที่สองเอลส์เวียร์ . ไอเอสบีเอ็น 0-444-50205-X.

เอกสารและชุดเอกสารสำรวจ

• เอ็นเดอร์ตัน, เฮอร์เบิร์ต บรูซ (1977). "องค์ประกอบของทฤษฎีการเรียกซ้ำ"ในบาร์ไวส์, จอน (บรรณาธิการ). คู่มือตรรกศาสตร์ทางคณิตศาสตร์ . นอร์ท-ฮอลแลนด์ . หน้า  527–566 . ISBN 0-7204-2285-X.

เอกสารวิจัยและชุดเอกสาร

• Burgin, Mark; Klinger, Allen (2004). "ประสบการณ์ รุ่น และข้อจำกัดในการเรียนรู้ของเครื่องจักร" วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี 317 ( 1– 3 ): 71– 91. doi : 10.1016/j.tcs.2003.12.005 .
• Friedberg, Richard M. (1958). "ทฤษฎีบทสามข้อเกี่ยวกับการแจงนับแบบเรียกซ้ำ: I. การแยกส่วน, II. เซตสูงสุด, III. การแจงนับโดยไม่ซ้ำ". วารสารตรรกศาสตร์เชิงสัญลักษณ์ 23 ( 3): 309– 316. doi : 10.2307/2964290 . JSTOR  2964290 . S2CID  25834814 .
• Gold, E. Mark (1967). "การระบุภาษาในขีดจำกัด" (PDF) . ข้อมูลและการควบคุม . 10 (5): 447– 474. doi : 10.1016/s0019-9958(67)91165-5 .[1]
• Jockusch, Carl Groos Jr. (1968). "เซตแบบกึ่งเรียกซ้ำและการลดรูปเชิงบวก" . ธุรกรรมของสมาคมคณิตศาสตร์อเมริกัน . 137 (2): 420– 436. doi : 10.1090/S0002-9947-1968-0220595-7 . JSTOR  1994957 .
• Kleene, Stephen Cole ; Post, Emil Leon (1954). "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics . Series 2. 59 (3): 379– 407. doi : 10.2307/1969708 . JSTOR  1969708 .
• Myhill, John R. Sr. (1956). "โครงข่ายของเซตที่นับได้แบบเวียนซ้ำ" วารสารตรรกศาสตร์เชิงสัญลักษณ์ 21 : 215– 220. doi : 10.1017 /S002248120008525X . S2CID  123260425 .
• Post, Emil Leon (1947). "ความไม่สามารถแก้ปัญหาแบบเรียกซ้ำของปัญหาของ Thue". Journal of Symbolic Logic . 12 (1): 1– 11. doi : 10.2307/2267170 . JSTOR  2267170 . S2CID  30320278 .ตีพิมพ์ซ้ำในDavis ปี 1965

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับทฤษฎีความสามารถในการคำนวณ

• หน้าหลักของสมาคมตรรกศาสตร์เชิงสัญลักษณ์
• หน้าหลักของเว็บไซต์ Computability in Europe ถูกเก็บถาวรเมื่อวันที่ 17 กุมภาพันธ์ 2011 ที่Wayback Machine
• เว็บเพจเกี่ยวกับหลักสูตรทฤษฎีการเรียกซ้ำระดับบัณฑิตศึกษา พร้อมเอกสารประกอบการบรรยายประมาณ 100 หน้า
• บันทึกการบรรยายภาษาเยอรมันเรื่องการอนุมานแบบอุปนัย