How is this algorithm solved

Algorithmic solvability of problems

Solvability of problems

Proof that a problem can be solved is usually provided by specifying a solution.

It is usually much more difficult to prove that a problem is unsolvable. You then have to make statements about all conceivable problem-solving options, both about those that you have already tried out and about those that you haven't even thought of.

Proofs of unsolvability are given a secure foundation if the means that can be used for the solution are specified. In the case of the nine-point problem, the term "grid-based route" was first clarified. With the help of this term, the insolubility with regard to the clarification made could be justified.

The situation is similar in computer science. Here one is interested in the algorithmic solvability of problems.

In the section Summary - Solvability of the Halting Problem. we have seen that the holding problem cannot be solved with the means of Python. But is it also algorithmically unsolvable? As the considerations on the nine-point problem show, one should be more careful. It might well be possible to use unconventional methods to solve the stop problem algorithmically

The only way to arrive at a satisfactory and non-speculative result is to specify the means of algorithmic problem solving. So we are taking a path that we followed in the same way with the nine-point problem.

Difficulties in specifying the algorithmic method

What is allowed in algorithmic problem solving? A more precise definition of the concept of algorithm provides an initial answer.

An algorithm is a processing rule that is formulated so precisely that it can also be processed by a machine.

It is often not that easy to decide whether a process description can be called an algorithm or not. The following criteria provide an orientation:

  • Uniqueness, d. H. the individual steps and their sequence are clearly described
  • Feasibility, d. H. he must be able to carry out the individual steps
  • Generality, d. H. it solves not just one problem, but a whole class of problems
  • Finiteness, d. H. its description consists of a text of finite length

Here, the machine, person or even imaginary unit is understood that is to execute the algorithm. The feasibility of an algorithm depends on the possibilities of the.

Has that cleared up all ambiguities? Probably not, because what does "feasibility" mean or what are the "possibilities of the processor".

The following example should clarify this.

Input: Polynomial equation p with integer coefficients in which different variables with different exponents can occur, e.g .: x3 + 5x2y2z - xz + 37 = 0 IF p has integer solutions: assign the value 0 to all variables AS LONG as no solution has been found: systematically change the values ​​of the variables Output: Solution tuple OTHERWISE: Output: "There are no solutions."

Is this description an algorithm? What speaks for it, what speaks against it?

For example, it is unclear whether a condition such as "p has integer solutions" can be executed. Can the "processor" - not described in detail above - check such a condition at all? This simple example already shows how little meaningful the criterion of feasibility formulated above is.

Conclusion: The above clarification of the term algorithm is an informal clarification. This is not precise enough to be used for (in) solvability proofs.

In the following, the aim is to close this gap and to formally define the term algorithm. With such a more precise algorithm term, the algorithmic solvability of problems can then be clarified argumentatively.