The Hilbert's-tenth-problem operator

Abstract: For a ring

R

, Hilbert's Tenth Problem

H T P (R)

is the set of polynomial equations over

R

, in several variables, with solutions in

R

. We view

H T P

as an operator, mapping each set

W

of prime numbers to

H T P (m a t h b b Z [W^{- 1}])

, which is naturally viewed as a set of polynomials in

m a t h b b Z [X_{1}, X_{2}, l d o t s]

. For

W = e m p t y s e t

, it is a famous result of Matiyasevich, Davis, Putnam, and Robinson that the jump

e m p t y s e t!^{'}

is Turing-equivalent to

H T P (m a t h b b Z)

. More generally,

H T P (m a t h b b Z [W^{- 1}])

is always Turing-reducible to

W^{'}

, but not necessarily equivalent. We show here that the situation with

W = e m p t y s e t

is anomalous: for almost all

W

, the jump

W^{'}

is not diophantine in

m a t h b b Z [W^{- 1}]

. We also show that the

H T P

operator does not preserve Turing equivalence: even for complementary sets

U

and

o v e r l i n e U

,

H T P (m a t h b b Z [U^{- 1}])

and

H T P (m a t h b b Z [o v e r l i n e U^{- 1}])

can differ by a full jump. Strikingly, reversals are also possible, with

V <_{T} W

but

H T P (m a t h b b Z [W^{- 1}]) <_{T} H T P (m a t h b b Z [V^{- 1}])

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The Hilbert's-tenth-problem operator