Séminaire Logique mathématique ICJ

Emmanuel Rauzy "Computable analysis on the space of marked groups"

Europe/Paris
112

112

Description

Computable analysis on the space of marked groups

I will present results related to the study of decision problems for finitely generated groups described by word problem algorithms.

The main tool to tackle this problem is the topology of the space of marked groups.

We will see that the space of marked groups is a recursive metric space that is computably complete. These facts allows us to use a lemma due to Markov Jr. to obtain undecidability results.

However, we will see that the space of marked groups, while being a Polish space, is not a computable Polish space. Because of this, many of the most important results of computable analysis cannot be applied to it. In particular, results of Ceitin and Moschovakis that assert that computable functions defined on computably Polish spaces are automatically continuous cannot be applied to the space of marked groups.