Tata Institute of Fundamental Research

Diophantine Sets and Computability

STCS Student Seminar
Speaker: Prabhat Kumar Jha
Organiser: Anirban Bhattacharjee
Date: Friday, 9 Oct 2020, 17:15 to 18:15
Venue:

(Scan to add to calendar)
Abstract:  Diophantine sets are defined using Diophantine equations. These sets are important and ubiquitous in number theory.
Recursively enumerable sets are defined using models of computation (Lambda calculus, Turing machines, etc). These sets are studied in computability/recursion theory.
In this talk, we will see an equivalance between these two kind of sets emerging from two different theories. This result is due to Matiyasevich and is known as MRDP theorem.
There are many interesting corollaries of this result including Godel's incompleteness theorem and undecidability of Diophantine equations.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09.