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

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

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

แนวคิด เรื่องระดับทัวริง (Turing degrees) ถูกนำเสนอโดยโพสต์ (Post, 1944)และผลลัพธ์พื้นฐานหลายอย่างได้รับการพิสูจน์โดยคลีน และโพสต์ (Kleene & Post, 1954)นับตั้งแต่นั้นมา ระดับทัวริงก็เป็นหัวข้อการวิจัยที่เข้มข้น การพิสูจน์หลายอย่างในสาขานี้ใช้วิธีการพิสูจน์ที่เรียกว่าวิธีลำดับความสำคัญ (priority method )

ในส่วนที่เหลือของบทความนี้ คำว่า"เซต"จะหมายถึงเซตของจำนวนธรรมชาติ เซตXกล่าวได้ว่าสามารถลดรูปได้ด้วยเครื่องจักรทัวริงไปเป็นเซตYหากมีเครื่องจักรทัวริงแบบออราเคิลที่สามารถตัดสินได้ว่าเซต X เป็นสมาชิกของเซตX หรือไม่ เมื่อได้รับออราเคิลสำหรับการเป็นสมาชิกของเซตYสัญลักษณ์X ≤ Yแสดงว่าXสามารถลดรูปได้ด้วยเครื่องจักรทัวริงไปเป็นY

เซตXและYจะถูกนิยามว่าสมมูลกันในเชิงทัวริง (Turing equivalent)ถ้าXสามารถลดรูปได้ในเชิงทัวริง (Turing reducible) ไปเป็น YและY สามารถลดรูปได้ในเชิงทัวริงไปเป็น Xสัญลักษณ์X ≡ Yแสดงว่าXและYสมมูลกันในเชิงทัวริง ความสัมพันธ์≡ สามารถมองได้ว่าเป็นความสัมพันธ์สมมูลซึ่งหมายความว่าสำหรับทุกเซตX , YและZ :

• X ≡ X
• X ≡ Yหมายความว่าY ≡ X
• ถ้าX ≡ YและY ≡ Zแล้วX ≡ Z​

ระดับทัวริง (Turing degree)คือชั้นสมมูลของความสัมพันธ์≡ สัญลักษณ์ [ X ] หมายถึงชั้นสมมูลที่ประกอบด้วยเซตXส่วนระดับทัวริงทั้งหมดจะใช้สัญลักษณ์ แทน${\displaystyle {\mathcal {D}}}$.

ระดับทัวริงมีลำดับบางส่วน≤ที่กำหนดไว้เพื่อให้ [ X ] ≤ [ Y ] ก็ต่อเมื่อX ≤ Y เท่านั้น มีระดับทัวริงที่ไม่ซ้ำกันเพียงหนึ่งเดียวที่ประกอบด้วยเซตที่คำนวณได้ ทั้งหมด และระดับนี้มีค่าน้อยกว่าระดับอื่นๆ ทุกระดับ โดยใช้สัญลักษณ์0 (ศูนย์) เพราะเป็นองค์ประกอบที่เล็กที่สุดของเซตลำดับบางส่วน${\displaystyle {\mathcal {D}}}$(โดยทั่วไปมักใช้ตัวหนาสำหรับระดับทัวริง เพื่อแยกความแตกต่างจากเซต เมื่อไม่มีความสับสนเกิดขึ้น เช่นกับ [ X ] การใช้ตัวหนาจึงไม่จำเป็น)

สำหรับเซตXและY ใดๆ เซตX เชื่อมYซึ่งเขียนว่าX ⊕ Yถูกกำหนดให้เป็นการรวมกันของเซต{2 n  : n ∈ X } และ {2 m +1  : m ∈ Y } ดีกรีทัวริงของX ⊕ Yคือขอบเขตบนน้อยที่สุดของดีกรีของXและYดังนั้น${\displaystyle {\mathcal {D}}}$เป็นเซมิแลตติซแบบเชื่อมต่อ ขอบเขตบนสุดที่น้อยที่สุดของดีกรีaและbจะถูกแทนด้วยa ∪ bเป็นที่ทราบกันว่า${\displaystyle {\mathcal {D}}}$ไม่ใช่โครงสร้างแลตทิซเนื่องจากมีคู่ของดีกรีที่ไม่มีขอบเขตล่างที่มากที่สุด

