Matijasevic’s Theorem: Diophantine descriptions of recursively enumerable sets

Groen, S.R. (2017) Matijasevic’s Theorem: Diophantine descriptions of recursively enumerable sets. Bachelor's Thesis, Mathematics.

Preview	Text BSc_Math_2017_Groen_SR.pdf - Published Version Download (675kB) | Preview
	Text toestemming.pdf - Other Restricted to Backend only Download (79kB)

Abstract

In 1970, Yuri Matijasevic finished the proof that all recursively enumerable sets are Diophantine, rendering Hilbert's tenth problem unsolvable. He did so by showing that exponential Diophantine sets are Diophantine, which complemented earlier work done by Martin Davis, Hilary Putnam and Julia Robinson. In this thesis, we analyze, explore and apply this result. We reconstruct a known way to create a Diophantine description of exponentiation: using the unit group of the number ring with the square root of some non-square number. This provides a mechanism with which we can create a Diophantine description of any recursively enumerable set. We apply this to find Diophantine descriptions of some specific sets of integers. We also study the complexity of such Diophantine descriptions. Furthermore, we try to create a new method of creating a Diophantine description of exponentiation, using the cube root instead of the square root, which results in a structure similar to that of the other unit group. It turns out that such a similar method does not work, as the desired divisibility sequences don't exist.

Item Type:	Thesis (Bachelor's Thesis)
Degree programme:	Mathematics
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	15 Feb 2018 08:28
Last Modified:	15 Feb 2018 08:28
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/15275

Actions (login required)

View Item