Skip to main content
deleted 270 characters in body
Source Link

EDIT: The question is not well-formed, as pointed out in the comments, but I'm leaving it up unanswered to preserve the discussion in the comments.


I'm always hesitant to bring my problems(Link to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask hereduplicate: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems)

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

EDIT: The question is not well-formed, as pointed out in the comments, but I'm leaving it up unanswered to preserve the discussion in the comments.


I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

(Link to SE duplicate: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems)

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

added 160 characters in body
Source Link

EDIT: The question is not well-formed, as pointed out in the comments, but I'm leaving it up unanswered to preserve the discussion in the comments.


I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

EDIT: The question is not well-formed, as pointed out in the comments, but I'm leaving it up unanswered to preserve the discussion in the comments.


I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

added 76 characters in body
Source Link

I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/posts/4959071/edithttps://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/posts/4959071/edit

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

I'm always hesitant to bring my problems to MO, but I asked this question on SE to no avail. I think it's obscure enough to ask here: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems

The Adian-Rabin theorem says that if a property of groups is Markov, (meaning, exhibited by at least one group, and having at least one "forbidden subgroup" which does not inject into any group with the property), then it is not decidable. The proof proceeds by extending a group $U$ with undecidable word problem such that deciding the property for this larger group depends on deciding the word problem on $U$ (which is not possible by assumption.)

If we stick to groups that don't have subgroups like $U$ with undecidable word problem, can we show that Markov properties are decidable on these groups? Since a group has an undecidable word problem iff it has a subgroup with an undecidable word problem (right?) I think this is equivalent to asking if we can decide a Markov property using an oracle that tells us if two group elements are equivalent.

Does anyone know about such results on the class of groups with decidable word problems?

Source Link
Loading