ทฤษฎีความสามารถในการคำนวณในตรรกศาสตร์ทางคณิตศาสตร์โดยทั่วไปมุ่งเน้นไปที่ความสามารถ ในการคำนวณ เชิงสัมพัทธ์ ซึ่งเป็นการวางนัยทั่วไปของความสามารถในการคำนวณของทัวริงที่กำหนดโดยใช้เครื่องจักรทัวริงแบบออราเคิลซึ่งทัวริงได้แนะนำในปี 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 อยู่ในC } มีคุณสมบัติที่ว่าปัญหาการหยุดหรือส่วนเติมเต็มของปัญหานั้นสามารถลดรูปได้แบบหลายต่อหนึ่งไปยังEกล่าวคือ สามารถแมปโดยใช้การลดรูปหลายต่อหนึ่งไปยังE ได้ (ดูทฤษฎีบทของไรซ์สำหรับรายละเอียดเพิ่มเติม) แต่เซตดัชนีเหล่านี้จำนวนมากมีความซับซ้อนมากกว่าปัญหาการหยุด เซตประเภทนี้สามารถจำแนกประเภทได้โดยใช้ลำดับชั้นทางเลขคณิตตัวอย่างเช่น เซตดัชนี FIN ของคลาสของเซตจำกัดทั้งหมดอยู่ในระดับ Σ เซตดัชนี REC ของคลาสของเซตเวียนเกิดทั้งหมดอยู่ในระดับ Σ เซตดัชนี COFIN ของเซตโคไฟไนต์ทั้งหมดก็อยู่ในระดับ Σ เช่นกัน และเซตดัชนี COMP ของคลาสของเซตที่สมบูรณ์แบบทัวริงทั้งหมด อยู่ในระดับ Σ ระดับลำดับชั้นเหล่านี้ถูกกำหนดขึ้นโดยอุปนัย โดย Σ ประกอบด้วยเซตทั้งหมดที่สามารถแจงนับได้โดยการคำนวณเมื่อเทียบกับ Σ และ Σ ประกอบด้วยเซตที่สามารถแจงนับได้โดยการคำนวณ เซตดัชนีที่ให้ไว้ในที่นี้สมบูรณ์แม้กระทั่งสำหรับระดับของมัน กล่าวคือ เซตทั้งหมดในระดับเหล่านี้สามารถลดรูปหลายต่อหนึ่งไปยังเซตดัชนีที่กำหนดให้

โปรแกรมคณิตศาสตร์ย้อนกลับถามว่าสัจพจน์การมีอยู่ของเซตใดบ้างที่จำเป็นต่อการพิสูจน์ทฤษฎีบทเฉพาะของคณิตศาสตร์ในระบบย่อยของเลขคณิตอันดับสองการศึกษานี้ริเริ่มโดย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 ]}แสดงให้เห็นว่าข้อความกลับก็เป็นจริงเช่นกัน กล่าวคือ เซตสูงสุดสองเซตใดๆ ก็เป็นออโตมอร์ฟิกกันได้ ดังนั้นเซตสูงสุดจึงก่อตัวเป็นวงโคจร กล่าวคือ ออโตมอร์ฟิซึมทุกตัวรักษาความเป็นเซตสูงสุดไว้ และเซตสูงสุดสองเซตใดๆ ก็สามารถแปลงเป็นกันและกันได้ด้วยออโตมอร์ฟิซึมบางอย่าง แฮร์ริงตันได้ยกตัวอย่างเพิ่มเติมของคุณสมบัติออโตมอร์ฟิก นั่นคือเซตสร้างสรรค์ ซึ่งเป็นเซตที่เทียบเท่ากับปัญหาการหยุดแบบหลายต่อหนึ่ง  

Besides the lattice of computably enumerable sets, automorphisms are also studied for the structure of the Turing degrees of all sets as well as for the structure of the Turing degrees of c.e. sets. In both cases, Cooper claims to have constructed nontrivial automorphisms that map some degrees to other degrees; this construction has, however, not been verified and some colleagues believe that the construction contains errors and that the question of whether there is a nontrivial automorphism of the Turing degrees is still one of the main unsolved questions in this area.^[21][17]

The field of Kolmogorov complexity and algorithmic randomness was developed during the 1960s and 1970s by Chaitin, Kolmogorov, Levin, Martin-Löf and Solomonoff (the names are given here in alphabetical order; much of the research was independent, and the unity of the concept of randomness was not understood at the time). The main idea is to consider a universal Turing machineU and to measure the complexity of a number (or string) x as the length of the shortest input p such that U(p) outputs x. This approach revolutionized earlier ways to determine when an infinite sequence (equivalently, characteristic function of a subset of the natural numbers) is random or not by invoking a notion of randomness for finite objects. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs. There are still many open problems in this area.^[d]

ทฤษฎีความสามารถในการคำนวณสาขานี้ได้วิเคราะห์คำถามต่อไปนี้: สำหรับค่าmและn ที่กำหนดไว้ โดยที่ 0 < m < nฟังก์ชันAใดบ้างที่สามารถคำนวณได้สำหรับอินพุตx , x , ..., x ที่แตกต่างกัน n ตัว ให้ได้ ทูเปิลของตัวเลขn ตัว y , y , ..., y โดยที่อย่างน้อยmสมการA ( x ) = y เป็นจริง เซตดังกล่าวเรียกว่าเซตแบบ ( 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สามารถคำนวณได้ก็ต่อเมื่อมีเครื่องจักรทัวริงที่เมื่อได้รับอินพุตn ตัว x , x , ..., x จะส่งคืนเอาต์พุตอย่างมากที่สุดnตัว โดยหนึ่งในนั้นคือจำนวนสมาชิกของ { x , x , ..., x }∩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ได้กำหนดรูปแบบการคำนวณบนจำนวนจริงอย่างเป็นทางการ