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

ตัวอย่างเช่น สมการไดโอแฟนไทน์มีคำตอบเป็นจำนวนเต็ม: ในทางตรงกันข้าม สมการไดโอแฟนไทน์ไม่มีคำตอบดังกล่าว ${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$${\displaystyle x=1,\ y=2,\ z=-2}$${\displaystyle x^{2}+y^{2}+1=0}$

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

เมื่อสัมประสิทธิ์และตัวแปรทั้งหมดถูกจำกัดให้เป็นจำนวนเต็มบวก ปัญหาที่เกี่ยวข้องกับการทดสอบเอกลักษณ์พหุนามคือรูปแบบที่ตัดสินได้ (ปราศจากการยกกำลัง) ของปัญหาพีชคณิตระดับมัธยมปลายของ Tarskiซึ่งบางครั้งเรียกว่า^{[ 4 ]}${\displaystyle {\overline {HSI}}.}$

ฮิลเบิร์ตได้กำหนดปัญหาไว้ดังนี้: ^{[ 5 ]}

กำหนดสมการไดโอแฟนไทน์ที่มีตัวแปรที่ไม่ทราบค่าจำนวนใดๆ และมีสัมประสิทธิ์เป็นจำนวนเต็มตรรกยะ: จงคิดค้นกระบวนการที่สามารถตรวจสอบได้ว่าสมการนั้นสามารถหาคำตอบได้ในจำนวนเต็มตรรกยะหรือไม่ โดยใช้จำนวนการดำเนินการที่จำกัด

คำว่า "กระบวนการ" และ "จำนวนการดำเนินการที่จำกัด" ถูกตีความว่าฮิลเบิร์ตกำลังถามถึงอัลกอริทึมส่วนคำว่า "ปริพันธ์เชิงตรรกะ" นั้นหมายถึงจำนวนเต็ม ไม่ว่าจะเป็นบวก ลบ หรือศูนย์ เช่น 0, ±1, ±2, ... ดังนั้น ฮิลเบิร์ตจึงถามถึงอัลกอริทึมทั่วไปเพื่อตัดสินว่าสมการไดโอแฟนไทน์ พหุนามที่กำหนด ซึ่งมีสัมประสิทธิ์เป็นจำนวนเต็มนั้นมีคำตอบเป็นจำนวนเต็ม หรือไม่

ปัญหาของฮิลเบิร์ตไม่ได้เกี่ยวข้องกับการหาคำตอบ แต่ถามเพียงว่าโดยทั่วไปแล้วเราสามารถตัดสินได้หรือไม่ว่ามีคำตอบหนึ่งหรือมากกว่าหนึ่งคำตอบ คำตอบของคำถามนี้คือ "ไม่" ในแง่ที่ว่าไม่มี "กระบวนการใด ๆ ที่สามารถคิดค้นขึ้น" เพื่อตอบคำถามนั้นได้ ในแง่สมัยใหม่ ปัญหาข้อที่สิบของฮิลเบิร์ตจึงเป็นปัญหาที่ไม่สามารถตัดสินได้

ในสมการไดโอแฟนไทน์ มีตัวแปรอยู่สองประเภท คือ พารามิเตอร์และตัวแปรที่ไม่ทราบค่าเซตไดโอแฟนไทน์ประกอบด้วยค่าพารามิเตอร์ที่ทำให้สมการไดโอแฟนไทน์สามารถหาคำตอบได้ ตัวอย่างทั่วไปคือสมการไดโอแฟนไทน์เชิงเส้นที่มีตัวแปรที่ไม่ทราบค่าสองตัว

${\displaystyle a_{1}x+a_{2}y=a_{3},}$

โดยสมการจะหาคำตอบได้ก็ต่อเมื่อตัวหารร่วมมากหารลงตัว เท่านั้น เซตของสามตัวเลขเรียงลำดับทั้งหมดที่ตรงตามเงื่อนไขนี้เรียกว่าเซตไดโอแฟนไทน์ซึ่งกำหนดโดยในแง่นี้ ปัญหาข้อที่สิบของฮิลเบิร์ตถามว่ามีอัลกอริทึมใดที่จะตรวจสอบได้หรือไม่ว่าเซตไดโอแฟนไทน์ที่สอดคล้องกับพหุนามใดๆ นั้นไม่ว่างเปล่า ${\displaystyle \gcd(a_{1},a_{2})}$${\displaystyle a_{3}}$${\displaystyle (a_{1},a_{2},a_{3})}$${\displaystyle a_{1}x+a_{2}y=a_{3}}$

โดยทั่วไปแล้ว ปัญหาจะเข้าใจได้ในแง่ของจำนวนธรรมชาติ (นั่นคือ จำนวนเต็มที่ไม่เป็นลบ) มากกว่าจำนวนเต็มใดๆ อย่างไรก็ตาม ปัญหาทั้งสองนั้นเทียบเท่ากัน กล่าวคือ อัลกอริทึมทั่วไปใดๆ ที่สามารถตัดสินได้ว่าสมการไดโอแฟนไทน์ที่กำหนดมีคำตอบเป็นจำนวนเต็มหรือไม่ สามารถปรับเปลี่ยนเป็นอัลกอริทึมที่ตัดสินได้ว่าสมการไดโอแฟนไทน์ที่กำหนดมีคำตอบเป็นจำนวนธรรมชาติหรือไม่ และในทางกลับกัน ตามทฤษฎีบทกำลังสองสี่ของลากรองจ์จำนวนธรรมชาติทุกจำนวนเป็นผลรวมของกำลังสองของจำนวนเต็มสี่จำนวน ดังนั้นเราจึงสามารถเขียนพารามิเตอร์ที่มีค่าเป็นจำนวนธรรมชาติทุกตัวใหม่ได้ในรูปของผลรวมของกำลังสองของพารามิเตอร์ที่มีค่าเป็นจำนวนเต็มใหม่สี่ตัว ในทำนองเดียวกัน เนื่องจากจำนวนเต็มทุกจำนวนเป็นผลต่างของจำนวนธรรมชาติสองจำนวน เราจึงสามารถเขียนพารามิเตอร์จำนวนเต็มทุกตัวใหม่เป็นผลต่างของพารามิเตอร์จำนวนธรรมชาติสองตัวได้^{[ 3 ]}ยิ่งไปกว่านั้น เราสามารถเขียนระบบสมการพร้อมกัน(โดยที่แต่ละสมการเป็นพหุนาม) ใหม่เป็นสมการเดียวได้ เสมอ${\displaystyle p_{1}=0,\ldots ,p_{k}=0}$${\displaystyle p_{i}}$${\displaystyle p_{1}^{\,2}+\cdots +p_{k}^{\,2}=0}$

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

เซตที่สามารถแจงนับได้แบบเวียนซ้ำทุกเซตเป็นเซตไดโอแฟนไทน์

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

${\displaystyle p(a,x_{1},\ldots ,x_{n})}$

โดยมีสัมประสิทธิ์จำนวนเต็ม โดยที่เซตของค่าของซึ่งสมการ ${\displaystyle a}$

${\displaystyle p(a,x_{1},\ldots ,x_{n})=0}$

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

ปี	กิจกรรม
1944	เอมิล ลีออน โพสต์ประกาศว่า ปัญหาข้อที่สิบของฮิลเบิร์ต "ต้องการการพิสูจน์ว่าไม่สามารถหาคำตอบได้"
1949	มาร์ติน เดวิส ใช้ระเบียบวิธีของเคิร์ต เกอเดล ในการประยุกต์ใช้ ทฤษฎีบทเศษเหลือของจีนเป็นเทคนิคการเขียนโค้ดเพื่อให้ได้รูปแบบมาตรฐานสำหรับเซตที่สามารถแจงนับได้แบบเวียนซ้ำ: ${\displaystyle \left\{a\mid \exists y\,\forall k\leqslant y\,\exists x_{1},\ldots ,x_{n}:p\left(a,k,y,x_{1},\ldots ,x_{n}\right)=0\right\}}$ โดยที่เป็นพหุนามที่มีสัมประสิทธิ์เป็นจำนวนเต็ม ในทางรูปแบบล้วนๆ มีเพียงตัวบ่งปริมาณสากลที่มีขอบเขตเท่านั้นที่ขัดขวางไม่ให้สิ่งนี้เป็นนิยามของเซตไดโอแฟนไทน์ ${\displaystyle p}$ โดยใช้การพิสูจน์ที่ไม่ซับซ้อนแต่ทำได้ง่าย เขาได้ข้อสรุปเป็นผลลัพธ์จากรูปแบบปกติว่า เซตของเซตไดโอแฟนไทน์ไม่ปิดภายใต้การเติมเต็ม โดยแสดงให้เห็นว่ามีเซตไดโอแฟนไทน์อยู่เซตหนึ่งซึ่งส่วนเติมเต็มของเซตนั้นไม่ใช่เซตไดโอแฟนไทน์ เนื่องจากเซตที่นับได้แบบเวียนซ้ำก็ไม่ปิดภายใต้การเติมเต็มเช่นกัน เขาจึงตั้งข้อสันนิษฐานว่าทั้งสองคลาสนี้เหมือนกัน
1950	จูเลีย โรบินสันซึ่งไม่ทราบถึงงานของเดวิส ได้ทำการตรวจสอบความเชื่อมโยงของฟังก์ชันเลขชี้กำลังกับปัญหาดังกล่าว และพยายามพิสูจน์ว่า EXP ซึ่งเป็นเซตของสามตัวเลขที่ เป็นเซตไดโอแฟนไทน์ เมื่อไม่สำเร็จ เธอจึงตั้ง สมมติฐานต่อไปนี้(ซึ่งต่อมาเรียกว่า JR):${\displaystyle (a,b,c)}$${\displaystyle a=b^{c}}$ มีเซตคู่ ไดโอแฟนไทน์ อยู่ชุดหนึ่งซึ่งและสำหรับทุกค่าบวกจะมีอยู่ค่าหนึ่งซึ่ง${\displaystyle D}$${\displaystyle (a,b)}$${\displaystyle (a,b)\in D\Rightarrow b<a^{a}}$${\displaystyle k,}$${\displaystyle (a,b)\in D}$${\displaystyle b>a^{k}.}$ โดยใช้คุณสมบัติของสมการเพลล์ เธอพิสูจน์ได้ว่า JR บ่งชี้ว่า EXP เป็นไดโอแฟนไทน์ เช่นเดียวกับสัมประสิทธิ์ทวินาม แฟกทอเรียล และจำนวนเฉพาะ
1959	เดวิสและพัตนัมร่วมกันศึกษาเซตไดโอแฟนไทน์แบบเอก ซ์โปเนนเชียล : เซตที่กำหนดได้ด้วยสมการไดโอแฟนไทน์ซึ่งเลขชี้กำลังบางตัวอาจไม่ทราบค่า โดยใช้รูปแบบปกติของเดวิสร่วมกับวิธีการของโรบินสัน และสมมติข้อสันนิษฐานที่ยังไม่ได้รับการพิสูจน์ในขณะนั้นว่ามีลำดับเลขคณิตที่ยาวอย่างไม่จำกัดซึ่งประกอบด้วยจำนวนเฉพาะพวกเขาพิสูจน์ได้ว่าทุกเซตที่แจงนับได้แบบเวียนซ้ำเป็นเซตไดโอแฟนไทน์แบบเอกซ์โปเนนเชียล พวกเขายังพิสูจน์เป็นผลลัพธ์เพิ่มเติมว่า JR บ่งชี้ว่าทุกเซตที่แจงนับได้แบบเวียนซ้ำเป็นเซตไดโอแฟนไทน์ ซึ่งในทางกลับกันก็บ่งชี้ว่าปัญหาที่สิบของฮิลเบิร์ตไม่สามารถแก้ไขได้
1960	โรบินสันทำให้การพิสูจน์ผลลัพธ์แบบมีเงื่อนไขสำหรับเซตไดโอแฟนไทน์เลขชี้กำลังง่ายขึ้น และทำให้เป็นอิสระจากการคาดการณ์เกี่ยวกับจำนวนเฉพาะ ดังนั้นจึงเป็นทฤษฎีบทอย่างเป็นทางการ ซึ่งทำให้สมมติฐาน JR เป็นเงื่อนไขที่เพียงพอสำหรับความไม่สามารถแก้ปัญหาข้อที่สิบของฮิลเบิร์ตได้ อย่างไรก็ตาม หลายคนสงสัยว่า JR เป็นจริงหรือไม่[ a ]
พ.ศ. 2504–2512	ในช่วงเวลานี้ เดวิสและพัตนัมพบข้อเสนอต่างๆ ที่บ่งชี้ถึง JR และโรบินสันซึ่งเคยแสดงให้เห็นแล้วว่า JR บ่งชี้ว่าเซตของจำนวนเฉพาะ เป็นเซตไดโอแฟนไทน์ ได้พิสูจน์ว่านี่เป็น เงื่อนไขแบบ "ก็ต่อเมื่อ" ยูริ มาติยาเซวิชได้ตีพิมพ์ผลงานการลดรูปบางส่วนของปัญหาที่สิบของฮิลเบิร์ต
1970	โดยอ้างอิงจากผลงานที่ตีพิมพ์ล่าสุดของNikolai Vorob'evเกี่ยวกับจำนวนฟิโบนาชชี[ 6 ] Matiyasevichพิสูจน์ว่าเซตที่เป็นจำนวนฟิโบนาชชีลำดับ ที่ nเป็นไดโอแฟนไทน์และแสดงการเติบโตแบบเลขชี้กำลัง[ 7 ]ซึ่งพิสูจน์สมมติฐาน JR ซึ่งในขณะนั้นเป็นคำถามที่ยังเปิดอยู่เป็นเวลา 20 ปี การรวม JR กับทฤษฎีบทที่ว่าเซตที่นับได้แบบเวียนซ้ำทุกเซตเป็นไดโอแฟนไทน์แบบเลขชี้กำลัง พิสูจน์ได้ว่าเซตที่นับได้แบบเวียนซ้ำเป็นไดโอแฟนไทน์ ซึ่งทำให้ปัญหาที่สิบของฮิลเบิร์ตไม่สามารถแก้ไขได้ ${\displaystyle P=\{(a,b)\mid a>0,b=F_{2a}\},}$${\displaystyle F_{n}}$

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

มีพหุนามอยู่ตัวหนึ่งซึ่งเมื่อกำหนดเซตไดโอแฟนไทน์ใดๆ แล้วจะมีจำนวนหนึ่งที่ทำให้${\displaystyle p(a,n,x_{1},\ldots ,x_{k})}$${\displaystyle S}$${\displaystyle n_{0}}$

$${\displaystyle S=\{\,a\mid \exists x_{1},\ldots ,x_{k}\,[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.}$$

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

Hilary Putnam ได้ชี้ให้เห็น^{[ 8 ]}ว่าสำหรับเซตไดโอแฟนไทน์ของจำนวนเต็มบวกใดๆ จะมีพหุนาม ${\displaystyle S}$

${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})}$

โดยที่ประกอบด้วยจำนวนบวกทั้งหมดจากค่าที่กำหนดให้กับตัวแปร ${\displaystyle S}$${\displaystyle q}$

${\displaystyle x_{0},x_{1},\ldots ,x_{n}}$

ครอบคลุมจำนวนธรรมชาติทั้งหมด สามารถมองได้ดังนี้: ถ้า

${\displaystyle p(a,y_{1},\ldots ,y_{n})=0}$

หากให้คำจำกัดความของไดโอแฟนไทน์แล้ว ก็เพียงพอที่จะตั้งค่า ${\displaystyle S}$

$${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].}$$

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

