The Church Problem for Countable Ordinals
Alexander Rabinovich · 2012
Abstract. A fundamental theorem of Büchi and Landweber shows that the Church synthesis problem is computable. Büchi and Landweber reduced the Church Problem to problems about ω-games and used the determinacy of such games as one of the main tools to show its computability. We consider a natural generalization of the Church problem to countable ordinals and investigate games of arbitrary countable length. We prove that determinacy and decidability parts of the Büchi and Landweber theorem hold for all countable ordinals and that its full extension holds for all ordinals < ω ω. 1.