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

Corresponding author: Hideki Tsuiki ( tsuiki@i.h.kyoto-u.ac.jp )

© Hideki Tsuiki, Shuji Yamada.
This article is freely available under the J.UCS Open Content License.
Citation: Tsuiki H, Yamada S (2009) On Finite-time Computability Preserving Conversions. JUCS - Journal of Universal Computer Science 15(6): 1365-1380. https://doi.org/10.3217/jucs-015-06-1365
Open Access
Abstract
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.
Keywords
finite-time computable functions, constant-time computable functions, sliding block functions, computable analysis, domain theory