การประยุกต์ใช้อื่นๆ เกี่ยวข้องกับสิ่งที่นักตรรกศาสตร์เรียกว่าประพจน์ ซึ่งบางครั้งเรียกว่าประพจน์ประเภทโกลด์บัค [ ^{b ] สิ่ง}เหล่านี้คล้ายกับสมมติฐานของโกลด์บัค ตรงที่ระบุว่าจำนวนธรรมชาติทั้งหมดมีคุณสมบัติบางอย่างที่สามารถตรวจสอบได้ด้วยอัลกอริทึมสำหรับแต่ละจำนวน^{[ c ]}ทฤษฎีบท Matiyasevich/MRDP บ่งชี้ว่าประพจน์แต่ละข้อเทียบเท่ากับข้อความที่ยืนยันว่าสมการไดโอแฟนไทน์บางสมการไม่มีคำตอบในจำนวนธรรมชาติ^{[ d ]}ปัญหาสำคัญและมีชื่อเสียงหลายข้ออยู่ในรูปแบบนี้ โดยเฉพาะอย่างยิ่งทฤษฎีบทสุดท้ายของแฟร์มาต์สมมติฐานของรีมันน์และทฤษฎีบทสี่สีนอกจากนี้ การยืนยันว่าระบบที่เป็นทางการ บางอย่าง เช่น เลขคณิตของพีอาโน หรือZFCมีความสอดคล้องกัน สามารถแสดงเป็นประโยคได้ แนวคิดคือการทำตามเคิร์ท เกอเดลในการเข้ารหัสการพิสูจน์ด้วยจำนวนธรรมชาติในลักษณะที่ว่าคุณสมบัติของการเป็นจำนวนที่แสดงถึงการพิสูจน์นั้นสามารถตรวจสอบได้ด้วยอัลกอริทึม ${\displaystyle \Pi _{1}^{0}}$${\displaystyle \Pi _{1}^{0}}$

