Diophantische Mengen

Satz (Davis, Matiyasevich, Putnam, Robinson; $ \approx$ 1970)

M diophantisch $ \iff$ M ist rekursiv aufzählbar
http://logic.pdmi.ras.ru/~yumat/H10Pbook/


positive Werte dieses Polynoms = Menge der Primzahlen

(k + 2)(1–(wz + h + jq)2–((gk + 2g + k + 1)(h + j) + hz)2–(2n + p + q + ze)2–(16(k + 1)3(k + 2)(n + 1)2 +1–f2)2–(e3(e + 2)(a + 1)2 +1–o2)2–((a2–1)y2 +1–x2)2–(16r2y4(a2–1) + 1–u2)2–(((a + u2(u2a))2–1)(n + 4dy)2 +1–(x + cu)2)2–(n + l + vy)2–((a2–1)l2 +1–m2)2–(ai + k + 1–li)2–(p + l (an–1) + b(2an + 2an2–2n–2)–m)2–(q + y(ap–1) + s(2ap + 2ap2–2p–2)–x)2–(z + pl (ap) + t(2app2–1)–pm)2)

(challenge: ...find some) http://primes.utm.edu/glossary/xpage/MatijasevicPoly.html



2014-07-06