All Questions
8 questions
2
votes
0
answers
71
views
Empty preimage under homomorphism of finitely presented groups with decidable word problems
Let $G, H$ be finitely presented groups with decidable word problems.
Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
user178109
6
votes
2
answers
490
views
What is the name of this type of groups?
Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as:
$$G=\langle ...
- 2,233
6
votes
3
answers
872
views
An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.
Edited (this question contains two versions of a similar question)
Is there some finitely presented group $G$ generated by $g_1,...,g_n$ such that
there is an element $g\in G$ expressed as a finite ...
- 14.3k
18
votes
1
answer
921
views
Automorphism group of the Turing degrees
It is conjectured that the automorphism group of the Turing degrees, $Aut(\mathcal{D})$, is trivial. However, to the best of my knowledge, the current state-of-the-art is that $Aut(\mathcal{D})$ is ...
- 21.2k
30
votes
3
answers
3k
views
Is it decidable whether or not a collection of integer matrices generates a free group?
Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
- 18.7k
17
votes
1
answer
875
views
Which finitely presented groups can be distinguished by decidable properties?
This question continues the line of inquiry
of these
three
questions.
Question. Which finitely presented groups can be
distinguished by decidable properties?
To be precise, let us say that φ is ...
- 236k
19
votes
4
answers
1k
views
Does every decidable question about finitely presented groups amount to a question about abelian groups?
This question is about an issue left unresolved by Chad
Groft's excellent
question and
John Stillwell's excellent
answer of
it. Since I find the possibility of an affirmative answer
so tantalizing, I ...
- 236k
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 258