Comment by TheNewAndy | Hacker News Reader

Comment by TheNewAndy | Hacker News Reader

Parent Full thread

I believe you are correct, however I am struggling to see how.

If you have the time to help me with my understanding then I would appreciate it.

I'm looking at wikipedia's formal definition, which says that for x to be computable, you need to provide a function from naturals to integers such that if you pick a denominator of a fraction (n), this function can give the numerator such that (f(n)-1)/n and (f(n)+1)/n end up straddling the value which is computable.

So, for an integer N, you make f(x) = xN then (f(n)-1)/n = N-(1/n) and (f(n)+1)/n = N+(1/n).

Therefore, for any integer N, it is computable.

Now, what is stopping me from doing something similar with a real?

If I say: f(x) = floor(xN)

Now (f(n)-1)/n = floor(n*N)-(1/n)

It is at this point where I realise I need to go to bed and sleep. If you see this and have the time to explain to me where it falls apart with reals, then I will be most happy. To be clear - I'm quite sure I am wrong, and this isn't me being passive aggressive about it.

You were looking at the definition of a computable real number [1]. The issue there is whether you can approximate the number arbitrarily well. An issue that is nonexistent in integers, as you note in

> Therefore, for any integer N, it is computable.

> If I say: f(x) = floor(xN)

For many definitions of a real, it's not at all clear whether you can compute this f(x). The ability to compute f already amounts to being able to approximate f arbitrarily well. For example, for Chaitin's number, you cannot compute your f() except for a few small values of N.

[1] https://en.wikipedia.org/wiki/Computable_number

Thanks for your reply - and I probably would have missed it except by complete chance.

I still don't think it has properly clicked, because the function "f(x) = xN" still needs me to know what N is - despite it being an integer.

For example, let's suppose that you manage to have a conversation with God and you discover that BB(100) has the value of 42, and Chaitlin's number is 1/2.

Does Chaitlin's number suddenly become computable? My intuition is that it remains uncomputable, but maybe my intuition is wrong... I guess by the definition, it is computable, but you can't prove it.

I'm also struggling with the reciprocal of BB(100). This is rational, so maybe it too is computable.

I guess I am struggling with the lack of a constructive proof and what that means - it is like we are saying "there exists an algorithm to do X, but the algorithm can't be known", and maybe that is the core of me being wrong - we can prove that such an algorithm exists, and so 1/BB(100) is computable just like BB(100) is computable 0 but every time I write this down, I still can't see how this logic doesn't also break down with actually non-computable numbers. e.g. "There is a function f(x) which returns an integer, I can't tell you what the integer is, but it is the one that results in showing that Chaitlin's number is computable"

Anyway, if you notice this and do reply, then very much thank you - and apologies if your reply goes unread

> BB(100) has the value of 42

You wouldn't be able to express BB(100) explicitly. My article is about a lower bound on the much smaller BB(63), and it's already very hard to give a sense of how large that is. Go would of course be able to give you the 100 bit program for it.

> Chaitlin's number is 1/2

We know that Chaitin's number is not computable. So it cannot be 1/2. It has an infinite binary expansion of which we can only ever compute a fixed number of bits.

> I guess by the definition, it is computable

It's not.

> I'm also struggling with the reciprocal of BB(100). This is rational, so maybe it too is computable.

A number x is computable if-and-only-if its reciprocal is. Any fixed integer, like N=BB(100) is computable (with the trivial program print N), and therefore so is its reciprocal. What is not computable is the function BB(.)

> there exists an algorithm to do X

What is X ?

If you want to discuss this further, please just send your reply by email.

>For example, let's suppose that you manage to have a conversation with God and you discover that BB(100) has the value of 42, and Chaitlin's number is 1/2.

An uncomputable number can not be expressed as a finite sequence of digits in any computable base. So Chaitin's constant must consist of an infinite number of digits regardless of what base you choose, so long as the base is computable.

So "God" or an oracle can never actually produce Chaitin's constant in any finite representation, all an oracle can do is behave as a function where you give it an integer N, and it returns the N'th digit of Chaitin's constant.

Reply on news.ycombinator.com