How to prove the absence of an algorithm for solving a problem?

Question

Programming

How to prove the absence of an algorithm for solving a problem? What can you read about it? Thanks in advance.

Answer 1

In the general case, problems of this kind are reduced to, on the contrary, proving the existence of an algorithm.
There are several universal basic methods of proof: by contradiction, induction, invariant, etc.
To solve such a problem, you need to highlight several main theses regarding your problem:
1. Initial data
2. Options for possible actions with them
3. How the data changes in the process
4. What should be the output
Based on this, the above methods can be applied, for example, to assume that such an algorithm exists, or, for example, to compose induction steps and determine whether the conditions are met for all cases. In this context, your assumptions are axioms, they are inviolable and do not require proof. Based on the axioms, you can build some lemmas - such "partial proofs" - some more complex provisions that are derived from the axioms and help later in the final proof. It should also be remembered that the condition of the proof can be artificially strengthened in order to make it easier to prove your entire theorem.
You can listen to more about this in lectures from MIT .

Answer 2

Find a condition that matches the solution but doesn't match the original data. Or vice versa and right to left

Answer 3

IMHO, there can be no universal proof here.
Only for some specific categories of tasks, for each - in its own way.

Answer 4

No way.
The problem either has an incorrect condition or has a solution.
The fact that someone does not have the necessary skills to solve the problem in this case does not matter

Answer 5

Are you looking for a stop problem ? Usually it is reduced to the desired problem, thereby showing algorithmic unsolvability.