摘要：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.
Loading...
