Loading...
Please wait, while we are loading the content...
Similar Documents
The computability of group constructions II
| Content Provider | Scilit |
|---|---|
| Author | Gatterdam, R. W. |
| Copyright Year | 1973 |
| Description | Finitely presented groups having word, problem solvable by functions in the relativized Grzegorczyk hierarchy, ${E^{n}$(A)| n ε N, A ⊂ N (N the natural numbers)} are studied. Basically the class $E^{3}$ consists of the elementary functions of Kalmar and $E^{n+1}$ is obtained from $E^{n}$ by unbounded recursion. The relativization $E^{n}$(A) is obtained by adjoining the characteristic function of A to the class $E^{n}$.It is shown that the Higman construction embedding, a finitely generated group with a recursively enumerable set of relations into a finitely presented group, preserves the computational level of the word problem with respect to the relativized Grzegorczyk hierarchy. As a corollary it is shown that for every n ≥ 4 and A ⊂ N recursively enumerable there exists a finitely presented group with word problem solvable at level $E^{n}$(A) but not $E^{n-1}$(A). In particular, there exist finitely presented groups with word problem solvable at level $E^{n}$ but not $E^{n-1}$ for n ≥ 4, answering a question of Cannonito. |
| Related Links | https://www.cambridge.org/core/services/aop-cambridge-core/content/view/7EEDBBD14F5D429670722344BC75E1D5/S0004972700045469a.pdf/div-class-title-the-computability-of-group-constructions-ii-div.pdf |
| Ending Page | 60 |
| Page Count | 34 |
| Starting Page | 27 |
| ISSN | 00049727 |
| e-ISSN | 17551633 |
| DOI | 10.1017/s0004972700045469 |
| Journal | Bulletin of the Australian Mathematical Society |
| Issue Number | 1 |
| Volume Number | 8 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 1973-02-01 |
| Access Restriction | Open |
| Subject Keyword | Bulletin of the Australian Mathematical Society Problem Solvable Presented Groups Group with Word Finitely Presented Group |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
