Diophantine flavour of Kolmogorov complexity
by
Yuri Matiyasevich
Steklov Institute of Mathematics at St.Petersburg

The DPRM-theorem can serve as a bridge between Theoretical Computer Science and Number Theory. As an example we can consider the real number \Omega introduced by Gregory Chaitin. This number can be interpreted as the probability that a randomly selected Turing machine stops. The number \Omega is of great interest because its binary digits are quite chaotic (in some exact technical sense).

With DPRM-theorem we can interpret \Omega as the probability that a randomly selected Diophantine equation has a solution. This description of \Omega involves infinitely many Diophantine equations. Gregory Chaitin [1975] gave also another definition of this number by constructing single particular exponential Diophantine equation G(k, z₁, ..., z_m)=0 such that the k-th binary digit of \Omega is equal to 1 iff the equation has infinitely many solutions in z₁, ..., z_m.

Recently, Toby Ord and Tien D. Kieu [2003] constructed particular exponential Diophantine equation T(k, z₁, ..., z_m)=0 such that for every k this equation has finitely many solutions in z₁, ..., z_m and the number of solutions is odd iff the k-th digit of \Omega is equal to 1.

The author was able to generalize this result in the following way.

Theorem. Let \C be any infinite decidable set with infinite complement. Then we can construct an exponential Diophantine equation Y(k, z₁, ..., z_m)=0 such that for every k the equation has finitely many solutions in z₁, ..., z_m and the number of solutions of the equation for given value of k belongs to the set \C iff the k-th digit of \Omega is equal to 1.

Date received: March 14, 2004

Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cani-11.