Decidability 1

Life is about decisions, large and small ones. What should I study? Which bread do I buy? Should I reach out to a long lost friend? Which approach to life should I take? What values are important to me? Do I buy the next lens or do I save up the money? Do I go outside for sports? Do I keep working for another evening? How do I want to spend the limited time I have in my life?

Some questions seem irrelevant, others may determine several years of our future life. So, how can we decide all these questions? Or: Is it even possible to decide all these questions? How should we approach and deal with any possibly life changing matter and decide: This or that? Now or later? Yes or no?

The more difficult the questions become that I face, the more I am convinced that they are inherently undecidable at any given moment in time. We do not have enough information to know all outcomes, the uncertainties are always large, and we cannot weigh in all factors because of their multitude and complexity. This also won’t change in the future. Maybe the options we decide on shift. Maybe it’s too late for a decision and we did not even have the opportunity to deliberately decide it ourselves. Some things we were sure that we chose correctly turned out to be terribly wrong; other things work perfectly even though we thought we made the wrong turn earlier.

Decidability is also infamous in computer science. In its simplest form it is known as the Halting Problem and was presented by Alan Turing. The problem formulation is as follows: Given an arbitrary algorithm and its input, is it possible to find another algorithmic solution that decides whether the given algorithm stops on the given input, or continues to run forever? If a solution can be found, then the problem is decidable. If no solution exists, then the problem is undecidable. In the case of the Halting problem, it can be shown that no algorithmic solution exists that solves the stated problem; thus, it is inherently undecidable. If you’re interested, keep reading for the proof:

We proof the above statement by contradiction. Imagine there exists an algorithm that can decide our problem statement: Given, as input, an arbitrary algorithm and its input, it can always decide whether this algorithm stops on the input or not. We call our deciding algorithm h and our input x. Given h, we now define a new algorithm h* that is a modified version of h: If h determines that the input algorithm stops, then h* keeps running in a loop. If h determines that the input algorithm keeps running, then h* stops. What happens if we feed our algorithm h* as input to itself (of which our original deciding algorithm h is part of)? This can be seen as a self-referential operation. We refer to the h* that is the deciding algorithm to h(h*) and to the input h* as x(h*). Both, h(h*) and x(h*) are the same algorithm. We have two possible outcomes: Either h decides that its input x(h*) stops – however, in this case h(h*) would keep running: a contradiction because x(h*) and h(h*) are the same algorithm. Or h decides that its input x(h*) doesn’t stop – but now, h(h*) would stop: again, a contradiction. Thus, the halting problem is not decidable.