On the expressive power of program schemes with sets
Alexei P. Stolboushkin · 2002
The author considers flow diagrams with sets, which is the class of program schemes equipped with finite sets of different levels, so that FDSet/sub 1/ is such a class equipped with finite sets, FDSet/sub 2/ is such a class equipped with finite sets and finite sets of finite sets, etc. He proves FDSet/sub 1/ is semi-universal. In particular, in infinite structures FDSet/sub 1/ is able to define every (generalized) computable function. For finite structures, the halting problem for FDSet/sub 1/, is decidable, and it is proved that DL(FDSet/sub 1/) exactly corresponds to the LINEARSPACE complexity class.>