Timeline for Defining computable functions categorically
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2018 at 20:30 | history | edited | Peter Gerdes | CC BY-SA 4.0 |
added 72 characters in body
|
| May 18, 2018 at 20:28 | comment | added | Peter Gerdes | Well then I misunderstood the question but maybe other people will as well so i will put that note in my answer. | |
| May 17, 2018 at 8:16 | comment | added | N. Virgo | So I was positively looking for a definition that would depend on the structure of the relationships between elements of the set (according to operations defined on them), rather than on the elements of the set itself. (Andrej Bauer's answer looks like exactly that - I need time to digest it though.) | |
| May 17, 2018 at 8:14 | comment | added | N. Virgo | @PeterGerdes in your first comment you say, "I won't get the same answers about what sets of rationals are computable if I consider the rationals under the normal +, * structure or under some structure with very different operations (speaking loosely)". This is a good description, I think, of what I was asking for. In category theory (speaking loosely) those two things would be considered different categories - it doesn't really matter that the underlying set is considered to be the rational numbers in both cases. | |
| May 16, 2018 at 21:27 | comment | added | Peter Gerdes | Ok, sneaky is unfair. Notions like this are certainly interesting and mathematically useful but my sense of the original question was a desire to have a unique rigorous notion of computability for binary trees...not the structure of binary trees under operations x,y and z since that question introduces exactly the same kind of judgement about appropriate choices that motivated the desire to avoid specifying a coding. In some sense this comes down to a question of interpretation of the question. | |
| May 16, 2018 at 21:19 | comment | added | Peter Gerdes | But the problem is that this isn't a definition of what computability means for a given collection of objects but rather (something like) a particular way to uniquely specify a kind of computability using a choice of relations. In particular, if I understand what you said correctly, I won't get the same answers about what sets of rationals are computable if I consider the rationals under the normal +, * structure or under some structure with very different operations (speaking loosely). I'd regard this as just a sneaky way of specifying a choice of coding. | |
| May 16, 2018 at 16:47 | comment | added | Andrej Bauer | Coding problems exist only for as long as one thinks of coding of bare sets. But as soon as you think of coding in a larger context, and you ask about coding of structures, the problem disappears. See my answer. | |
| May 16, 2018 at 15:19 | comment | added | Gerhard Paseman | Indeed, coding or some other form of interpretation performed on the putative category needs to be done in order for computable to have meaning. One has to start with declaring some functions as computable (usually successor and at least one constant which may be "unnatural", and projection functions which in a universal algebra context seem "natural") and closing them under some special forms of composition, which forms and functions may be arbitrary but represent some aspects of computability. Gerhard "Thinks Your Response Is Good" Paseman, 2018.05.16. | |
| May 16, 2018 at 14:26 | review | Low quality posts | |||
| May 16, 2018 at 17:43 | |||||
| May 16, 2018 at 13:30 | history | answered | Peter Gerdes | CC BY-SA 4.0 |