Genericity and randomness with ITTMs

Benoit Monin (LACL/Créteil University)

04-Aug-2020, 14:00-15:00 (4 years ago)

Abstract: We will talk about constructibility through the study of Infinite-Time Turing 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 computation can be any ordinal. Special rules are then defined to specify what happens at a limit step of computation.

This simple computational model yields 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 theory to Sigma_1-definability of subsets of ordinals, within initial segments of the Godel constructible hierarchy. Even though alpha-recursion theory is defined in a rather abstract way, the specialists have a good intuition of what ``compute'' means in this setting, and this intuition relies on the rough idea of ``some'' informal machine carrying computation times through the ordinal. ITTMs appeared all the more interesting, as they consist of a precise machine model that corresponds to part of alpha-recursion theory.

Recently Carl and Schlicht used the ITTM model to extend algorithmic randomness and effective genericity notions in this setting. Genericity 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 reals sharing it is of measure 1, whereas for genericity, a property is typical if the class of reals sharing it is co-meager.

We will present a general framework to study randomness and genericity within Godel's constructible hierarchy. Using this framework, we will present various theorems about randomness and genericity with respect to ITTMs. We will then end with a few exciting open questions for which we believe Beller Jensen and Welch's forcing technique of their book ``coding the universe'' should be useful.

logic

Audience: researchers in the topic


Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.

Organizers: Damir Dzhafarov*, Vasco Brattka*, Ekaterina Fokina*, Ludovic Patey*, Takayuki Kihara, Noam Greenberg, Arno Pauly, Linda Brown Westrick
*contact for this listing

Export talk to