Timeline for Can you tell if you have escaped from a recursive definition?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 18, 2023 at 21:58 | comment | added | The Amplitwist |
The link to research.microsoft.com in the previous comment seems to be broken, but a copy of the PDF is saved on the Wayback Machine
|
|
| Mar 28, 2010 at 5:18 | vote | accept | S. Donovan | ||
| Mar 28, 2010 at 4:10 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 173 characters in body
|
| Mar 28, 2010 at 4:07 | comment | added | Joel David Hamkins | This is a deep philosophical question, and several titans in computability/complexity theory have come down on the side of saying that there is no answer to the question of when are two algorithms the same. See this essay research.microsoft.com/en-us/um/people/gurevich/opera/192.pdf by Blass, Dershowitz and Gurevich. | |
| Mar 28, 2010 at 3:58 | comment | added | S. Donovan | I'm not really worried about how complex it it or how long ti would take expect as far as that might tell me if the algorithms are in some sense the "same" I guess I'm looking for ways to define when algorithms are the same. Is that taken up in computational complexity theory? | |
| Mar 28, 2010 at 3:50 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |