Timeline for Why does Weihrauch reducibility make use of multi-functions?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27 at 10:34 | comment | added | Peter Gerdes | @JoeMiller So is it correct to say that if you limit yourself to normal functions you practically can't analyize the difficulty of problems like WKL without limiting yourself to one particular form (eg leftmost path...which may not have right features). Ok, thats better. No I wonder if it's merely more elegant or actually lets you prove results that would be hard to prove by looking for a Weirach reduction for some rule giving a solution. | |
| Apr 4 at 7:29 | comment | added | Gro-Tsen | While it doesn't exactly answer your question, I recommend Kihara's paper “Rethinking the notion of oracle”, which considers all sorts of kinds of reductions (oracles you can only use once vs, oracles you can use repeatedly; functions vs. partial functions vs. multifunctions vs. “extended predicates”; on $\mathbb{N}$ vs. on $\mathbb{N}^{\mathbb{N}}$; and so on), and give different points of view on each. I think it's very enlightening. | |
| Apr 3 at 18:42 | answer | added | Sam Sanders | timeline score: 4 | |
| Apr 3 at 15:08 | vote | accept | Peter Gerdes | ||
| Apr 2 at 13:16 | answer | added | Arno | timeline score: 11 | |
| Apr 2 at 11:05 | comment | added | Joe Miller | @NoahSchweber is right. For example, how would you translate WKL into a Weihrauch problem? It should take a tree in $2^{<\omega}$ to an infinite path through the tree. That's a partial multifunction. | |
| Apr 1 at 22:48 | comment | added | Noah Schweber | Since problems don't generally have unique solutions, you need multifunctions (that is, you represent principles as multifunctions) for anything reverse-math-flavored. | |
| Apr 1 at 21:17 | history | asked | Peter Gerdes | CC BY-SA 4.0 |