From: Page 156 of Sipser, M.(2010) Introduction to the Theory of Computation, (2nd Edition) [ or Page 184 of Sipser, M.(2013) Introduction to the Theory of Computation, (3rd Edition)]

**Integral root of single variable
Polynomials**:

Polynomial
equations with one variable, x, can be checked if the
value of x is an integer.

Let D_{1}_{ } = { p | p is a polynomial over x with an
integral root }

Example_1: 3x^{2
} + 2x - 56
= 0 is in the set D_{1}. This polynomial belongs to D_{1}, because x = 4

Example_2: 6x^{2}
+ 13x + 6 =
0 does
**NOT** belong to
D_{1 } ( x = -1.5 (or
x= -2/3 = -.666) )

(13.5 -
19.5 +6 = 0 with x= **-**1.5 ) [Factor
example2 as (3x
+2 )(2x +3) = 0 ]

The set D_{1 } is decidable. “Here is a TM, M_{1}, that
recognizes D_{1: }

M_{1 } = “The input is a polynomial over the variable x.

1. Evaluate p with x set successively to the values 0, 1, -1, 2, -2, 3, -3,
. . . .

If at any point the polynomial
evaluates to 0, *accept*”

__+__

(k * C_{max}_{
}/C_{1 })

Where k is the number of terms in the
Polynomial,_{ }C_{max}_{ }is the coefficient of the
largest absolute value, and C_{1 } is the coefficient of the highest order
term.

__+__ ^{2 } + 2x
- 56 = 0,

the roots of the Polynomial must be
between: (3
* 56/3) = +-56

This polynomial belongs to D_{1},
because x = 4

__For multivariable
Polynomials,__

*Let D*_{ }* = { p
| p is a polynomial with integral roots
} is **undecidable**; that is, it may run for ever on some
input. *

This was the
10^{th} problem on Hilbert’s list?

In 1900, in recognition of their depth, David
Hilbert proposed the solvability of all Diophantine problems as the tenth of his celebrated problems. In 1970, a
novel result in mathematical logic known as Matiyasevich's theorem settled
the problem negatively: in general, Diophantine problems are unsolvable.

S9:
Write a web-based program for demonstrating integral root single variable
polynomials. For extra credits, demonstrate integral root two variable polynomials in addition to single variable polynomials. To get started see:

http://www.asethome.org/mathfoundations/decidability/