dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Rin, B.G. | |
dc.contributor.author | Beelen, K.I. | |
dc.date.accessioned | 2021-05-05T18:00:08Z | |
dc.date.available | 2021-05-05T18:00:08Z | |
dc.date.issued | 2021 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/39372 | |
dc.description.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. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 423589 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en_US | |
dc.title | A Transfinite Complete One-Way Function | |
dc.type.content | Bachelor Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | Turing machine, infinite time Turing machine, ordinal Turing machine, transfinite computation, transfinite probability, one-way function, tiling problem | |
dc.subject.courseuu | Kunstmatige Intelligentie | |