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.

Text
Bouke_Kuijer_WM_2010.pdf  Published Version Download (385kB)  Preview 
Abstract
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 nonexistence 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 
URI:  https://fse.studenttheses.ub.rug.nl/id/eprint/9050 
Actions (login required)
View Item 