Timeline for Are compact topological $n$-manifolds recursively enumerable?
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 31, 2023 at 16:48 | comment | added | YCor | How does a Turing machine output a topological manifold if it's not triangulable? | |
| Jul 16, 2020 at 17:00 | vote | accept | Eric S. | ||
| Jul 15, 2020 at 4:46 | answer | added | Ian Agol | timeline score: 10 | |
| Jul 15, 2020 at 1:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Nov 23, 2015 at 16:45 | comment | added | Eric S. | That's an interesting link, Thomas, but it only seems to apply to smooth manifolds, not general topological manifolds. | |
| Nov 23, 2015 at 16:36 | comment | added | Thomas Rot | I am probably burning my hands here, as this is very far from what I usually think about. Are (smooth?) manifolds not more or less the same thing as connected components of zero sets of rational polynomials, which can be enumerated: mathoverflow.net/questions/71415/manifolds-and-polynomials | |
| Oct 24, 2015 at 23:15 | comment | added | Peter Samuelson | @EricS. I'm not sure either - it could be the case that this strategy works for PL manifolds but doesn't work for topological ones for a subtle (at least for me) reason. | |
| Oct 24, 2015 at 23:06 | comment | added | Eric S. | @PeterSamuelson, I don't see any immediate reason something like that couldn't be made to work, but then again I don't know enough to be sure that it would. One might try to formulate this approach in terms of some notion of "computable pseudogroups." | |
| Oct 24, 2015 at 19:50 | comment | added | Peter Samuelson | "the space of gluing maps between two balls in $\mathbb R^n$ has a dense countable subset," and "if the finitely many gluing maps needed to describe $M$ are approximated well enough, the two resulting manifolds are homeomorphic." But I don't know enough topology to make this precise off the top of my head. (edit: we'd also need each point in the countable dense set in the previous comment to be described by a finite amount of data.) | |
| Oct 24, 2015 at 19:49 | comment | added | Peter Samuelson | The classification problem is much harder than the problem in the question, which is just to enumerate all manifolds. For example, the question of whether a finitely presented group is trivial is undecidable, but the problem "enumerate all finitely presented groups" has an essentially trivial answer (list all finite sets of words in all finite alphabets of the form $(x_1,\cdots,x_n)$). I think the answer to the question should be "yes," which should be some combination of the statements "a compact M is determined by finitely many gluing maps," (cont...) | |
| Oct 24, 2015 at 15:43 | answer | added | Christian Remling | timeline score: 1 | |
| Oct 24, 2015 at 4:35 | comment | added | Eric S. | Thanks, @BjørnKjos-Hanssen! @Jason Rute, I interpret the classification issue as a harder question, since it is known to be unsolvable, even for PL manifolds. One might also ask about the Turing degree in this case, but it is probably halting complete. The questions you ask about computability above are along the lines of what I am asking. | |
| Oct 24, 2015 at 4:32 | history | edited | Eric S. | CC BY-SA 3.0 |
added 30 characters in body
|
| Oct 24, 2015 at 2:48 | comment | added | Jason Rute | Via Wikipedia (en.wikipedia.org/wiki/Topological_manifold): "The full classification of $n$-manifolds for $n$ greater than three is known to be impossible; it is at least as hard as the word problem in group theory, which is known to be algorithmically undecidable. In fact, there is no algorithm for deciding whether a given manifold is simply connected. There is, however, a classification of simply connected manifolds of dimension $\geq 5$." I don't know the citation, what they mean by classification, or if the result applies to the class of compact manifolds. | |
| Oct 24, 2015 at 2:40 | comment | added | Jason Rute | I guess another question is whether every topological manifold is even homeomorphic to (1) a computable subset of $\mathbb{R}^n$ (for some $n$), (2) a computable metric space, or (3) a computable topological space. | |
| Oct 24, 2015 at 2:32 | comment | added | Jason Rute | I suppose an in-between possibility exists: You could possibly be able to enumerate all topological manifolds (in a matter similar to @BjørnKjos-Hanssen's suggestion, or as the index of a description of a computable topological space), but your enumeration contains homeomorphic duplicates of each manifold type, and moreover, it is impossible to find an enumeration containing only one representative of each homeomorphism class. | |
| Oct 24, 2015 at 0:57 | history | edited | Eric S. | CC BY-SA 3.0 |
added 13 characters in body
|
| Oct 24, 2015 at 0:55 | comment | added | Eric S. | @ChristianRemling, to avoid confusion, I have removed the question about Turing degrees, and clarified that I am in part asking for an answer to the issues you bring up. | |
| Oct 24, 2015 at 0:49 | history | edited | Eric S. | CC BY-SA 3.0 |
added 433 characters in body
|
| Oct 23, 2015 at 22:57 | comment | added | Bjørn Kjos-Hanssen | @ChristianRemling Yes, and I mean, say, the set of integers $2^n3^k5^f$ where $n$ and $k$ are as in my other comment, and $f$ is a number encoding the finite approximation (in the sense of a bitmap with low resolution, I guess) to the embedded manifold. | |
| Oct 23, 2015 at 22:48 | comment | added | Christian Remling | @BjørnKjos-Hanssen: The OP asks about a Turing degree, among other things, so I really think we must insist on a set of integers that we are asked to investigate. | |
| Oct 23, 2015 at 22:41 | comment | added | Bjørn Kjos-Hanssen | @ChristianRemling I think the question is okay if you interpret it more loosely. Even if it can't be triangulated, we can still ask for a sequence of better and better approximations (as measured by $\epsilon=1/k>0$) of an embedding of our manifold in $\mathbb R^n$ for a suitable $n$. And we can make a double sequence of approximations $A_{n,\epsilon}$ of the embedding $A_n$ of the $n$th manifold. | |
| Oct 23, 2015 at 22:35 | comment | added | Christian Remling | Yes, I think that (Timothy's comment) sums it up. Or, in the context of the halting problem you refer to: Is there a TM that decides if TM #n, run on input $0$, say, stops? That of course depends on how you number TM's. It makes no sense whatsoever to ask the question without first clarifying how one wants TM's numbered (there are or course agreed on admissible numberings in this case that are standard, but I wouldn't know of a standard numbering of manifolds). | |
| Oct 23, 2015 at 22:02 | comment | added | Timothy Chow | @Eric S. : I believe that Christian Remling's point is that before you even think about computability, a more fundamental question is whether there is even a way to describe a compact topological manifold using a finite number of bits. And the question of what constitutes a reasonable description is a question that you have to answer before anyone else can answer the computability question, or else there is nothing to stop someone from saying that the number 1 is a description of some compact manifold, the number 2 is a description of some other compact manifold, etc. | |
| Oct 23, 2015 at 18:18 | comment | added | Eric S. | @Christian, the whole point is I don't know how to create an algorithm that eventually labels all $n$-manifolds. If I did, I would already have the answer to this question. But yes, the output of this Turing machine is supposed to be a string which somehow encodes a manifold. For example, if I asked about PL $4$-manifolds, the Turing machine could just output some binary description of all admissible triangulations of 4-manifolds. | |
| Oct 23, 2015 at 14:53 | comment | added | Christian Remling | Turing machines output numbers or strings, not manifolds, so you first need to label your manifolds somehow to make this precise. The answer will of course depend on how you do this (say you give the compact topological manifolds the labels $2,4,6,8,\ldots$; then I could sell you a Turing machine that lists them). | |
| Oct 23, 2015 at 9:14 | comment | added | Eric S. | This is not immediately clear to me, especially considering their proof is by contradiction. | |
| Oct 23, 2015 at 9:04 | comment | added | Andreas Thom | Did you look at the proof of Cheeger and Kister? I thought that it amounts to an enumeration with possible repetitions. | |
| Oct 23, 2015 at 8:23 | history | edited | Eric S. | CC BY-SA 3.0 |
edited body
|
| Oct 23, 2015 at 7:49 | review | First posts | |||
| Oct 23, 2015 at 8:31 | |||||
| Oct 23, 2015 at 7:47 | history | asked | Eric S. | CC BY-SA 3.0 |