Skip to main content
1 of 3
kakaz
  • 1.6k
  • 2
  • 25
  • 35

Internal operations on uncomputable functions

  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, beying internal only inside shells of similar growth?

  2. Or relaxing a bit, it returns an uncomputable 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 uncomputable functions:

Let A be Ackerman function, so it is uncomputable ( it grows faster than any computable function). Obviously A + A is another uncomputable function, equivalent to oryginal 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.

kakaz
  • 1.6k
  • 2
  • 25
  • 35