Algorithmic problems for differential polynomial algebras (Q267385)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithmic problems for differential polynomial algebras |
scientific article |
Statements
Algorithmic problems for differential polynomial algebras (English)
0 references
8 April 2016
0 references
In this paper it is proved that the membership problem for finitely generated differential ideals of differential algebras with at least two derivation operators is algorithmically undecidable, i.e. the word problem for differential algebras is undecidable. The main instrument of proving this is an interpretation of Minsky machines. The proof uses the fact that every recursive function can be calculated by Minsky machines without cycles [the author, Algebra Logic 32, No. 4, 244--255 (1993); translation from Algebra Logika 32, No. 4, 450--470 (1993; Zbl 0851.16023)] a method of interpreting the ideal membership problem from [the author, ``The occurrence problem in free associative and free Jordan algebras'', in: Algorithmic problems in algebra and model theory, 11--15 (1995)], it is also proved that the membership problem for finitely generated differential subalgebras is undecidable.
0 references
differential polynomial algebras
0 references
the ideal membership problem
0 references
the subalgebra membership problem
0 references
Minsky machines
0 references
Groebner bases
0 references
0 references
0 references