This post is a reporting of the results in Jones [1978] – Three Universal Representations of Recursively Enumerable Sets.

So, firstly, we should report Matijasevic’s result on Diophantine Equations and their solvability. There is **no** algorithm to decide whether or not a Diophantine equation has integer solutions. This result was achieved through showing that Recursively Enumerable Sets (aka enumerable sets) are Diophantine.

From this, Jones yields his first result;

*The r.e. sets , may be represented in the form:*

This is a wonderful result. This sentence is undecidable in the recursive sense, and also in a formal/axiomatic sense given by Godel in 1931. What Jones goes on to do is to re-write this formula as a pure polynomial. That is, remove all symbols and form a pure polynomial expression of enumerable sets. This result is as follows:

*The r.e. sets, may be represented in the form:*

So here are two prenex normal form formulas, with the same quantifier prefix, that can actually have reduced quantification! This is an amazing result, and the third universal statement, a system of 36 equations that is equivalent to any Diophantine equation, with any number or unknowns or of any degree, yet this Universal Formula is fixed. This paper is a fabulous result, and worth hunting down.

In analysis of the above statements, you can see how the rules are expressed. Put simply:

Disjunction:

Conjunction:

Conditional:

Also, in the translation above, Jones adds the first clause to the formula to remove the index from the . This means that the quantifiers are straightforward, and the sentence is a true translation of the logical statement. It is worth noting that such methods have problems with things like , but that this is not important in the current setup. See the work of Bovykin and de Smet on translations and reductions of logical statements into polynomials for more information.

Hope that was enjoyable!

### Like this:

Like Loading...

*Related*