2
$\begingroup$

  1. Is there know set of operations for which uncomputable functions are, let's name it down-unclosed? I mean a set of operations which takes two ( or more) uncomputable functions and return computable function? It is obvious it depends on certain property, like rates of growth, so are this hypothetical internal operations structured like onion, being internal only inside shells of similar growth? So what is known for other classes of functions? non primitive recursive (NPR)? For primitive recursive answer is known.

  2. Or relaxing a bit, it returns an uncomputable ( or NPR) function, which grows much slower?

  3. Is there any general notion describing such relationships ( "down-unclosure" under set of operations in bigger set which has built in order?) Maybe category abstract nonsense is ready defined?

Example regarding not primitive recursive function:

Let A be Ackerman function, so it is not primitive recursive ( it grows faster than any primitive recursive function). Obviously A + A is another NPR function, equivalent to original one, and similar for multiplication or exponents etc. But $$A/A$$ looks like quite normal computable function, an probably there are variants like linear combinations fraction or maybe even complicated functional composition on arguments ( for example $$A/(A°g)$$ where g is linear function and ° means function composition, so I mean Ackerman fraction of two functions, one of them with argument shifted $$x \to ax+b$$).

Down-unclosure:

Example of down-unclosure is visible in various areas. There are a proof techniques based on lowering some parameters in the bounded from below set ( for example in natural numbers, contraction of volumes, or more generally measure of sets etc ), various analytical techniques based on control of remainder growth, or even set theoretic techniques based on "almost all" elements which may be seen as certain types of such "down-unclosure" trick.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Nov 12, 2017 at 12:31
  • $\begingroup$ Yes, of course, my mistake, but general question is still valid, and generalisations as well. Is it interesting question? $\endgroup$
    – kakaz
    Commented Nov 12, 2017 at 12:34
  • 2
    $\begingroup$ The hierarchy of Turing degrees may fulfill some of what you request for a larger hierarchy of non-computability. $\endgroup$
    – Joel David Hamkins
    Commented Nov 12, 2017 at 12:34
  • $\begingroup$ 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? $\endgroup$
    – kakaz
    Commented Nov 12, 2017 at 12:43
  • 1
    $\begingroup$ 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? $\endgroup$
    – Noah Schweber
    Commented Nov 12, 2017 at 18:51

1 Answer 1

Reset to default
4
$\begingroup$

The jump inversion theorem (Friedburg 1957) shows that any Turing degree $d$ above the halting problem is the jump of another degree $d=b'$, which means that $d$ is Turing equivalent to the halting problem relative to $b$.

Friedburg's original construction can be viewed as a specific map from any sufficiently non-computable set $d$ to a strictly simpler set $b$, with the property that $d$ is Turing equivalent to the halting problem relative to $b$.

There are numerous generalizations and refinements of the jump inversion phenomenon in computability theory.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .