Hacker News Reader

Comment by myWindoonn | Hacker News Reader

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

View on HN

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.

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.

As opposed to classical reals which have a computable equivalence? (Hint: they don't)

But when working with reals we normally don't bother with computability. Whereas with computable numbers you don't even have anything else really.

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 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 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 - Encoding discrete quantum algebras in a hierarchy of binary words

Highly interesting.

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.

Reply on news.ycombinator.com