Sabrina Ouazzani

Laboratoire d’Algorithmique, Complexité et Logique, Paris-Est Creteil University

A brief story of gaps in the infinite time Turing machines

Logic and Set Theory Seminar

9th May 2017, 3:00 pm – 4:00 pm
Howard House, 4th Floor Seminar Room

I will present a part of my PhD thesis entitled "From algorithmics to logics through infinite time computation" in which I have studied the infinite time Turing machines model of computation from a computer scientist's point of view. In particular I focused on the structure of gaps in the clockable ordinals, that is to say, ordinal times at which no infinite time program halts.

So in this talk I will present infinite time Turing machines (ITTM), from the original definition of the model to some new infinite time algorithms. These algorithmic techniques will allow to highlight some properties of the ITTM-computable ordinals and we will see that they bring some information about the structure of gaps.

Comments are closed.