3 ms·

There exists a notion of "computable analysis", based on the delightful fact that Turing machines (or other Turing-complete enumerable computers) can be viewed

There exists a notion of "computable analysis", based on the delightful fact that Turing machines (or other Turing-complete enumerable computers) can be viewed as computing real numbers. These so-called computable reals are a little limited, but still usable for most tasks [0]. [0] https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis

chx 8y ago
It's a real PITA to work with computable numbers because even their equivalence is not computable. Also, the field is really young. It was only in 2000 that Weihrauch has proven that every computable real function is continuous.
- myWindoonn 8y ago
  Their equivalence can be given by a Turing machine, though, so the non-computability comes directly from the Halting Problem. This is worth mentioning because some folks get the incorrect impression that it's not possible to write a program that, say, outputs whether two computable reals are equal to each other. It is possible! But the program might not halt. I shouldn't trivialize the difficulty. It is a PITA. I remember my first foray into this; I wrote a program which computed sqrt(8), which worked fine, and then another program which computed sqrt(8)^2, which didn't halt. The edges are tricky.
- voxl 8y ago
  As opposed to classical reals which have a computable equivalence? (Hint: they don't)
  - chx 8y ago
    But when working with reals we normally don't bother with computability. Whereas with computable numbers you don't even have anything else really.
aeneasmackenzie 8y ago
They are usable for all tasks. What are you going to do with a number you can't compute? Nothing, because you can't do anything with it.
no_identd 8y ago
Originally I wanted to make a point here about Interactive Computation, the strong Church-Turing hypothesis and persistent Turing Machines, however, while checking on the latest research in that area before doing so, I found the following paper: https://arxiv.org/abs/1702.06000 https://arxiv.org/abs/1702.06000 TE Raptis - 'Viral' Turing Machines, Computation from Noise and Combinatorial Hierarchies Which gets cited by the following paper by the same author, which cites the OP paper(!), AND elaborates on it: https://arxiv.org/abs/1805.06301 https://arxiv.org/abs/1805.06301 TE Raptis - Finite Information Numbers through the Inductive Combinatorial Hierarchy Which itself gets yet another follow on by the same author: https://arxiv.org/abs/1806.01637 https://arxiv.org/abs/1806.01637 - Encoding discrete quantum algebras in a hierarchy of binary words Highly interesting.

chx 8y ago

It's a real PITA to work with computable numbers because even their equivalence is not computable. Also, the field is really young. It was only in 2000 that Weihrauch has proven that every computable real function is continuous.

myWindoonn 8y ago
Their equivalence can be given by a Turing machine, though, so the non-computability comes directly from the Halting Problem. This is worth mentioning because some folks get the incorrect impression that it's not possible to write a program that, say, outputs whether two computable reals are equal to each other. It is possible! But the program might not halt. I shouldn't trivialize the difficulty. It is a PITA. I remember my first foray into this; I wrote a program which computed sqrt(8), which worked fine, and then another program which computed sqrt(8)^2, which didn't halt. The edges are tricky.
voxl 8y ago
As opposed to classical reals which have a computable equivalence? (Hint: they don't)
- chx 8y ago
  But when working with reals we normally don't bother with computability. Whereas with computable numbers you don't even have anything else really.

aeneasmackenzie 8y ago

They are usable for all tasks. What are you going to do with a number you can't compute? Nothing, because you can't do anything with it.

no_identd 8y ago

Originally I wanted to make a point here about Interactive Computation, the strong Church-Turing hypothesis and persistent Turing Machines, however, while checking on the latest research in that area before doing so, I found the following paper: https://arxiv.org/abs/1702.06000 https://arxiv.org/abs/1702.06000 TE Raptis - 'Viral' Turing Machines, Computation from Noise and Combinatorial Hierarchies Which gets cited by the following paper by the same author, which cites the OP paper(!), AND elaborates on it: https://arxiv.org/abs/1805.06301 https://arxiv.org/abs/1805.06301 TE Raptis - Finite Information Numbers through the Inductive Combinatorial Hierarchy Which itself gets yet another follow on by the same author: https://arxiv.org/abs/1806.01637 https://arxiv.org/abs/1806.01637 - Encoding discrete quantum algebras in a hierarchy of binary words Highly interesting.