${\displaystyle \Pi _{1}^{0}}$ประโยคเหล่านี้มีคุณสมบัติพิเศษคือ หากประโยคเหล่านั้นเป็นเท็จ ข้อเท็จจริงนั้นจะสามารถพิสูจน์ได้ในระบบตรรกะที่เป็นทางการทั่วไปใดๆ ก็ตาม เนื่องจากความเท็จนั้นหมายถึงการมีอยู่ของตัวอย่างค้านที่สามารถตรวจสอบได้ด้วยการคำนวณทางคณิตศาสตร์อย่างง่าย ดังนั้น หากประโยคใดประโยคหนึ่งไม่สามารถพิสูจน์ได้ทั้งตัวประโยคเองและประโยคปฏิเสธในระบบใดระบบหนึ่งเหล่านี้ ประโยคนั้นจะต้องเป็นจริง ${\displaystyle \Pi _{1}^{0}}$

รูปแบบที่โดดเด่นเป็นพิเศษของทฤษฎีบทความไม่สมบูรณ์ของเกอเดลยังเป็นผลมาจากทฤษฎีบทของมาติยาเซวิช/MRDP อีกด้วย:

อนุญาต

${\displaystyle p(a,x_{1},\ldots ,x_{k})=0}$

ให้นิยามไดโอแฟนไทน์ของเซตที่ไม่สามารถคำนวณได้ ให้เป็นอัลกอริทึมที่ส่งออกลำดับของจำนวนธรรมชาติโดยที่สมการที่สอดคล้องกัน ${\displaystyle A}$${\displaystyle n}$

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0}$

