Timeline for Is there a non self-referencing non-computable function?
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2014 at 3:06 | history | edited | Andrés E. Caicedo |
edited tags
|
|
| Nov 12, 2009 at 20:01 | answer | added | Richard Dore | timeline score: 1 | |
| Nov 10, 2009 at 13:59 | vote | accept | Manuel Araoz | ||
| Nov 9, 2009 at 14:07 | answer | added | sdcvvc | timeline score: 13 | |
| Nov 9, 2009 at 5:40 | comment | added | Reid Barton | It seems that your issue is not with properties of the functions themselves, but properties of the proofs of uncomputability, is that right? You keep wording your comments as referring to (e.g.) "mundane functions", but I cannot imagine a function more mundane than determining whether a polynomial has integer solutions. | |
| Nov 9, 2009 at 3:29 | comment | added | Manuel Araoz | I tend to see this self-referencing problem in every non-computable function I know, and wondered if a more "mundane" function existed that satisfied this awesome property of being beyond computers' reach. | |
| Nov 9, 2009 at 3:28 | comment | added | Manuel Araoz | I'm sorry for my lack of appropriate language. With "artificial", I intended meaning that OK, it's true that Halt is not computable because if a program existed that computed it, and you evaluated it on its own program number, a contradiction would occur, but this seems a very special and self-referencing case. I mean, it's not a case were one would usually use Halt if it were computable. In fact (I may be wrong here, please correct me), Halt(x,y) function should be computable for many values of x and y... | |
| Nov 8, 2009 at 21:56 | answer | added | Martin Lackner | timeline score: 2 | |
| Nov 8, 2009 at 17:38 | answer | added | Bakh | timeline score: 2 | |
| Nov 8, 2009 at 9:09 | comment | added | David Eppstein | I also don't see what you mean by artificial. It is very reasonable to ask how to detect infinite loops in programs, just as some systems detect other kinds of bugs such as uninitialized variables, array out of bounds, etc. | |
| Nov 8, 2009 at 9:03 | answer | added | Boris Bukh | timeline score: 20 | |
| Nov 8, 2009 at 5:06 | answer | added | Harrison Brown | timeline score: 2 | |
| Nov 8, 2009 at 5:01 | answer | added | Eric Wofsey | timeline score: 7 | |
| Nov 8, 2009 at 4:30 | answer | added | David E Speyer | timeline score: 5 | |
| Nov 8, 2009 at 4:23 | answer | added | Darsh Ranjan | timeline score: 5 | |
| Nov 8, 2009 at 4:23 | comment | added | Darsh Ranjan | I have no idea what you mean by "artificial" here, but I'll attempt to answer this anyway...(below) | |
| Nov 8, 2009 at 4:03 | history | asked | Manuel Araoz | CC BY-SA 2.5 |