Simulation of simultaneous safe recursion over an arbitrary structure |
| |
Authors: | Olga Xirotiri |
| |
Affiliation: | Technological Educational Institute of Crete, Sector of Mathematics, Stavromenos, Heraklion 71500, Crete, Greece |
| |
Abstract: | In O. Bournez, F. Cucker, P.J. de Naurois, J.Y. Marion, Computability over an arbitrary structure. Sequential and parallel polynomial time, in: Lecture Notes in Computer Science, vol. 2620, Springer, Berlin, 2003, pp. 185-199] the class of safe recursive functions over an arbitrary structure is defined. A question of simulation of the simultaneous safe recursion by single safe recursion was set. We prove that this simulation is feasible using bounded coding and decoding functions. |
| |
Keywords: | Safe recursion BSS-machines Projective Turing machines Theory of computation Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|