How to prove no algorithm for the solution of any problem? What you can read about it? Thanks in advance.

asked July 9th 19 at 11:22

5 answers

answered on

Solution

In General, problems of this kind are reduced to the contrary, proof of the existence of the algorithm.

There are a few universal basic methods of proof: by contradiction, induction, invariant, etc.

To solve this problem, you need to highlight a few key points concerning your problem:

1. The source data

2. Some of the actions with them

3. How to change data in the process

4. What should come out of it

Based on this it is possible to apply the above methods, for example, to assume that such an algorithm exists, or, for example, to make the induction step and determine whether all of the cases are conditions. In this context, your initial conditions are axioms, they are indestructible and do not require evidence. On the basis of axioms, you can build some lemmas - are currently "partial proof" - some of the more complex provisions that are derived from axioms, and later help in the final proof. It should also be remembered that the condition of the evidence can be artificially enhanced in order to make it easier to prove your entire theorem.

More about this you can listen to lectures from MIT.

There are a few universal basic methods of proof: by contradiction, induction, invariant, etc.

To solve this problem, you need to highlight a few key points concerning your problem:

1. The source data

2. Some of the actions with them

3. How to change data in the process

4. What should come out of it

Based on this it is possible to apply the above methods, for example, to assume that such an algorithm exists, or, for example, to make the induction step and determine whether all of the cases are conditions. In this context, your initial conditions are axioms, they are indestructible and do not require evidence. On the basis of axioms, you can build some lemmas - are currently "partial proof" - some of the more complex provisions that are derived from axioms, and later help in the final proof. It should also be remembered that the condition of the evidence can be artificially enhanced in order to make it easier to prove your entire theorem.

More about this you can listen to lectures from MIT.

answered on July 9th 19 at 11:26

Find a condition that matches, but does not match the original data. Or Vice versa from right to left

How to prove, for example, that fizzbuzz can't be solved without using variables? Solve using variables will not work. - demetris84 commented on July 9th 19 at 11:29

What is considered to be a variable? There are three checks on the multiplicity. 15 ,5,3 . If not, make a variable for the number of iteration, it is possible krugami to write out every... - mercedes commented on July 9th 19 at 11:32

answered on July 9th 19 at 11:28

IMHO, a universal proof there can be.

Only for some specific categories of tasks, each in their own way.

Only for some specific categories of tasks, each in their own way.

answered on July 9th 19 at 11:30

As.

Task or has an incorrect condition, or has a solution.

Something that someone does not have the required skills to solve problem in this case is irrelevant

Task or has an incorrect condition, or has a solution.

Something that someone does not have the required skills to solve problem in this case is irrelevant

answered on July 9th 19 at 11:32

You are probably searching for the problem stop? It is usually reduced to the desired task, thus showing algorithmic unsolvability.

Find more questions by tags AlgorithmsMathematicsProgramming