In computability theory, an algorithmically unsolvable problem is a problem that has a yes or no answer for each object from a certain set of input data, for which (fundamentally) there is no algorithm that, having received any possible object as input, stops and gives the correct answer after a finite number of steps.
Content
- 1 Problems Related to Abstract Machines
- 2 Matrix Issues
- 3 Other problems
- 4 Problems whose algorithmic unsolvability has not been proved
- 5 See also
- 6 notes
Problems Related to Abstract Machines
- Stop problem
- Self-applicability problem
- Busy beaver
- Any problem formulated in Rice's theorem
- Determine whether a given initial configuration in the game “Life” will ever reach a given final configuration [1]
Matrix Issues
- The problem of a dying matrix : for a given finite set of square n × n matrices, determine whether the product of all or some of these matrices (possibly with repetitions) exists in any order giving a zero matrix. The problem is insoluble even for n = 3 (solvability for n = 2 is an open question [2] )
- Unit matrix problem : for a given finite set of n × n square matrices, determine whether the product of all or some of these matrices (possibly with repetitions) exists in any order giving a unit matrix. The problem is unsolvable for integer matrices starting from n = 4 [3] and solvable for n = 2 [4] (solvability for n = 3 is an open question). The problem is equivalent to the question whether the matrix semigroup is a group.
- The freedom problem for a matrix semigroup is algorithmically unsolvable for integer matrices starting from n = 3 and is open for n = 2.
Other issues
- Resolution Problem ( German: Entscheidungsproblem ).
- Derivability of a formula in Peano arithmetic .
- Post Compliance Problem .
- Calculation of Kolmogorov complexity of an arbitrary string.
- An ideal archiver that creates for any input file the smallest possible program that prints this file [5] .
- An ideal size-optimizing compiler [6] .
- Hilbert's tenth problem .
- Determine whether a plane can be tiled with a given set of Wang tiles .
- Determine whether the plane can be tiled with this set of polyminoes .
- The problem of unification second and higher orders.
- The problem of type inference in the Hindley-Milner type system with an N- rank polymorphism.
Unproven algorithmic unsolvability problems
For some problems, the algorithm that solves them is unknown, and by their nature they are similar to the known algorithmically unsolvable problems. Questions about the algorithmic solvability of such problems are open problems . Here are some of the tasks:
- An analogue of the tenth Hilbert problem for equations of degree 3
- An analogue of the tenth Hilbert problem for equations in rational numbers [7]
- The problem of a dying matrix for matrices of order 2
See also
- Algorithmic solvability of formal theory
- Gödel's incompleteness theorem
Notes
- ↑ Life Universal Computer
- ↑ When is a pair of matrices mortal?
- ↑ Paul C. Bell; Igor Potapov. On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups (Eng.) // International Journal of Foundations of Computer Science : journal. - World Scientific, 2010. - Vol. 21.6 . - P. 963–978 . - DOI : 10.1142 / S0129054110007660 .
- ↑ Christian Choffrut; Juhani Karhumäki. Some decision problems on integer matrices. (unspecified) // ITA. - 2005 .-- T. 39 (1) . - S. 125-131 . - DOI : 10.1051 / ita: 2005007 .
- ↑ The presence of such an archiver would make it possible to calculate the Kolmogorov complexity of an arbitrary string, which is an algorithmically unsolvable problem.
- ↑ In particular, he would replace any non-stopping algorithm with a trivial empty cycle, and recognizing such algorithms is equivalent to a stopping problem and is an algorithmically unsolvable problem.
- ↑ Uspensky V. A. , Semenov A. L. Solvable and unsolvable algorithmic problems. // Quantum , 1985, No. 7, p. 9 - 15