2022 Developer Survey is open! Take survey.

Questions tagged [computable-analysis]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
85 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 ...
user avatar
  • 1,947
2 votes
5 answers
411 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 ...
user avatar
  • 1,947
19 votes
3 answers
612 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 ...
user avatar
0 votes
2 answers
145 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 ...
user avatar
-1 votes
1 answer
86 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 ...
user avatar
4 votes
1 answer
260 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? ...
user avatar
11 votes
2 answers
371 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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
  • 21.3k
1 vote
1 answer
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 ...
user avatar
  • 111
13 votes
3 answers
1k 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 ...
user avatar
  • 348
1 vote
1 answer
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 ...
user avatar
12 votes
6 answers
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 ...
user avatar
18 votes
2 answers
7k views

Complexity of computing the discrete Fourier transform?

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, ...
user avatar
  • 22.8k
2 votes
0 answers
81 views

mean/integral, except where positive differences between values and "mean" are weighted differently from negative differences?

Given a curve $f(x)$ (for $x \in [0,1]$), and a line $y=a$, let $U$ be the total area below $f$ and above $a$, and let $L$ be the total area above $f$ and below $a$. If $L=U$, this means that $a =\...
user avatar
  • 21
6 votes
2 answers
497 views

Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis. A very general question: Most algorithms compromise of ...
user avatar
  • 1,145
1 vote
1 answer
157 views

Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

Let's say I had an optimization problem $$ \min_{x \in D} f(x) $$ Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist. Imagine I had a ...
user avatar
  • 113
43 votes
3 answers
4k views

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Background The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
user avatar
  • 21.3k
27 votes
6 answers
2k views

How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
user avatar
  • 5,070
4 votes
3 answers
547 views

What applications of Cantor space are there?

Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic? John Tucker's page Computation on Topological ...
user avatar