ไม่มีคำตอบในจำนวนธรรมชาติ นอกจากนี้ยังมีจำนวนที่ไม่แสดงผลออกมา ในขณะที่สมการนั้นจริงๆ แล้ว ${\displaystyle n_{0}}$${\displaystyle A}$

${\displaystyle p(n_{0},x_{1},\ldots ,x_{k})=0}$

ไม่มีคำตอบในจำนวนธรรมชาติ

เพื่อให้เห็นว่าทฤษฎีบทนี้เป็นจริง ก็เพียงพอที่จะสังเกตว่า หากไม่มีจำนวนดังกล่าวเราสามารถทดสอบการเป็นสมาชิกของจำนวน นั้น ในเซตที่ไม่สามารถคำนวณได้นี้ได้โดยใช้อัลกอริทึม โดยการเรียกใช้อัลกอริทึมเพื่อดูว่าผลลัพธ์เป็น หรือไม่ ในขณะเดียวกันก็ตรวจสอบทูเปิลที่เป็นไปได้ทั้งหมดของจำนวนธรรมชาติเพื่อหาคำตอบของสมการ ${\displaystyle n_{0}}$${\displaystyle n}$${\displaystyle A}$${\displaystyle n}$${\displaystyle k}$

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0}$

และเราอาจเชื่อมโยงอัลกอริทึมกับระบบที่เป็นทางการทั่วไปใดๆ เช่นเลขคณิตของพีอาโนหรือZFCโดยให้มันสร้างผลลัพธ์ของสัจพจน์อย่างเป็นระบบ แล้วส่งออกตัวเลขเมื่อใดก็ตามที่ประโยคในรูปแบบ ${\displaystyle A}$${\displaystyle n}$

