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.��
Let� D1 �=�� { p | p is a polynomial over x with an
integral root� }� �
Example_1: ����3x2
��+ 2x� - 56�
= 0� is in the set D1.� This polynomial belongs to D1, because� x = 4
Example_2: ��6x2
+ 13x �+ 6 =
0��� does�
NOT� belong 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. 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 *� Cmax
/C1 )
Where k is the number of terms in the
Polynomial,���� Cmax� is the coefficient of the
largest absolute value,� and� C1 �is the coefficient of the highest order
term.�������
������
+�� �������
the roots of the Polynomial must be
between: ���������(3
*� 56/3) =� +-56
This polynomial belongs to D1,
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
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/