Forum Problem Lists Definitions FAQ

4.20 (1973)

Solved

a) Let $F$ be a free group, and $N$ a normal subgroup of it. Is it true that the Cartesian square of $N$ is $m$-reducible to $N$ (that is, there is an algorithm that from a pair of words $w_1, w_2 \in F$ constructs a word $w \in F$ such that $w_1 \in N$ and $w_2 \in N$ if and only if $w \in N$)?
b) (Well-known problem). Do there exist finitely presented groups in which the word problem has an arbitrary pre-assigned recursively enumerable $m$-degree of unsolvability?

Contributor: M. K. Valiev

Progress

a) No, it is not true (O. V. Belegradek, Siberian Math. J., 19 (1978), 867–870).
b) No, there exist $m$-degrees which do not contain the word problem of any recursively presented cancellation semigroup (C. G. Jockusch, jr., Z. Math. Logik Grundlag. Math., 26, no. 1 (1980), 93–95).

Comments

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic. If you want to submit a proof (or a partial proof), please use the dedicated proof submission form rather than posting it in the comments.
Order by newest first or oldest first.

No comments yet. Be the first to comment.

Proof claims

Proof claims are the responsibility of the submitter. Appearance here does not mean the claim has been checked for mathematical correctness. Moderators only screen for spam, abuse, and obviously low-effort submissions.

No proof claims yet.