Timeline for How can we define a denotational semantics for recursive functions?
Current License: CC BY-SA 4.0
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 2 at 14:43 | history | edited | David Young | CC BY-SA 4.0 |
added 99 characters in body
|
| Jan 26 at 19:05 | history | edited | David Young | CC BY-SA 4.0 |
added 2 characters in body
|
| Jan 17 at 2:40 | vote | accept | David Young | ||
| Aug 22, 2023 at 5:40 | comment | added | David Young | @MartinBerger That's a good point. I'll see about including that when I get a bit more time. Also, thank you for the pointer to the survey article by Ong. It has been very interesting. | |
| Aug 16, 2023 at 7:43 | comment | added | Martin Berger | @DavidYoung Your answer is fine, but I think it would be even better if the shortcomings of order-theoretic methods were mentioned. Basically order theoretic models are illuminating only for simple forms of computation. | |
| Aug 16, 2023 at 2:24 | comment | added | David Young | @MartinBerger I'm not fully sure I understand what you mean. Are you saying that I should include info about (the lack of) full abstraction in the answer, or is there something wrong? I sort of understand the full abstraction problem for PCF. I didn't intend to suggest that this semantics is fully abstract, only that it's adequate (though I didn't actually say "adequate", looking back). Thank you for the comment. I read some of your semantics answers recently and I've found them helpful. | |
| Aug 15, 2023 at 21:46 | comment | added | Martin Berger | Domain-theoretic like this is usually not precise, see the famous full-abstract problem for PCF. Luke Ong has written a survey article Correspondence between operational and denotational semantics: the full abstraction problem for PCF. The core issue is that (simple) domain-theoretic semantics don't rule out parallel evaluation, but PCF is a sequential language. | |
| Aug 11, 2023 at 12:34 | history | edited | kaya3 | CC BY-SA 4.0 |
MathJax, glorious MathJax
|
| Jul 12, 2023 at 17:43 | history | edited | David Young | CC BY-SA 4.0 |
typo
|
| Jul 5, 2023 at 13:25 | history | edited | David Young | CC BY-SA 4.0 |
deleted 1660 characters in body
|
| Jul 5, 2023 at 13:24 | comment | added | David Young | @MikeSpivey Ah, you're right. I was thinking of the continuous functions from the synthetic topology from Martin Escardo's Synthetic topology of data types and classical spaces. In that case, continuous functions are computable by definition (Sec 3.1). I'll remove that part of my answer. | |
| Jul 5, 2023 at 10:03 | comment | added | Mike Spivey | It's wrong to confuse continuous functions with computable ones: for example, consider the function in N_btm - - > N_btm that maps bottom to bottom and each number n to either 0 or 1 depending on whether the n'th Turing machine halts on a blank tape. That function is continuous because it is monotonic, but it isn't computable. | |
| Jul 4, 2023 at 15:47 | history | edited | David Young | CC BY-SA 4.0 |
added 124 characters in body
|
| Jul 4, 2023 at 15:05 | history | edited | David Young | CC BY-SA 4.0 |
deleted 30 characters in body
|
| Jul 4, 2023 at 7:00 | history | edited | David Young | CC BY-SA 4.0 |
added 84 characters in body
|
| Jul 4, 2023 at 6:44 | history | edited | David Young | CC BY-SA 4.0 |
added 50 characters in body
|
| Jul 4, 2023 at 4:46 | history | edited | David Young | CC BY-SA 4.0 |
[Edit removed during grace period]; added 851 characters in body
|
| Jul 4, 2023 at 4:38 | history | edited | David Young | CC BY-SA 4.0 |
[Edit removed during grace period]; added 851 characters in body
|
| Jul 4, 2023 at 4:29 | history | edited | David Young | CC BY-SA 4.0 |
[Edit removed during grace period]; added 851 characters in body
|
| Jul 4, 2023 at 4:16 | history | edited | David Young | CC BY-SA 4.0 |
[Edit removed during grace period]; added 8 characters in body
|
| Jul 4, 2023 at 4:06 | history | edited | David Young | CC BY-SA 4.0 |
added 2 characters in body
|
| Jul 4, 2023 at 3:54 | history | edited | David Young | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 4, 2023 at 3:49 | history | edited | David Young | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 3, 2023 at 23:00 | history | edited | David Young | CC BY-SA 4.0 |
added 13 characters in body
|
| Jul 3, 2023 at 22:18 | history | edited | David Young | CC BY-SA 4.0 |
added 5 characters in body
|
| Jul 3, 2023 at 21:54 | history | edited | David Young | CC BY-SA 4.0 |
deleted 1 character in body
|
| Jul 3, 2023 at 20:22 | history | edited | David Young | CC BY-SA 4.0 |
added 31 characters in body
|
| Jul 3, 2023 at 19:50 | history | edited | David Young | CC BY-SA 4.0 |
added 188 characters in body
|
| Jul 3, 2023 at 19:36 | history | answered | David Young | CC BY-SA 4.0 |