BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Benoit Monin (LACL/Créteil University) DTSTART:20200804T140000Z DTEND:20200804T150000Z DTSTAMP:20260423T004822Z UID:CTA/16 DESCRIPTION:Title: Gen ericity and randomness with ITTMs\nby Benoit Monin (LACL/Créteil Univ ersity) as part of Computability theory and applications\n\n\nAbstract\nWe will talk about constructibility through the study of Infinite-Time Turin g machines. The study of Infinite-Time Turing machines\, ITTMs for short\, goes back to a paper by Hamkins and Lewis. Informally these machines work like regular Turing machines\, with in addition that the time of computat ion can be any ordinal. Special rules are then defined to specify what hap pens at a limit step of computation. \n\nThis simple computational model y ields several new non-trivial classes of objects\, the first one being the class of objects which are computable using some ITTM. These classes have been later well understood and characterized by Welch. ITTMs are not the first attempt of extending computability notions. This was done previously for instance with alpha-recursion theory\, an extension of recursion theo ry to Sigma_1-definability of subsets of ordinals\, within initial segment s of the Godel constructible hierarchy. Even though alpha-recursion theory is defined in a rather abstract way\, the specialists have a good intuiti on of what ``compute'' means in this setting\, and this intuition relies o n the rough idea of ``some'' informal machine carrying computation times t hrough the ordinal. ITTMs appeared all the more interesting\, as they cons ist of a precise machine model that corresponds to part of alpha-recursion theory.\n\nRecently Carl and Schlicht used the ITTM model to extend algor ithmic randomness and effective genericity notions in this setting. Generi city and randomness are two different approaches to study typical objects\ , that is\, objects having ``all the typical properties'' for some notion of typicality. For randomness\, a property is typical if the class of real s sharing it is of measure 1\, whereas for genericity\, a property is typi cal if the class of reals sharing it is co-meager.\n\nWe will present a ge neral framework to study randomness and genericity within Godel's construc tible hierarchy. Using this framework\, we will present various theorems a bout randomness and genericity with respect to ITTMs. We will then end wit h a few exciting open questions for which we believe Beller Jensen and Wel ch's forcing technique of their book ``coding the universe'' should be use ful.\n LOCATION:https://researchseminars.org/talk/CTA/16/ END:VEVENT END:VCALENDAR