Non-Computational Problems in Theory of computation explain in simple and easy terms with easy example
Non-computational problems in the theory of computation are those that cannot be solved by a computer or algorithm, regardless of how powerful or efficient the computer is. These problems are fundamentally unsolvable due to their inherent nature. Let’s explore a couple of non-computational problems with simple examples:
1. **The Halting Problem**:
The halting problem is a classic example of a non-computational problem. It asks whether a given program will eventually stop (halt) when run on a particular input, or if it will run forever in an infinite loop. Alan Turing proved that there is no general algorithm that can decide this for all possible programs and inputs. In other words, you cannot create a computer program that can always correctly predict whether another program will halt or run forever.
Simple Example: Imagine you have a program that simulates another program and checks if it halts or runs forever. If you could solve the halting problem, you could use it to create a paradox. Consider the following program:
```
if (solvesHaltingProblem(programA, inputX)) {
// Run forever
} else {
// Halt
}
```
If the programA halts, it should run forever (according to the inner program). But if the programA runs forever, it should halt (again according to the inner program). This leads to a contradiction and shows that the halting problem is unsolvable in a general sense.
2. **The Entscheidungsproblem**:
The Entscheidungsproblem, posed by David Hilbert, asks for an algorithm that can decide whether a given mathematical statement is true or false. In other words, it’s about determining the truth or falsehood of mathematical propositions. However, Kurt Gödel’s incompleteness theorems and Alan Turing’s work on the halting problem showed that there cannot be a universal algorithm that can decide the truth or falsehood of all mathematical statements.
Simple Example: Let’s say you have a computer program that can decide the truth or falsehood of any mathematical statement. Now, consider the following statement:
“This statement is false.”
Is this statement true or false? If the program says it’s true, then it must be false because it claims to be false. If the program says it’s false, then it must be true because it claims to be false. This creates a paradox, demonstrating that a general algorithm for the Entscheidungsproblem is impossible.
In essence, non-computational problems highlight the limits of what can be achieved with algorithms and computers. These problems are like intellectual puzzles that cannot be consistently and universally solved by any computational process.
