Automatic problem solving

from Wikipedia, the free encyclopedia

The automatic problem solving is a branch of artificial intelligence is, the contents of the formalization of problems and their automated solution is. The formalization is usually carried out using graphs or decision trees . The solution to a problem is understood as a path in such a graph or tree which leads to a state that fulfills all the desired conditions. At the beginning of research in the area of ​​automatic problem solving, there was still hope for general problem solving programs for any problem (e.g. General Problem Solver ), but today problem solving is deliberately limited to relatively specific problem areas.

The basic strategy for automatic problem-solving is to submit all axioms and derivation rules of a formal system to a machine in a purely mechanical way and then to let this machine prove new propositions purely formally and typographically by reasoning based on the axioms and using all valid derivation rules new well-formed chains of the formal system are generated. These then proved theorems can then in turn be used as a basis for further, even more complex deductions.

However, the concept of automatic problem solving has been recognized as a hopeless undertaking based on the results of basic mathematical and information technology research. Above all, work in the first half of the 20th century, which dealt with Turing machines and the undecidability of formal statements ( Rice's theorem , halting problem ) as well as the incompleteness of formal systems of statements ( Gödel's incompleteness theorem ), revealed fundamental limits for solving problems.

Every sufficiently powerful formal system (sufficiently powerful to be able to represent, for example, mathematical problems of number theory) is therefore necessarily either contradictory or incomplete. In the first case, statements of the form "This sentence cannot be proven" could be generated within the system, which obviously contain a self-contradiction. In the latter case, the system is not powerful enough to actually derive all true sentences by strictly applying the following rules; that is, there are true but unprovable statements within such a system; the system is therefore said to be incomplete.

The incompleteness theorem suddenly destroyed the mathematician's hope of being able to prove all possible truths by applying a finite number of derivation steps (something that should also be possible with an automaton). An important consequence of Gödel's theorem is the failure of the so-called Hilbert program .

See also :