Timeline for Computability of sets of fixed point values
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2016 at 21:47 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 345 characters in body
|
| Oct 4, 2016 at 19:36 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 9 characters in body
|
| Oct 4, 2016 at 18:43 | comment | added | Andrés E. Caicedo | This reminds me of a cute paper I saw recently, John Case & Michael Ralston, Non-obfuscated unprovable programs & many resultant subtleties, Log. Methods Comput. Sci. 12 (2016), no. 2, 2:2, 25 pp. lmcs.episciences.org/1634, which deals with a very similar issue (and relates it to provability). | |
| Oct 4, 2016 at 17:28 | answer | added | Joel David Hamkins | timeline score: 3 | |
| Oct 4, 2016 at 15:32 | comment | added | Jason Rute | I am pretty sure that using the fact that $\{e : \varphi_e \text{ is total}\}$ is $\Pi^0_2$ complete, one can also show that the set of fix points for a given total computable $F$ is $\Pi^0_2$ and moreover there exists some total computable $F$ such that the set of $F$-fixed points is $\Pi^0_2$ complete. (I don't however know if every $\Pi^0_2$ set is the set of fixed points of some total computable $F$. That is a more difficult.) | |
| Oct 4, 2016 at 9:26 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 30 characters in body
|
| Oct 4, 2016 at 9:13 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 9 characters in body
|
| Oct 4, 2016 at 9:06 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 9 characters in body
|
| Oct 4, 2016 at 8:58 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
deleted 6 characters in body
|
| Oct 4, 2016 at 8:51 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 2 characters in body
|
| Oct 4, 2016 at 8:43 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 100 characters in body
|
| Oct 4, 2016 at 8:31 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 100 characters in body
|
| Oct 4, 2016 at 7:53 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
deleted 100 characters in body
|
| Oct 4, 2016 at 4:44 | history | edited | Giovanni Viglietta | CC BY-SA 3.0 |
added 102 characters in body
|
| Oct 4, 2016 at 4:38 | history | asked | Giovanni Viglietta | CC BY-SA 3.0 |