Computational Complexity On Compact Sets In Cantor Space

Computational complexity is a branch of theory of computation science. The majority of the numerous investigations concern countable structures. The increasing demand for more reliable computation in uncountable structures, such as real space, various models have been proposed. In this paper, we shall use a turing machine based model, Type-2Turing Machine.In TTE, computable functions on finite and infinite strings of symbols are defined explicitly by Type-2machines, and then finite and infinite strings are used as "names" of other objects such as real numbers, closed subsets of Euclidean space or continuous real functions. In addition to time complexity, which counts the number of Turing steps of the machine as a function of the input and of the output precision, we introduce lookahead of machines measuring the number of input symbols for producing an output of given length. We introduce the computational complexity in Cantor space, real space and computable metric space. Further more, we discuss the computational complexity on compact set in Cantor space.