Timeline for Categories of recursive functions
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2013 at 8:23 | comment | added | Paul Taylor | I have just had an email from Milly saying "The question if free monoids are enough to get parameterized list objects is still open to me". Her papers are at www.math.unipd.it/~maietti/papers but unfortunately there are only filenames and no index.html. | |
| Apr 22, 2013 at 18:20 | comment | added | Paul Taylor | Francois, I am still trying to check with Milly whether the parametricity question is still open. My way of dealing with it would be to translate it into the enclosing model of ASD - see below - but the technology is still not in place to do this. Wouter, I am still not clear what you claim is a counterexample to what; maybe you could spell out what you mean in detail as an "answer" rather than as a terse "comment". | |
| Apr 11, 2013 at 14:33 | comment | added | Paul Taylor | Don't worry about it, Francois, I didn't take any offense! But the notion of AU is important and does deserve better coverage in the literature. So if you would like to study them (and publish your results!) then we would be very pleased. | |
| Apr 11, 2013 at 14:05 | comment | added | François G. Dorais | (Regarding the stability of free monoids, it wasn't my intent to "fault" anyone, it's a great question! In fact, I am very happy to hear that it is an open question, which actually resolves my initial dilemma, in a way.) | |
| Apr 11, 2013 at 14:01 | comment | added | François G. Dorais | Paul, my choice of word "mess" was not the best. I am very thankful to you and Milly for your work and I still hope that André publishes his proof. The "mess" was a description of the situation I was in a few years ago. I was trying to sort out these ideas and had been told about the existence arithmetic universes but I couldn't find any concrete information about them. I eventually gave up. Now that you and Milly have cleared much of the mess I was in, I will have to find some time to continue where I had left off... Thank you again! | |
| Apr 11, 2013 at 6:58 | comment | added | Wouter Stekelenburg | @Paul: A counterexample to the conjectures. I did specify the objects of my categories in the question: powers of $\mathbb N$ for the first and recursively enumerable set for the second. | |
| Apr 10, 2013 at 11:38 | comment | added | Paul Taylor | Wouter, what is a counterexample to what? You didn't specify the objects of the category in your question, but one might infer that they are just powers of N, so the category does not have quotients. In fact, there are at least three techniques for adding the objects whose shadows are outlined by the morphisms and I am optimistic that the result would have whatever you think are the appropriate properties. | |
| Apr 10, 2013 at 11:33 | comment | added | Paul Taylor | Francois, what is it that you regard as a mess? Maybe you can try to persuade Andre to write up Godel's theorem, but surely we should thank Milly for doing what she has done. Yes, there was ambiguity about whether an AU should have free monoids or just N, but the consensus now is for monoids. As to whether they are stable as a theorem, that is my "fault", but this is just an open conjecture like any other. | |
| Apr 9, 2013 at 16:20 | comment | added | Wouter Stekelenburg | So the answer to my second question is no, because the free arithmetical universal is a counterexample. | |
| Apr 9, 2013 at 16:08 | vote | accept | Wouter Stekelenburg | ||
| Apr 8, 2013 at 9:08 | comment | added | Paul Taylor | I should make it clear that there is no disagreement between Milly and me as to what properties an arithmetic universe must have: certainly the free monoids should be stable. If you are looking at them "from the inside", ie what you can do with an AU when you have one, that settles the question. The point is economy of what you need to check if you're constructing one, as I was in my 2005 CTCS/ENTCS paper. Once you have some "organic" "set theory" you can bootstrap useful stuff from parsimonious basic assumptions. However, I suspect that this question is still open. | |
| Apr 7, 2013 at 22:58 | comment | added | François G. Dorais | Thank you so much for writing this! I was very interested in all this a few years ago but I couldn't resolve some issues and I eventually (but reluctantly) just walked around them. The main one was exactly that: how much do you need to prove the stability of free monoids. Mind you, at that time, it wasn't even clear whether Joyal's (mythical) arithmetic universe had any free monoids beyond the nno. Anyway, if you, Maietti (or anyone else) figure this mess out, I really want to know! | |
| Apr 7, 2013 at 21:06 | history | edited | Paul Taylor | CC BY-SA 3.0 |
added 3569 characters in body
|
| Apr 7, 2013 at 15:53 | comment | added | Todd Trimble | Of course, one source for this is tac.mta.ca/tac/volumes/24/3/24-03abs.html | |
| Apr 7, 2013 at 15:28 | history | answered | Paul Taylor | CC BY-SA 3.0 |