${\displaystyle \neg \exists x_{1},\ldots ,x_{k}\,[p(n,x_{1},\ldots ,x_{k})=0]}$

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

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

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

จูเลีย โรบินสันและยูริ มาติยาเซวิชแสดงให้เห็นว่าเซตไดโอแฟนไทน์ทุกเซตมีมิติไม่เกิน 13 ต่อมา มาติยาเซวิชได้ปรับปรุงวิธีการของพวกเขาเพื่อแสดงให้เห็นว่าตัวแปรที่ไม่ทราบค่า 9 ตัวก็เพียงพอแล้ว แม้ว่าผลลัพธ์นี้อาจไม่ใช่ผลลัพธ์ที่ดีที่สุดเท่าที่จะเป็นไปได้ แต่ก็ไม่มีความคืบหน้าเพิ่มเติม^{[ e ]}ดังนั้น โดยเฉพาะอย่างยิ่ง ไม่มีอัลกอริทึมสำหรับการทดสอบสมการไดโอแฟนไทน์ที่มีตัวแปรที่ไม่ทราบค่า 9 ตัวหรือน้อยกว่าเพื่อหาคำตอบในจำนวนธรรมชาติ สำหรับกรณีของคำตอบจำนวนเต็มตรรกยะ (ดังที่ฮิลเบิร์ตได้ตั้งคำถามไว้แต่เดิม) เทคนิค 4-squares แสดงให้เห็นว่าไม่มีอัลกอริทึมสำหรับสมการที่มีตัวแปรที่ไม่ทราบค่าไม่เกิน 36 ตัว แต่ซี-เว่ย ซุนแสดงให้เห็นว่าปัญหาสำหรับจำนวนเต็มนั้นไม่สามารถแก้ไขได้แม้แต่สำหรับสมการที่มีตัวแปรที่ไม่ทราบค่าไม่เกิน 11 ตัว

