Computability of Optimizers
Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Extending and Automating Basic Probability Theory with Propositional Computability Logic
Classical probability theory is formulated using sets. In this paper, we extend classical probability theory with propositional computability logic. Unlike other formalisms, computability logic is built on the notion of …
On the Computability of Solomonoff Induction and Knowledge-Seeking
Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the arithmetical hierarchy. We also …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)How To Solve Moral Conundrums with Computability Theory
Various moral conundrums plague population ethics: the Non-Identity Problem, the Procreation Asymmetry, the Repugnant Conclusion, and more. I argue that the aforementioned moral conundrums have a structure neatly account…
EthicsPhilosophyImplementing Agent-Based Systems via Computability Logic CL2
Computability logic(CoL) is a powerful computational model. In this paper, we show that CoL naturally supports multi-agent programming models where resources (coffee for example) are involved. To be specific, we discuss …
Is Complexity Important for Philosophy of Mind?
Computational complexity has often been ignored in philosophy of mind, in philosophical artificial intelligence studies. The purpose of this paper is threefold. First and foremost, to show the importance of complexity ra…
Philosophy