| dbo:description
|
- Decision problem pertaining to equivalency of expressions (en)
- problema matemàtic de decisió (ca)
|
| dbo:thumbnail
| |
| dbo:wikiPageWikiLink
| |
| dbp:event
|
- Graham Higman characterises the subgroups of finitely presented groups with Higman's embedding theorem, connecting recursion theory with group theory in an unexpected way and giving a very different proof of the unsolvability of the word problem. (en)
- Dehn presents Dehn's algorithm, and proves it solves the word problem for the fundamental groups of closed orientable two-dimensional manifolds of genus greater than or equal to 2. Subsequent authors have greatly extended it to a wide range of group-theoretic decision problems. (en)
- Britton presents a greatly simplified version of Boone's 1959 proof that the word problem for groups is unsolvable. It uses a group-theoretic approach, in particular Britton's Lemma. This proof has been used in a graduate course, although more modern and condensed proofs exist. (en)
- William Boone independently shows the word problem for groups is unsolvable, using Post's semigroup construction. (en)
- Axel Thue poses a general problem of term rewriting on tree-like structures. He states "A solution of this problem in the most general case may perhaps be connected with unsurmountable difficulties". (en)
- The Church-Turing thesis emerges, defining formal notions of computability and undecidability. (en)
- Emil Post and Andrey Markov Jr. independently construct finitely presented semigroups with unsolvable word problem. Post's construction is built on Turing machines while Markov's uses Post's normal systems. (en)
- Pyotr Novikov gives the first published proof that the word problem for groups is unsolvable, using Turing's cancellation semigroup result. The proof contains a "Principal Lemma" equivalent to Britton's Lemma. (en)
- Alan Turing shows the word problem for cancellation semigroups is unsolvable, by furthering Post's construction. The proof is difficult to follow but marks a turning point in the word problem for groups. (en)
- Gennady Makanin proves that the existential theory of equations over free monoids is solvable. (en)
- Max Dehn poses the word problem for finitely presented groups. (en)
- Axel Thue poses the word problem for finitely presented semigroups. (en)
- Boone publishes a simplified version of his construction. (en)
- John Britton gives another proof that the word problem for groups is unsolvable, based on Turing's cancellation semigroups result and some of Britton's earlier work. An early version of Britton's Lemma appears. (en)
|
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdfs:label
|
- Word problem (mathematics) (en)
- Problème du mot (fr)
- Problema da palavra (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
