JUCS - Journal of Universal Computer Science 15(6): 1365-1380, doi: 10.3217/jucs-015-06-1365
On Finite-time Computability Preserving Conversions
expand article infoHideki Tsuiki, Shuji Yamada§
‡ Kyoto University, Kyoto, Japan§ Kyoto Sangyo University, Kyoto, Japan
Open Access
A finite-time computable function is a partial function from ∑ω to ∑ ω whose value is constructed by concatenating a finite list with a suffix of the argument. A finite-time computability preserving conversion α : X → Y for X, Y ⊂ ∑ω is a bijection which preserves finite-time computability. We show that all the finite-time computability preserving conversions with the domain ∑ω are extended sliding block functions.
finite-time computable functions, constant-time computable functions, sliding block functions, computable analysis, domain theory