Non-computability of solutions of certain equations on digital computers (2022)

Re:Non-computability of solutions of certain equations on di... by ogogmad on Sunday August 04, 2024 @11:49AM (#41154285)

A weaker but easier result is that the differentiation operator is uncomputable: Define f_t(x) = t arctan(x/t). As t -> 0, f_t -> 0. But notice that f'_t(0) = 1.

By contrast, the integration operator is computable. Why? Because a piece of code that defines a function f over the real numbers can be generalised to interval numbers (see "interval arithmetic") -- it then follows that the upper and lower Darboux sums are both computable. QED

[edit] Changed oo to 0.

[ Parent | on HN ]

Re:Non-computability of solutions of certain equations on di... by lisper on Sunday August 04, 2024 @11:58AM (#41154336)

Thanks!

I think you don't even need arctan for this. Just put one of Myhill's "bumps" at x=0 and shrink it down. That function approaches f(x)=0 for all x but its derivative at x=0 remains 1.

[ Parent | on HN ]

Re:Non-computability of solutions of certain equations on di... by ogogmad on Monday August 05, 2024 @03:07PM (#41164372)

The arctan has the advantage that it's differentiable infinitely many times over R.

[ Parent | on HN ]