Hilbertov 10. problem

master's thesis

• Title (english): Hilbert's 10th problem
• Author: Karlo Murtezani
• Mentor: Filip Najman (mentor)
• Committee member: Filip Najman (predsjednik povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Committee member: Vanja Wagner (član povjerenstva)
• Committee member: Ana Prlić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-09-23, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

David Hilbert objavio je 23 problema koji su doprinijeli razvoju matematike u 20. stoljeću. U Hilbertovom desetom problemu cilj je bio pronaći proces koji u konačnom broju operacija može odrediti ima li bilo koja jednadžba cjelobrojno rješenje. Yuri Matijasevič 1970. godine dokazao je posljednju tvrdnju koja je nedostajala da bi se pokazalo da takav proces, koji danas promatramo kao algoritam, ipak ne postoji. Rad sadrži dokaz nerješivosti Desetog problema. Na početku smo istaknuli i objasnili pojmove iz teorije izračunljivosti te uveli pojam diofantskog skupa za koji želimo dokazati da je ekvivalentan poluodlučivom skupu iz teorije izračunljivosti. Diofantske jednadžbe, odnosno jednadžbe čiji su koeficijenti i rješenja cjelobrojni, definiraju diofantske skupove pa kad bismo dokazali da nisu odlučivi, mogli bismo zaključiti da Hilbertov deseti problem nema rješenje. Dalje smo dokazali da su eksponencijalne funkcije diofantske koristeći Fibonaccijeve nizove, što je predstavljalo prepreku pri dokazu navedene ekvivalencije. Samu ekvivalenciju dokazali smo uvođenjem univerzalne diofantske jednadžbe i Turingovih strojeva. Prije samog dokaza uveli smo vrste kodiranja poput Cantorovog te Gödelovog te diofantske relacije.

Abstract (english)

David Hilbert published twenty-three problems that contributed to the development of mathematics in the 20th century. Hilbert’s tenth problem asked to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. In 1970, Yuri Matijasevich finally proved the missing link in decades-long proof research to show that such a process, today regarded as an algorithm, does not exist. This work contains proof of unsolvability to the Tenth problem. In the beginning, we indicate and clarify the basic notions in the theory of computability. We introduce the diophantine set for which we want to demonstrate the equivalence to the semidecidable set established in the theory of computability. Diophantine equations, i.e., equations composed with integer coefficients and solutions, define diophantine sets. Proving that the diophantine sets are also semi-decidable implies the unsolvability of Hilbert’s tenth problem. Furthermore, we also show that the exponential functions are diophantine using Fibonacci’s sequences, which was the last obstacle of the mentioned equivalence. Introducing the universal diophantine equation, as well as the Turing machines makes it possible to conclude the equivalence. For the proof, we also introduce different types of coding, e.g., Cantor’s and Gödel’s coding, and necessary diophantine relations.

• Keywords: Hilbert; David; Hilbertov deseti problem; teorija izračunljivosti; diofantski skup; Fibonaccijevi nizovi; Turingovi strojevi
• Keywords (english): Hilbert; David; Hilbert’s tenth problem; theory of computability; diophantine set; Fibonacci’s sequences; Turing machines
• Language: croatian
• URN:NBN: urn:nbn:hr:217:718893
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-11-02 13:02:35