มาร์ติน เดวิส ศึกษาคำถามเชิงอัลกอริทึมที่เกี่ยวข้องกับจำนวนคำตอบของสมการไดโอแฟนไทน์ ปัญหาข้อที่สิบของฮิลเบิร์ตถามว่าจำนวนนั้นเป็น 0 หรือไม่ ให้และให้เป็นเซตย่อยแท้ที่ไม่ว่างของเดวิสพิสูจน์แล้วว่าไม่มีอัลกอริทึมใดที่จะทดสอบสมการไดโอแฟนไทน์ที่กำหนดให้เพื่อตรวจสอบว่าจำนวนคำตอบเป็นสมาชิกของเซต หรือไม่ดังนั้นจึงไม่มีอัลกอริทึมใดที่จะตรวจสอบว่าจำนวนคำตอบของสมการไดโอแฟนไทน์เป็นจำนวนจำกัด จำนวนคี่ กำลังสองสมบูรณ์ จำนวนเฉพาะ ฯลฯ ${\displaystyle A=\{0,1,2,3,\ldots ,\aleph _{0}\}}$${\displaystyle C}$${\displaystyle A}$${\displaystyle C}$

การพิสูจน์ทฤษฎีบท MRDP ได้รับการกำหนดรูปแบบอย่างเป็นทางการในRocq (ก่อนหน้านี้รู้จักกันในชื่อCoq ) ^{[ 9 ]}

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

มีการศึกษาค้นคว้ามากมายเกี่ยวกับปัญหาข้อที่สิบของฮิลเบิร์ตสำหรับวงแหวนของจำนวนเต็มของฟิลด์จำนวนพีชคณิต โดยอ้างอิงจากงานก่อนหน้านี้ของJan Denefและ Leonard Lipschitz และใช้ทฤษฎีฟิลด์ชั้น Harold N. Shapiro และAlexandra Shlapentokhสามารถพิสูจน์ได้ว่า:

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

Shlapentokh และ Thanases Pheidas (โดยอิสระจากกัน) ได้ผลลัพธ์เดียวกันสำหรับฟิลด์จำนวนพีชคณิตที่ยอมรับการฝังตัวเชิงซ้อนคู่หนึ่งพอดี

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

