19.dets, 14:00 ICT-638 "Sequential interactive behaviour of recursive program schemes"
Tarkvarateaduse instituudi seminaril teisipäeval, 19.12.2017 esineb Pierre-Louis Curien (IRIF, CNRS & Université Paris Diderot (Paris 7)) teemal "Sequential interactive behaviour of recursive program schemes".
Seminar toimub ruumis ICT-638.
Sisukokkuvõte: We analyse primitive recursive program schemes (PRPS) under the interactive angle offered by Berry and Curien's theory of sequential algorithms, and we revisit in this framework a theorem of Loïc Colson called "ultimate obstinacy theorem". This theorem says that the execution of any PRPS eventually calls the same argument over and over (and no other). This excludes for example the natural algorithm of comparison of two natural numbers by decrementing them alternately. The general slogan is that we are not only interested in what is computed (the input-output relation of the program), but in how the computation is performed. This kind of fine study is not accessible in models of computation in the style of Turing machines, but is possible in models based on lambda-calculus, or recursion à la Kleene.