Presentationer av examensarbete C i matematik
- Datum: –17.00
- Plats: Ångströmlaboratoriet 4006
- Arrangör: Matematiska institutionen
- Kontaktperson: Vera Koponen
13:15: Oliver Hjorth
14:15: Anton Hallberg, Post's problem in recursion theory and its solution,
Abstract: The notion of Turing reducibility is a way of comparing the computational complexity of sets of natural numbers. It induces a preorder on the sets of natural numbers. The equivalence classes of the preorder are called Turing degrees and on these Turing reducibility induces a partial order. There are two natural recursively enumerable Turing degrees: the Turing degree of any recursive set and the Turing degree of the Halting problem. Emile Post asked (in 1944) whether there where any other recursively enumerable Turing degrees. In 1956-1957, Muchnik (in the USSR) and Friedberg (in the USA) independently proved that there are other recursively enumerable Turing degrees than the obvious ones, in fact there are infinitely many.
15:15: Elisa Pitkälä, Kvadratiska rester.
16:15: Sofie Eiderfors, Representation av tal som summor av kvadrater.