Timeline for Internal operations on uncomputable functions
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 20, 2017 at 12:01 | vote | accept | kakaz | ||
| Nov 12, 2017 at 19:53 | comment | added | kakaz | @Noah - of course it is. But I am asking about cases where there's some hierarchy defined, and we have a set of operations which descent down this hierarchy. So Your example may be a trivial one, but definitely there are interesting ones as well. | |
| Nov 12, 2017 at 18:51 | comment | added | Noah Schweber | The union, or intersection, or etc. of two arbitrarily complicated sets can be arbitrarily simple - for example, take any set and its complement, or any set and itself. Is this the sort of thing you're looking for? | |
| Nov 12, 2017 at 14:05 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Nov 12, 2017 at 13:33 | history | edited | Martin Sleziak | CC BY-SA 3.0 |
Removed deprecated (abstract-algebra) tag - see the tag info: https://mathoverflow.net/tags/abstract-algebra/info (if there are some other suitable tags, choose them instead.)
|
| Nov 12, 2017 at 12:43 | comment | added | kakaz | Yes, definitely it is related, but mainly I am asking about nontrivial transformations which takes arguments inside some level and return something at lower level. Another example: suppose you have two NP time problems, and a process depending on the solutions of it. For which processes resolution may be in P? Is it possible to cancel out NP hardened processes and get something simpler? | |
| Nov 12, 2017 at 12:38 | history | edited | kakaz | CC BY-SA 3.0 |
added 154 characters in body
|
| Nov 12, 2017 at 12:34 | comment | added | Joel David Hamkins | The hierarchy of Turing degrees may fulfill some of what you request for a larger hierarchy of non-computability. | |
| Nov 12, 2017 at 12:34 | comment | added | kakaz | Yes, of course, my mistake, but general question is still valid, and generalisations as well. Is it interesting question? | |
| Nov 12, 2017 at 12:31 | comment | added | Joel David Hamkins | The Ackermann function is computable. It is not primitive recursive and it grows faster than any primitive recursive function, which may be what you had meant, but it is computable. | |
| Nov 12, 2017 at 10:14 | history | asked | kakaz | CC BY-SA 3.0 |