Computable and incomputable functions and search algorithms

Citation

Woodward J (2009) Computable and incomputable functions and search algorithms. In: Proceedings - 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems, ICIS 2009, volume 1. IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009. ICIS 2009, Shanghai, 20.11.2009-22.11.2009. Piscataway, NJ: IEEE, pp. 871-875. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5358045&abstractAccess=no&userType=inst

Abstract
Previous results state that there is no single universal search algorithm which outperforms other algorithms in terms of search on functions over finite domains. We consider functions with countably infinite domains, that is functions which are mappings from the set of natural numbers to the set of natural numbers. A search algorithm samples points of a given function, producing a sequence of output values. The main result of this paper is that, given two search algorithms, and a function (computable or incomputable), then we can construct a function on which the pair of search algorithms perform identically. What is more, the Kolmogorov complexity of the functions and algorithms is related. We also show that search and bias have a deep connection. With regards to search, the ease with which we find a function in a search space consisting of programs, is the same as bias, (i.e. the preference of the search space towards one function over another). We show this for finite and countable infinite sized search spaces. The law of conservation of generalization states that for every function a learning algorithm does well on, there exists a function on which it does badly. This has previously been proved for functions over finite sized domains. Here we show how this result can be extended to functions over countably infinite sized domains.