3 ms·

a) All functions from computable reals to computable reals are continuous. This makes sense, because an arbitrarily small input difference leading to an arbitra

by orlp 3y ago

a) All functions from computable reals to computable reals are continuous. This makes sense, because an arbitrarily small input difference leading to an arbitrarily large output difference is not a good basis for computation. You can still have discontinuities for discrete computable maps. b) Neither is equality computable for the reals. Nothing is lost here. c) Differentiation is computable for the functions of computable reals if you have a computable rate of convergence.

chromoblob 3y ago
How to do (c)? I tried to model the reals as lazily computed sequences of intervals with rational bounds where every next interval is subset of previous one, and couldn't write a higher-order differentiator function because on every step for a given input interval there is output interval with non-zero (in most cases) size and the differentiated function may contain quick enough oscillations that the derivative is unbounded, and thus the derivative will stay unbounded no matter what you do. What do you mean by rate of convergence?
- orlp 3y ago
  https://en.wikipedia.org/wiki/Modulus_of_convergence https://en.wikipedia.org/wiki/Modulus_of_convergence
  - chromoblob 3y ago
    (I assume you refer to the sequence of reals that is used to compute the limit in the definition of derivative) But is there a way to somehow construct this modulus automatically for some functions? And if there isn't, then isn't requiring manual input of the modulus like just requiring manual input of the derivative itself? Can you typically find the modulus manually more easily than the derivative?
    - orlp 3y ago
      > But is there a way to somehow construct this modulus automatically for some functions? In a sense. You would end up with https://en.wikipedia.org/wiki/Automatic_differentiation https://en.wikipedia.org/wiki/Automatic_differentiation. The amount of functions you can construct in this manner is massive, along with their derivatives, but it is not an operator that given an arbitrary computable function gives you its derivative.
      - chromoblob 3y ago
        Thank you.

by orlp 3y ago

chromoblob 3y ago

How to do (c)? I tried to model the reals as lazily computed sequences of intervals with rational bounds where every next interval is subset of previous one, and couldn't write a higher-order differentiator function because on every step for a given input interval there is output interval with non-zero (in most cases) size and the differentiated function may contain quick enough oscillations that the derivative is unbounded, and thus the derivative will stay unbounded no matter what you do. What do you mean by rate of convergence?

orlp 3y ago
https://en.wikipedia.org/wiki/Modulus_of_convergence https://en.wikipedia.org/wiki/Modulus_of_convergence
- chromoblob 3y ago
  (I assume you refer to the sequence of reals that is used to compute the limit in the definition of derivative) But is there a way to somehow construct this modulus automatically for some functions? And if there isn't, then isn't requiring manual input of the modulus like just requiring manual input of the derivative itself? Can you typically find the modulus manually more easily than the derivative?
  - orlp 3y ago
    > But is there a way to somehow construct this modulus automatically for some functions? In a sense. You would end up with https://en.wikipedia.org/wiki/Automatic_differentiation https://en.wikipedia.org/wiki/Automatic_differentiation. The amount of functions you can construct in this manner is massive, along with their derivatives, but it is not an operator that given an arbitrary computable function gives you its derivative.
    - chromoblob 3y ago
      Thank you.