Timeline for Computability of sets of fixed point values
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2016 at 19:05 | comment | added | Giovanni Viglietta | Yes, but as I'm trying to point out since the beginning, some of these questions do not depend on unimportant syntactic details. For instance, that the set of fixed points of x+k cannot be recursive is still a remarkable fact. Hence the question: can we extend this result? Can we characterize the functions whose fixed point sets have some inherent complexity? Anyway, the construction that my friend showed me is not trivial and I do not know if I am allowed to publish it... All I can do is invite him to contribute to this discussion directly. Sorry... | |
| Oct 5, 2016 at 14:28 | comment | added | Joel David Hamkins | But also, to my way of thinking about it, if the result does indeed depend on the way we number the programs, then as I mentioned earlier, it suggests that the question is not actually natural, but is instead depending on unimportant syntactic details. | |
| Oct 5, 2016 at 13:40 | comment | added | Joel David Hamkins | It would be kind of you to post the construction. It is fine in such a case to post an answer to your own question. | |
| Oct 5, 2016 at 13:30 | comment | added | Giovanni Viglietta | Okay, a friend showed me one such numbering. Now everything about x+1 is settled: the set of its fixed points is never recursive, but could be r.e. or not r.e. depending on the numbering. However, the general problem remains open and very interesting, IMHO. | |
| Oct 4, 2016 at 23:14 | comment | added | Joel David Hamkins | Ah, sorry for the confusion. | |
| Oct 4, 2016 at 23:09 | comment | added | Giovanni Viglietta | No, the updated question also asks for an admissible numbering that makes the set recursively enumerable. Can you show me any? | |
| Oct 4, 2016 at 23:03 | comment | added | Joel David Hamkins | recursively enumerable is the same thing as c.e. (=computably enumerable). So I think I've answered your updated question. | |
| Oct 4, 2016 at 23:02 | comment | added | Giovanni Viglietta | Sorry, I meant 'recursively enumerable'. I corrected my comment. | |
| Oct 4, 2016 at 23:00 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 30 characters in body
|
| Oct 4, 2016 at 23:00 | comment | added | Joel David Hamkins | Yes, that's what my answer already does. My answer is that for my numbering, it isn't recursively enumerable. It is co-c.e. and $\Pi^0_1$-complete, and hence not c.e. | |
| Oct 4, 2016 at 22:56 | comment | added | Giovanni Viglietta | I read the Update. Yes, I happened to know that part, too... :D Now, can you find a numbering that makes the set recursively enumerable? | |
| Oct 4, 2016 at 22:41 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 1221 characters in body
|
| Oct 4, 2016 at 20:58 | comment | added | Joel David Hamkins | Well, the fact that I haven't heard of the result certainly doesn't mean that it hasn't been looked at by others. | |
| Oct 4, 2016 at 20:37 | comment | added | Giovanni Viglietta | That was my initial thought as well. But on the other hand, the theorem I gave above (i.e., if all orbits have finite complement, then the fixed point set is not recursive) is pretty general, and applies to $\lambda x.x+1$ and any admissible numbering. This suggests that there may be something deeper going on. Are you telling me that this theorem was not known, and that there is no general theory that includes it? | |
| Oct 4, 2016 at 20:35 | comment | added | Joel David Hamkins | Because the question is not just about the function that the index computes, but it is allowed to ask about the index itself. That is why Rice's theorem, for example, does not apply here. For example, for some enumerations it may be that odd numbers always compute the empty function, and in this case, to decide fixed points of the function $f(i)=2i+1$ will be equivalent to the empty-function problem. | |
| Oct 4, 2016 at 20:32 | comment | added | Andrej Bauer | The acceptable numberings of partial computable functions are pretty robust, why do you think the answers may depend? For instance, the indices of the fixed points of $\lambda x . x + 1$, how could they depend on the numbering in an essential way? | |
| Oct 4, 2016 at 20:04 | comment | added | Joel David Hamkins | I think that if you are looking at specific functions like that, the answer could depend on the particular way that you represent computable functions by their indices. That is, the answers in those cases may depend on what are usually otherwise considered irrelevant syntactic details. | |
| Oct 4, 2016 at 19:49 | comment | added | Giovanni Viglietta | Yes, this is basically what I already knew, because both Rogers and Odifreddi have this exercise. But my question was more general. Let us forget about pathological functions and take, for instance, $\lambda x.x+1$. I can prove that the set of fixed point values of this $f$ is not recursive. Is it recursively enumerable? What about $\lambda x.x+2$? Are there general theorems about the fixed point values of these functions? | |
| Oct 4, 2016 at 17:59 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
edited body
|
| Oct 4, 2016 at 17:28 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |