17 votes

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

I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think. The community of people who work on exact real arithmetic consists of ...
user avatar
  • 26.6k
16 votes
Accepted

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

This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result ...
user avatar
  • 26.6k
13 votes

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

I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings. First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \...
user avatar
  • 26.6k
10 votes

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

In general, people always care about floating point errors. However I disagree with Andrej, and I do not think that floats are preferred to arbitrary precision reals (for the most part) because of ...
user avatar
  • 13.2k
7 votes
Accepted

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

No, it is not decidable. A good heuristic to answer such questions is the following: every computable map is continuous. If you could decide whether $f(x) = 0$ for all $x \in \mathbb{C}$, then the ...
user avatar
  • 26.6k
4 votes

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

Computing an 'infinite' object is usually defined based on Turing machines with one-way output tape; cmp. Section 2.1 in [Weihrauch'00]. This also asserts closure under composition. [Turing'36] first ...
user avatar
3 votes

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

Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and ...
user avatar
  • 1,081
3 votes
Accepted

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

The first theorem of the form you are asking about was proved by Y. Moschovakis in Notation systems and recursive ordered fields, Compositio Mathematica 17:40–71 (1965). Then in the context of Type ...
user avatar
  • 26.6k
3 votes

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

To turn my comment into an answer... Andrej Bauer in this post makes the parenthetical claim An important theorem states that any two representations of reals which are acceptable are actually ...
user avatar
3 votes
Accepted

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

No, it is undecidable. Imagine a TM that outputs a sequence $0.1111\ldots$ that may be finite or not. If it is finite, the conversion algorithm should give some fraction like $\frac{11\ldots11}{10\...
user avatar
3 votes

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

How about, $x\in[0,1]$ is computable if there is a TM $M$ which, on input $n\in\mathbb{N}$, prints the first $n$ digits of the decimal expansion of $x$ and then halts. Edit (13-Jul-2021). This ...
user avatar
  • 10k
3 votes

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

The standard solution is to require write only tape if you want to use TTE. Obviously you can have RW work tapes. Another solution is information theoretic (domain theory) and says that you get ...
user avatar
  • 21.3k
2 votes

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

One solution is what Radu GRIGore suggested, namely requiring that every digit becomes fixed after some (finite) number of steps. Of course, this comes with the practical issue that you never know ...
user avatar
1 vote
Accepted

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

I guess I have an alternative solution. Let $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$ be computable. Define $$ h(u) = v \mbox{ iff } f(u\Sigma^{\omega}) = \{v\} \mbox{ with $u$ minimal} $$ ...
user avatar
  • 1,947

Only top scored, non community-wiki answers of a minimum length are eligible