สำหรับเซตX ใดๆ สัญลักษณ์X ′ หมายถึงเซตของดัชนีของเครื่องออราเคิลที่หยุดทำงาน (เมื่อได้รับดัชนีเป็นอินพุต) เมื่อใช้Xเป็นออราเคิล เซตX ′เรียกว่าการกระโดดของทัวริงของXการกระโดดของทัวริงที่มีดีกรี [ X ] ถูกกำหนดให้เป็นดีกรี [ X ′ ] ซึ่งเป็นนิยามที่ถูกต้องเพราะX ′ ≡ Y ′เมื่อใดก็ตามที่X ≡ Yตัวอย่างสำคัญคือ0 ′ซึ่งเป็นดีกรีของ ปัญหาการ หยุดทำงาน

• ดีกรีทัวริงทุกค่าเป็นอนันต์นับได้นั่นคือ ประกอบด้วยค่าที่แน่นอนเพียงค่าเดียว${\displaystyle \aleph _{0}}$ชุดต่างๆ
• มีอยู่${\displaystyle 2^{\aleph _{0}}}$ระดับทัวริงที่แตกต่างกัน
• สำหรับแต่ละระดับaอสมการที่เข้มงวดa < a ′เป็นจริง
• สำหรับแต่ละระดับaเซตของระดับที่ต่ำกว่าaเป็นเซตที่นับได้เซตของระดับที่มากกว่าaมีขนาดเท่ากับ${\displaystyle 2^{\aleph _{0}}}$.

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

ดีกรีหนึ่งเรียกว่าสามารถแจงนับได้แบบเวียนซ้ำ (re) หรือแจงนับได้ด้วยการคำนวณ (ce) ถ้ามันประกอบด้วยเซตที่สามารถแจงนับได้แบบเวียนซ้ำ ดีกรีทุกตัวที่เป็น re จะมีค่าต่ำกว่า0 ′แต่ไม่ใช่ว่าทุกดีกรีที่ต่ำกว่า0 ′จะเป็น re อย่างไรก็ตาม เซต${\displaystyle A}$สามารถลดรูปหลายหนึ่งไปเป็น0 ′ได้ก็ต่อเมื่อ${\displaystyle A}$คือ re. ^{[ 3 ]}

• แซ็กส์ (1964) : ระดับ re มีความหนาแน่น กล่าวคือ ระหว่างระดับ re สองระดับใดๆ จะมีระดับ re ที่สามอยู่
• Lachlan (1966a)และYates (1966) : มีระดับ re สองระดับ โดยไม่มีขอบเขตล่างสูงสุดในระดับ re
• Lachlan (1966a)และYates (1966) : มีคู่ของระดับ re ที่ไม่เป็นศูนย์ซึ่งขอบล่างที่มากที่สุดคือ0
• ลัคแลน (1966b) : ไม่มีคู่ของค่า re ดีกรีใดที่มีขอบล่างมากที่สุดเป็น0และขอบบนน้อยที่สุดเป็น0 ′ผลลัพธ์นี้เรียกกันอย่างไม่เป็นทางการว่าทฤษฎีบทที่ไม่ใช่รูปเพชร
• Thomason (1971) : แลตทิซแบบกระจาย จำกัดทุกตัว สามารถฝังลงในระดับ re ได้ ในความเป็นจริงพีชคณิตบูลีนแบบไร้อะตอม ที่นับได้ สามารถฝังได้ในลักษณะที่รักษาค่าสูงสุดและค่าต่ำสุดไว้
• Lachlan & Soare (1980) : ไม่ใช่ว่า แลตติซจำกัดทั้งหมดจะสามารถฝังลงในระดับ re ได้ (ผ่านการฝังที่รักษา suprema และ infima ไว้) ตัวอย่างเฉพาะแสดงอยู่ทางด้านขวา
• LA HarringtonและTA Slaman (ดูNies, Shore & Slaman (1998) ): ทฤษฎีลำดับที่หนึ่งของระดับ re ในภาษา⟨ 0 , ≤ , = ⟩เทียบเท่ากับทฤษฎีของเลขคณิตลำดับที่หนึ่งที่แท้จริง แบบหลายต่อ หนึ่ง

