Timeline for Is it decidable to check if an element has finite order or not?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 8, 2016 at 16:38 | vote | accept | Al Tal | ||
| Oct 8, 2016 at 16:38 | vote | accept | Al Tal | ||
| Oct 8, 2016 at 16:38 | |||||
| Oct 5, 2016 at 22:20 | comment | added | Benjamin Steinberg | It can be undecidable for groups with decidable subgroup membership problem. It is undecidable in free metsbelian groups and Z wr Z. Markus Lohrey and I have several papers on this | |
| Oct 5, 2016 at 18:38 | comment | added | Al Tal | Benjamin, could you please tell what is interesting is known and unknown about the membership problem for submonoids? | |
| Oct 5, 2016 at 17:18 | comment | added | Benjamin Steinberg | I thought about these things back when I used to study the submonoid membership problem of which the order problem is a special case. | |
| Oct 5, 2016 at 17:18 | comment | added | YCor | Thanks, I hadn't realized this! of course while the infinite order problem is solvable iff the order problem is solvable, the problem become different if we care of effectiveness (but this is not the point here). | |
| Oct 5, 2016 at 16:54 | comment | added | Benjamin Steinberg | If you know how to check the word problem then you can check the powers of an element and see if some power is trivial and what is the smallest so you just need to be able to check if the order is infinite. | |
| Oct 5, 2016 at 16:47 | comment | added | YCor | I've checked the paper: it seems to indeed have unsolvable "infinite order" problem (this does not formally follow from having unsolvable order problem: e.g., if a group is torsion, the "infinite order problem" is trivially solvable, but maybe not the order problem). | |
| Oct 5, 2016 at 16:40 | history | edited | YCor | CC BY-SA 3.0 |
added link
|
| Oct 5, 2016 at 16:31 | history | answered | Benjamin Steinberg | CC BY-SA 3.0 |