Skip to main content
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.)
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
  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, beyingbeing internal only inside shells of similar growth? So what is known for other classes of functions? non primitive recursive ( NPRNPR)? 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 oryginaloriginal 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.

  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? 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 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.

  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.

added 154 characters in body
Source Link
kakaz
  • 1.6k
  • 2
  • 25
  • 35
  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? 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 uncomputable functionsnot primitive recursive function:

Let A be Ackerman function, so it is uncomputablenot primitive recursive ( it grows faster than any computableprimitive recursive function). Obviously A + A is another uncomputableNPR 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.

  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.

  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? 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 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.

Source Link
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.