A Transfinite Complete One-Way Function

Abstract

Infinite time Turing machines and ordinal Turing machines are used to perform transfinite computational tasks. In order to further explore the capabilities of these models, this research looks into one-way functions and the possibility to generalize them to work in a transfinitary context. One of the greatest problems in (finitary) computer science is determining whether these functions exist or not. Crucially, it bears mentioning that the notion of one-way function is probabilistic in nature. In 2003, Levin presented a complete one-way function—a function guaranteed to be one-way if any one-way functions exist—based on the tiling problem. His findings were further developed in research by Kozhevnikov and Nikolenko in 2009. Following their research, we define a notion of transfinite one-way function, for any suitable generalized system of probability. Such a notion has not been defined before, and the present paper provides the groundwork needed to do so. To this end, we consider one possible candidate example of a generalized system of probability sufficient to ground the notion of transfinite one-way function—namely, Benci’s theory of non-Archimedean probability—together with the theory of surreal numbers. Our main result proves that every ordinal polynomial-time computation on an ordinal Turing machine can be simulated by a transfinite tiling problem, and that transfinite tiling is therefore a transfinite complete one-way function.