Computability of optimizers for AI and data science

Artificial Intelligence (AI) and Data Science stand as pivotal innovations that revolutionize methods and processes across a multitude of industries. In unison, they facilitate the management, storage, transmission, and analysis of vast data volumes. A significant portion of these challenges are articulated as optimization problems. The potency of AI and Data Science is deeply rooted in the successful resolution of these optimization problems, which are prevalent in areas such as machine learning model fine-tuning, operational research, and logistics. However, it is crucial to acknowledge that solutions to these optimization problems do not always come with guarantees. This does not necessarily imply that research is lacking in this direction. Instead, it is often a manifestation of the constraints imposed by the nature of the digital hardware used for calculations. Digital hardware is bound by physical limitations, including constraints on processing power, storage capacity, and time. A key limitation, however, is its inherent binary nature, which can handle only discrete values precisely and may struggle with mathematical functions on real variables. This chapter aims to summarize key results from the field of computability and highlight critical, yet lesser-known issues in optimization theory.