Hilbert's 10th problem

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.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