G. S. Tseytin's seven-relation semigroup with undecidable word problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911762298699776 |
|---|---|
| author | Nyberg-Brodda, Carl-Fredrik |
| author_facet | Nyberg-Brodda, Carl-Fredrik |
| contents | We give an introduction to the ideas behind G. S. Tseytin's 1958 construction of a seven-relation semigroup with undecidable word problem. We give a history of the ideas leading up to its construction, some intuition for the proof, and provide an overview of some subsequent results and developments which stem from this remarkable semigroup. An English translation of Tseytin's article by the author of the present article is supplemented at the end of the article (the Russian original was published in Trudy Mat. Inst. Steklov 52 (1958), pp. 172--189). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11757 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | G. S. Tseytin's seven-relation semigroup with undecidable word problem Nyberg-Brodda, Carl-Fredrik History and Overview Group Theory We give an introduction to the ideas behind G. S. Tseytin's 1958 construction of a seven-relation semigroup with undecidable word problem. We give a history of the ideas leading up to its construction, some intuition for the proof, and provide an overview of some subsequent results and developments which stem from this remarkable semigroup. An English translation of Tseytin's article by the author of the present article is supplemented at the end of the article (the Russian original was published in Trudy Mat. Inst. Steklov 52 (1958), pp. 172--189). |
| title | G. S. Tseytin's seven-relation semigroup with undecidable word problem |
| topic | History and Overview Group Theory |
| url | https://arxiv.org/abs/2401.11757 |