Research on "Formal Methods in Computing"

Total functionals and well-founded strategies

ABSTRACT. In existing game models, total functionals have no simple characterization, neither in term of game strategies, nor in terms of the total set-theoretic functionals they define. We show that the situation changes if we extend the usual notion of game by allowing infinite plays. Total functionals are now exactly those having a tree strategy in which all branches end in a last move, winning for the strategy. Total functionals now define (via an extensional collapse) all set theretical functionals. Our model is conrete: we use infinite computations only to have a nice characterization of totality. A computation may be infinite only when the input is a discontinuous functional; in practice never.

• [pdf] , ( © Springer-Verlag )

BIBTEX.

@conference{BerardideLiguoro:TLCA-99,
   author    = {Stefano Berardi, Ugo {de' Liguoro}},
   title     = {{Total functionals and well-founded strategies}},
   booktitle = {{TLCA'99}},
   year      = {1999},
   publisher = {Springer},
   pages     = {54-68},
   series    = {LNCS 1581}
}