Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computable-analysis]

computability and complexity in real or complex analysis

2
votes
0answers
28 views

Semidecidable properties of computable reals

By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
0
votes
0answers
14 views

What is the scaling of automatic differentiation compared to symbolic and numerical differentiation?

Automatic differentiation is a set of techniques to numerically evaluate the derivative of a function. Quoting from Wikipedia (emphasis mine): These classical methods run into problems: symbolic ...
0
votes
2answers
70 views

What is the relationship between two definitions of Turing-computability of a partial function?

When one wants to know that whether a partial function $f \colon \Sigma^{*} \supsetneq \mathrm{dom}(f) \rightarrow \Sigma^{*}$ is Turing-computable, there are two methods that I think they are both ...
9
votes
2answers
217 views

Decidable properties of computable reals

Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true? Does this correspond in some direct way to ...
2
votes
2answers
97 views

What does Sigma notation mean, in the context of computability of functions?

I was reading a paper on the computability of AIXI [1] and came across the notion of $\Sigma^0_n$-computability for real-valued functions in section 2.3. I'd like to read about this in more detail. ...
3
votes
2answers
145 views

Is Newton's Method to compute the zeros of a function an algorithm?

Looking for Newton's method in Wikipedia, I read the following: In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, is ...
14
votes
2answers
468 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with ...
2
votes
1answer
73 views

Poly-time computability of inversion of poly-time real functions

At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases: Let $INV_1$ be the operator that maps a one-to-one function $f:[0,1]\...
4
votes
1answer
403 views

How does automatic differentiation work?

What is the intuitive idea behind automatic differentiation? If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f? ...
6
votes
3answers
993 views

Is a PDA as powerful as a CPU?

This is a question I have stumbled upon in my exam revision and I find it intriguing: My computer is blue and it has a massive graphics card and a DVD and every- thing so which is more powerful: my ...
11
votes
1answer
517 views

A continuous optimization problem that reduces to TSP

Suppose I am given a finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. ...