# Questions tagged [computable-analysis]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
73 views

### Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain

The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of ...
393 views

### A definition of computable numbers that requires to “wait an infinite amount of time” to get the correct result; how to make this precise

Consider the following definition: A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its ...
595 views

### Computation of reals: floating point vs TTE vs domain theory vs etc

Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised ...
130 views

### Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

"any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference where may proof of this theorem be found, and what is the the computational ...
85 views

### For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

Any computable number may have different representations of finite length . For example,$\sqrt{2}$ may be represented as root of equation, or as a (shortest for a universal Turing Machine)program of ...
245 views

### Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$ in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm? ...
357 views

### How to judge the definition of computational complexity of reals is natural or suitable?

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
1k views

### What is a reasonable representation/encoding of objects? [closed]

Question What is a reasonable representation of objects (for computability)? What is the criteria that we should apply to see if a representation is reasonable? This answer by Andrej suggests that ...
108 views

### Delimiting the roots of a polynomial

Given a polynomial of degree $n$, namely, $y=a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$, with $a_i\in \mathbb{R}$, I would to know if it is possible to compute a rational number $K$ such that the ...
958 views

### Decidability of transcendental numbers

I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help. My question is whether it is known that ...
293 views

### Concerning decidability of a problem on real numbers [closed]

This question is an outgrowth of a certain maths problem I've been thinking about. Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
3k views

### Functions that typed lambda calculus cannot compute

I just want to know some examples of the functions that can be computed by the untyped lambda calculus but not by typed lambda calculi. As I am a beginner, some reiteration of background information ...
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers? The classical algorithm for fast Fourier transforms, ...