ในปี 2024 ปีเตอร์ คอยแมนส์และคาร์โล ปากาโนได้ตีพิมพ์หลักฐานที่อ้างว่าปัญหาที่ 10 ของฮิลเบิร์ตไม่สามารถตัดสินได้สำหรับวงแหวนของจำนวนเต็มทุกวงโดยใช้การจัดเรียงแบบบวก^{[ 11 ] [ 12 ]} ต่อมาทีมนักคณิตศาสตร์อีกทีมหนึ่งได้อ้างหลักฐานอีกแบบหนึ่งของผลลัพธ์เดียวกันโดยใช้วิธี การที่แตกต่างกัน^{[ 11 ] [ 13 ]}

• ปัญหาพีชคณิตมัธยมปลายของทาร์สกี้

• ฮิลเบิร์ต, เดวิด (1901) "ปัญหาคณิตศาสตร์". เอกสารสำคัญจาก Mathematik และ Physik ชุดที่ 3 (เป็นภาษาเยอรมัน) 1 : 44– 63, 213– 247.
• เดวิส, มาร์ติน ; มาติยาเซวิช, ยูริ ; โรบินสัน, จูเลีย (1976). "ปัญหาที่สิบของฮิลเบิร์ต: สมการไดโอแฟนไทน์: แง่มุมเชิงบวกของคำตอบเชิงลบ" ในเฟลิกซ์ อี. บราวเดอร์ (บรรณาธิการ). การพัฒนาทางคณิตศาสตร์ที่เกิดขึ้นจากปัญหาของฮิลเบิร์ต . รายงานการประชุมสัมมนาคณิตศาสตร์บริสุทธิ์ . เล่มที่ XXVIII.2. สมาคมคณิตศาสตร์อเมริกัน . หน้า  323–378 . ISBN 0-8218-1428-1. Zbl  0346.02026 . ตีพิมพ์ซ้ำในThe Collected Works of Julia Robinson , บรรณาธิการโดย Solomon Feferman , หน้า 269–378, American Mathematical Society 1996
• Martin Davis , "ปัญหาข้อที่สิบของฮิลเบิร์ตแก้ไม่ได้," American Mathematical Monthly , เล่มที่ 80 (1973), หน้า 233–269; พิมพ์ซ้ำเป็นภาคผนวกใน Martin Davis, Computability and Unsolvability , พิมพ์ซ้ำโดย Dover ปี 1982
• Davis, Martin ; Hersh, Reuben (1973). "ปัญหาที่ 10 ของฮิลเบิร์ต" Scientific American . 229 (5): 84– 91. Bibcode : 1973SciAm.229e..84D . doi : 10.1038/scientificamerican1173-84 .
• Jan Denef , Leonard Lipschitz, Thanases Pheidas, Jan van Geel, บรรณาธิการ, "ปัญหาที่สิบของฮิลเบิร์ต: การประชุมเชิงปฏิบัติการที่มหาวิทยาลัยเกนต์ ประเทศเบลเยียม 2–5 พฤศจิกายน 1999" Contemporary Mathematicsเล่มที่ 270(2000), American Mathematical Society
• M. Ram Murtyและ Brandon Fodden: "ปัญหาที่สิบของฮิลเบิร์ต: บทนำสู่ตรรกศาสตร์ ทฤษฎีจำนวน และความสามารถในการคำนวณ", สมาคมคณิตศาสตร์อเมริกัน, ISBN 978-1-4704-4399-3(มิถุนายน 2562)
• Shlapentokh, Alexandra (2007). ปัญหาที่สิบของฮิล เบิร์ต ชั้นไดโอแฟนไทน์และการขยายไปสู่ฟิลด์ทั่วโลกเอกสารทางคณิตศาสตร์ใหม่ เล่มที่ 7 เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ ISBN 978-0-521-83360-8. Zbl  1196.11166 .

• ปัญหาข้อที่สิบของฮิลเบิร์ต: ประวัติศาสตร์แห่งการค้นพบทางคณิตศาสตร์
• หน้าปัญหาที่สิบของฮิลเบิร์ต!
• ซุน จื้อเหว่ย (14 เมษายน 2543). "เกี่ยวกับปัญหาข้อที่สิบของฮิลเบิร์ตและหัวข้อที่เกี่ยวข้อง" (PDF) . maths.nju.edu.cn . สืบค้นเมื่อ27 กันยายน 2568 .
• ตัวอย่างภาพยนตร์เรื่อง "ปัญหาที่สิบ" ของจูเลีย โรบินสันและฮิลเบิร์ตบน YouTube