On Finite-time Computability Preserving Conversions

Hideki Tsuiki (Kyoto University, Japan)

Shuji Yamada (Kyoto Sangyo University, Japan)

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: computable analysis, constant-time computable functions, domain theory, finite-time computable functions, sliding block functions

Categories: F.1.m, F.4.3, G.2.m