Paper Info
Title
Effective Fixed Point Theorem over a Non-computably Separable Metric Space
Abstract
This paper shows effective fixed point theorems for computable contractions. Effective fixed point theorem for computable contractions over a computable metric space is easily shown. A function over a computable metric space is represented by a Type-1 function, and the fixed point of a contraction is given by iteration of such Type-1 function. If the contraction is computable, then its fixed point is also computable. If the support space is not computably separable, the method above is not available. The function space of an interval into real numbers is not computably separable with polynomial time computability. This paper show the fixed point theorem for such non-computably separable spaces. This theorem is proved with iteration of Type-2 functionals. As an example of that, this paper shows that Takagi function is a polynomial time computable function.
Year
DOI
Venue
2000
10.1007/3-540-45335-0_18
CCA
Keywords
Field
DocType
function space,takagi function,fixed point,effective fixed point theorem,computable metric space,polynomial time computable function,computable contraction,type-1 function,computably separable,non-computably separable metric space,fixed point theorem,polynomial time,metric space
Discrete mathematics,Fixed-point property,Least fixed point,Fixed point,Gap theorem,Computable number,Computable function,Mathematics,Fixed-point theorem,Computable analysis
Conference
ISBN
Citations 
PageRank 
3-540-42197-1
1
0.39
References 
Authors
3
1
Name
Order
Citations
PageRank
Izumi Takeuti1164.73