From:� Page 156 of Sipser,
M.�� (2010) Introduction to the Theory of
Computation, (2^{nd} 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/