Javascript must be enabled for the correct page display

Creating a diophantine description of a r.e. set and on the complexity of such a description

Kuijer, L.B. (2010) Creating a diophantine description of a r.e. set and on the complexity of such a description. Master's Thesis / Essay, Mathematics.

Bouke_Kuijer_WM_2010.pdf - Published Version

Download (385kB) | Preview


A very old class of problems in mathematics is the solving of Diophantine equations. Essentially a Diophantine equation is a polynomial equation that should be solved in the natural numbers. While solutions to specific Diophantine equations have of course been found, a general method to solve any given Diophantine equation has not. In 1900 Hilbert considered this a suficiently important problem to include the finding of such a method in his famous list of at that time unsolved mathematical problems. In 1970 Matijasevic [6] showed that such a method does not exist. I will give a proof of the non-existence of such an algorithm that resembles proofs that were developed later. The main idea used in section 3 strongly resembles the method used in 1975 by Matijasevic and Robinson [8], although many details are handled in a different way here. Section 4 uses some of the same methods as presented in 1984 by Jones and Matijasevic [5], but they are applied to a different formalization here. After giving the proof I will briefly discuss some complexity measures that could have applications when considering the solvability of diophantine equations in a fixed number of unknowns.

Item Type: Thesis (Master's Thesis / Essay)
Degree programme: Mathematics
Thesis type: Master's Thesis / Essay
Language: English
Date Deposited: 15 Feb 2018 07:30
Last Modified: 15 Feb 2018 07:30

Actions (login required)

View Item View Item