From:Page 156 of Sipser, M.�� (2010) Introduction to the Theory of Computation, (2nd Edition)

Integral root of single variable Polynomials:

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

LetD1 =�� { p | p is a polynomial over x with an integral root}

Example_1: ����3x2 ��+ 2x- 56= 0is in the set D1.This polynomial belongs to D1, becausex = 4

Example_2: 6x2 + 13x + 6 = 0��� doesNOTbelong to�� D1 ��( 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 D1 is decidable. �Here is a TM,M1, that recognizes D1:

M1 = �The input is a polynomial over the variable x.

1.     Evaluatep with x set successively to the values 0, 1, -1, 2,��� -2, 3, -3,. . . .

If at any point the polynomial evaluates to 0, accept

������ +�� �������

The algorithm terminates, because the roots of such a polynomial must be between the values:

��������(k *Cmax /C1 )

Where k is the number of terms in the Polynomial,���� Cmaxis the coefficient of the largest absolute value,andC1 is the coefficient of the highest order term.�������

������ +�� �������

For example_1,�� 3x2 + 2x- 56= 0,

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

This polynomial belongs to D1, becausex = 4

 

For multivariable Polynomials,

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

This was the 10th 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/