It recently occurred to me that Turing’s solution to the halting problem has remarkable connections with the theory of deterministic chaos especially if you reformulate his solution as a fixed-point theorem. This is important for natural scientists that regularly use computer simulations because it means that predicting the behaviour of a complex computer simulation is not easier than predicting the behaviour of a chaotic system. In fact, the correspondence between the behaviour of Turing machines and deterministic chaos is important in another setting which may be called the reverse halting problem.
Scientists typically observe a phenomenon, a data-generating process, they assume that this was the result of an algorithmic procedure \(F\) that may be simulated by a Turing machine(i.e. a computer) and then they try to recover the function \(F\) using machine learning methods. In this sense, the reverse halting problem is a hardness of approximation problem. However, this problem can’t escape the challenge of deterministic chaos either. In fact, the degree of chaos determines how hard the hardness of approximation problem is i.e. whether it belongs to P or NP.
Unless you have a full understanding of the initial conditions, this process could have had an astronomical number of possible histories given what you know. This is one reason why I am somewhat skeptical of the entire neural circuit breaking enterprise in computational neuroscience . This situation also explains why machine learning researchers spend so much time carefully choosing the random seed for their experiments; the random seed is part of the initial value problem in machine learning.
On the other hand, I am a lot more confident that a first-principles approach to neural morphogenesis or what has developed into brain organoid research will lead to important breakthroughs in neuroscience.
- Aidan Rocke. Turing’s fixed-point theorem. 2021.
- Eric Jonas & Konrad Kording. Could a Neuroscientist Understand a Microprocessor? 2017.
- Venkatakrishnan Ramaswamy. An Algorithmic Barrier to Neural Circuit Understanding. 2019.