นอกจากนี้ ยังมีทฤษฎีบทจำกัดของโชเอนฟิลด์ ซึ่งระบุว่าเซตAสอดคล้องกับเงื่อนไขต่อไป นี้${\displaystyle [A]\leq _{T}\emptyset '}$ก็ต่อเมื่อมี "การประมาณแบบเวียนซ้ำ" สำหรับฟังก์ชันลักษณะเฉพาะของมัน: ฟังก์ชันgเช่นนั้น สำหรับค่า sที่ มากพอ${\displaystyle g(s)=\chi _{A}(s)}$[ ^{4 ]​}

เซตAเรียกว่าเซต n -r e ถ้ามีตระกูลของฟังก์ชัน${\displaystyle (A_{s})_{s\in \mathbb {N} }}$โดยที่: ^{[ 4 ]}

• A คือการประมาณค่าแบบเวียนซ้ำของA : สำหรับt บางค่า สำหรับs ≥ t ใดๆ เราจะได้A ( x ) = A ( x ) โดยเฉพาะอย่างยิ่งการรวมA เข้า กับฟังก์ชันลักษณะเฉพาะของมัน( การลบเงื่อนไขนี้ออกจะทำให้ได้นิยามของ A ที่เป็น " n -re แบบอ่อน" )
• A คือ "述语แบบ nทดลอง": สำหรับทุกx , A ( x )=0 และจำนวนสมาชิกของ${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$คือ≤ n​

คุณสมบัติของ ระดับ n -re: ^{[ 4 ]}

• กลุ่มของเซตที่มี ดีกรี n -re เป็นกลุ่มย่อยที่แท้จริงของกลุ่มของเซตที่มีดีกรี ( n +1)-re
• สำหรับทุกn > 1 จะมีระดับ ( n + 1)-re สองตัวคือ a , bที่มี${\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$โดยที่ส่วนนั้น${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}$ไม่มีองศาn -re อยู่ภายใน
• ${\displaystyle A}$และ${\displaystyle {\overline {A}}}$เป็น ( n + 1)-re ก็ต่อเมื่อทั้งสองเซตเป็น weakly -n -re

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

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

ตัวอย่างเช่น เครื่องจักรทัวริง X ที่เรียบง่าย (และไม่สามารถคำนวณได้) (ต่ำ หมายถึงX ′=0′) สามารถสร้างขึ้นได้ในขั้นตอนที่ไม่มีที่สิ้นสุดดังต่อไปนี้ ในตอนเริ่มต้นของขั้นตอนที่nให้T เป็นเทปเอาต์พุต (ไบนารี) ซึ่งระบุด้วยชุดดัชนีเซลล์ที่เราวาง 1 ไว้จนถึงตอนนี้ (ดังนั้นX =∪ T ; T =∅)และให้P ( m ) เป็นลำดับความสำคัญสำหรับการไม่ส่งออก 1 ที่ตำแหน่งm ; P ( m )=∞ในขั้นตอนที่n ถ้าเป็นไปได้ (มิฉะนั้นไม่ต้องทำอะไรในขั้นตอนนี้) ให้เลือก i < nที่น้อยที่สุดโดยที่∀ m P ( m )≠ iและเครื่องจักรทัวริงiหยุดทำงานใน< n ขั้นตอนบนอินพุต S ⊇ T บางอย่างโดยที่∀ m ∈ S \ T P ( m ) ≥ i เลือก เซตSใดๆ (ที่มีขอบเขตจำกัด) กำหนด T = Sและสำหรับทุกเซลล์mที่เครื่องจักรi เยี่ยมชม บนSกำหนดP ( m ) = min( i , P ( m )) และกำหนดลำดับความสำคัญทั้งหมดที่มากกว่าiเป็น ∞ จากนั้นกำหนดเซลล์ที่มีลำดับความสำคัญ ∞ หนึ่งเซลล์ (เซลล์ใดก็ได้) ที่ไม่ได้อยู่ในSให้มีลำดับความสำคัญ เท่ากับ iโดยพื้นฐานแล้ว เราจะทำให้เครื่องจักรiหยุดทำงานหากสามารถทำได้โดยไม่กระทบต่อลำดับความสำคัญที่น้อยกว่าiจากนั้นกำหนดลำดับความสำคัญเพื่อป้องกันไม่ให้เครื่องจักร ที่มากกว่า iขัดขวางการหยุดทำงาน ลำดับความสำคัญทั้งหมดจะคงที่ในที่สุด

เพื่อให้เห็นว่าXมีค่าต่ำ เครื่องจักรiจะหยุดที่Xก็ต่อเมื่อมันหยุดภายใน< nขั้นตอนบนT บางตัว โดยที่เครื่องจักร< iที่หยุดที่Xจะหยุดภายใน< n − iขั้นตอน (โดยการเรียกซ้ำ สามารถคำนวณได้สม่ำเสมอจาก 0′) Xไม่สามารถคำนวณได้ เนื่องจากมิฉะนั้นเครื่องจักรทัวริงจะหยุดที่Yก็ต่อเมื่อY \ Xไม่ว่างเปล่า ซึ่งขัดแย้งกับการสร้าง เนื่องจากX ไม่รวมเซลล์ที่มีลำดับความสำคัญ iบางเซลล์สำหรับi ที่มีค่ามาก และXเรียบง่ายเพราะสำหรับแต่ละiจำนวนเซลล์ที่มีลำดับความสำคัญiมีค่าจำกัด

• วัดมาร์ติน