Halting Problem in Theory of Computation

The theory of computation is a theoretical learning of mathematics and computer science which focuses on dealing with the computation logic in the context of machines. 

In simpler words, the theory helps researchers and scientists to understand the working of machines and their problem-solving capabilities. 

The theory of computation utilises different symbols, machines and languages to provide logical answers and solve problems. One important question or concept related to the theory of computation is the halting problem. 

The problem helps you check whether the specified algorithm will ever stop or will keep running forever. However, there is a lot more to this problem which makes it one of the most asked questions. 

If you are also wondering what makes the halting problem so special and a top-asked question, we have got all your answers. Let's begin with the basics and understand what is a halting problem. 

Understanding Halting Problem

The halting problem in the theory of computation focuses on checking out whether the specific algorithm will ever stop at any point in time or not. When you run a program or an algorithm on the given input, there can be two outcomes. Either the algorithm will return a valid output and stop after some time or the program will keep running infinitely. The halting problem helps us understand and differentiate between these two conditions. 

Here, you will be given an algorithm or a problem and using a halting problem, you are required to find if the program will ever stop or not. 

In the theory of computation, the concept of Turing machine can be used to design a machine which can detect if the program will stop on the given input or not. 

But the question here is: can you really design a machine that can detect it? Is there any way possible? 

Well, if you are confused about the same questions, the next section certainly has answers for you. 

Halting Problem Solution

Let's be honest, there is no solution for the halting problem. There is no generalized algorithm to predict if the program will halt or not. To check the same, the only method is to run that program and see if ever halts. 

To prove that the halting problem has no solutions, let's consider an example. However, before the proof, let's discuss some basic terminologies. 

1. Turing Machine

It is a mathematical model used in computations. A Turing machine can be defined as a kind of CPU that manages and controls every data manipulation carried out by your system. A Turing machine can either halt or may run infinitely based on the input provided to the machine. 

2. Decision Problems

There are only two possible results of a decision problem on the given input. In the theory of computation and complexity theory, a decision problem is generally represented as a yes or no question on the given input values. 

3. Undecidable Problems

An undecidable problem in the theory of computation is a kind of problem that requires the answer in yes or no form. However, no program can provide an accurate answer all the time which means that the algorithm or the program that you are running may give an incorrect answer sometimes. There are also chances that the program may run infinitely without even providing any answer.

So, now that you are aware of all the basic terms used in the halting problem, let's understand why it is not possible to find the solution to the problem. 

Step 1: Let's say that we can create a machine, say HM((P, I). Here, HM denotes the halting machine, P denotes the program and I denotes the input. When the machine will accept the input, the machine will provide an output that whether the program P will terminate or not. 

Step 2: After that, you need to create an inverted halt machine. This will take a program P as its input and

• It will loop infinitely if HM provides output as Yes. 

• It will halt in case HM will provide output as No. 

Step 3: Now, consider a scenario where the IM program is passed to the function as its input. Here, a contradiction will arise. 

This is because it is not possible that the outer function halts and the inner function are still running in the loop. At the same time, it is not possible that the outer function halts even if the inner function is still halting. Therefore, both conditions will not halt in the IM machine even on the basis of our assumptions. 

Therefore, we can say that the problem solution is undecidable. 

Similarly to the halting problem, another tricky problem that you will often come across is the dining philosopher's problem in OS. Let's dig deeper into this problem and understand how to solve it. 

Dining Philosopher's Problem In OS

The problem statement states that 5 philosophers are sharing a single circular table. Here, they think and eat alternatively. Now, a bowl filled with rice and 5 chopsticks is available for each philosopher. Each philosopher will need both left and right chopsticks for eating. A philosopher will only eat in case both chopsticks are there. In case they are not available, the philosopher will put the chopstick back and will begin thinking. 

To resolve this problem, generally semaphores are used. However, the issue with the solution is that it ensures that two neighbouring philosophers do not eat together. This condition, therefore, leads to a deadlock. The deadlock can be avoided if:

• Only four philosophers should be present at the table. 

• The philosopher sitting on the even spot must pick the right chopstick first and then pick the left one. Whereas, the philosopher sitting on the odd spot must pick the left chopstick first and then pick the right one. 

• A philosopher must only pick a chopstick if both of them are available. 

Conclusion

The halting problem is a well-known problem related to the theory of computations that indicates whether the algorithm will stop for the given input or not. 

However, when it comes to finding solutions to the halting problem, no such generalised algorithm is present to accurately decide if the given problem will halt or not. 

Therefore, to check if the algorithm will stop or not, the only way is to run the program and see. 

Article source: https://article-realm.com/article/Finance/33383-Halting-Problem-in-Theory-of-Computation.html