BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Gihanee Senadheera (Southern Illinois University) DTSTART:20210930T180000Z DTEND:20210930T190000Z DTSTAMP:20260423T035749Z UID:OLS/78 DESCRIPTION:Title: Eff ective Concept Classes of PACi/PAC Incomparable Degrees and Jump Structure \nby Gihanee Senadheera (Southern Illinois University) as part of Onli ne logic seminar\n\n\nAbstract\nThe Probably Approximately Correct (PAC) l earning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size a nd computation time. This reducibility in PAC learning resembles the reduc ibility in Turing computability. In 1957 Friedberg and Muchnik independent ly solved the Post problem by constructing computably enumerable sets $A$ and $B$ of incomparable degrees using the priority construction method. We adapt this idea to PACi/PAC reducibilities and construct two the effectiv e concept classes $C_0$ and $C_1$ such that $C_0$ is not reducible to $C_1 $ and vice versa. When considering PAC reducibility it was necessary to wo rk on the size of an effective concept class\, thus we use Kolmogorov comp lexity to obtain the size. Analogous to Turing jump\, we give a jump struc ture on effective concept classes. As the future work\, we begin to explor e an embedding of structures from PAC degrees to 1-1 degrees or Turing deg rees.\n LOCATION:https://researchseminars.org/talk/OLS/78/ END:VEVENT END:VCALENDAR