Portal de Periódicos da CAPES

Word Problems and Recursively Enumerable Degrees of Unsolvability. A Sequel on Finitely Presented Groups

1966; Princeton University; Volume: 84; Issue: 1 Linguagem: Inglês

10.2307/1970530

1939-8980

William W. Boone,

Logic, programming, and type systems

The present paper is a sequel to [B4.2 We specify an explicit grouptheoretic construction based on techniques of Britton [D] which, if added to the Thue system constructions of [B], results in the exhibition of a finitely presented group with word problem of arbitrary recursively enumerable degree of unsolvability. One may be given the arbitrary degree as the word problem of a given Thue system. Only the results of [B] are needed, not the details, except for two definitions of notation.3 The exhibition of a finitely generated, recursively related group of arbitrary recursively enumerable degree of unsolvability (as described in [B3])2 is briefly noted. Related independent lines of development are the announcements by Cejtin [B9] (for Thue systems), and by Fridman [B13] (for finitely presented groups), as well as the detailed arguments by Clapham [Bl0] (for finitely presented groups), and by Shepherdson [B251 (for Thue systems). (See footnote 6.) Like [BI, this work is dedicated to the memory of Thoralf Skolem.