E-Locus - Institutional Repository of the University of Crete

Home Collections School/Department School of Sciences and Engineering Department of Mathematics and Applied Mathematics Post-graduate theses

Post-graduate theses

Current Record: 1 of 124

[Add to Basket]

Identifier

000459872

Title

Undecidability in number theory Hilbert's tenth problem and extensios of it

Alternative Title

Αναποκρισιμότητα στη θεωρία αριθμών. Δέκατο πρόβλημα του Hilbert και επεκτάσεις του

Author

Καλλέργης, Νικόλαος

Thesis advisor

Σκλήνος, Ρίζος

Reviewer

Κουβιδάκης, Αλέξανδρος
Γαρεφαλάκης, Θεόδουλος

Abstract

We are going to examine the negative answer to Hilbert’s tenth problem, i.e. the problem of finding an algorithm which, given an arbitrary Diophantine equation with integer coefficients, is able to decide if the equation has integer solutions. The non-existence of such an algorithm will be obtained by combining the original proof of Yuri Matijasevic, Hilary Putnam, Julia Robinson and Martin Davis in 1970, along with Alan Turing’s invention, the Turing machine. First we will define formally what a Turing machine is and how it operates. Then we will prove that the Halting problem is undecidable with the aid of the universal Turing machine and then the negative answer to Hilbert’s Diophantine problem will be obtained with the aid of the Halting problem. In Chapter 3, two extensions of Hilbert’s problem will be examined, one in which the solutions are sought in the polynomial ring R[T], where R is an integral domain of characteristic zero that contains Z, with the coefficients being elements of Z[T]. The other extension will be for the ring of power series F[[t]] where F is an integral domain of characteristic greater than zero with a parameter t.

Language

English

Subject

Turing machine

Μηχανές turing

Issue date

2024-03-22

Collection

School/Department--School of Sciences and Engineering--Department of Mathematics and Applied Mathematics--Post-graduate theses

Type of Work--Post-graduate theses

Permanent Link

https://elocus.lib.uoc.gr//dlib/1/c/f/metadata-dlib-1698394459-670128-30382.tkl