zlacker

>>tromp+(OP)
The article discusses different encodings of numbers to give non-dense representations of numbers exceeding (2^64)-1. (These representations are inherently non-dense by the pigeonhole principle.) But I feel like this is missing a key point. A 64-bit string that we agree represents only numbers can represent 18446744073709551616 different numbers. The choice of what numbers are represented is completely up to us. If we want certain properties (dense integers) we end up with the highest being 18446744073709551615. If we want other properties (nearly logarithmic distribution, signedness, and good mapping to hardware for arithmetic) we might end up with FP64 with a maximum value around 10^308. And if we want no interesting property constraints except being dual to a program on a Turing machine, we end up with a busy beaver number. But... remember, we can choose any 18446744073709551616 values we want to be representable. There's no restriction on the interpretation of these strings; or, equivalently, the amount of external information required to explain the interpretation of these strings is unbounded. As a result, we can choose any computable number to be encoded by the string 64'b1, or by any other string, and exceed any desired bounds.

>>addaon+ab6
> we can choose any computable number to be encoded by the string 64'b1

First of all, every finite number is computable by definition.

And second, your encodings will, unlike those in the lambda calculus, be completely arbitrary.

PS: in my self-delimiting encoding of the lambda calculus, there are only 1058720968043859 < 2^50 closed lambda terms of size up to 64 [1].

[1] https://oeis.org/A114852

>>tromp+Ne6
>First of all, every finite number is computable by definition.

You likely mean every integer or rational is computable (although not by definition). There are finite real numbers that are not computable, in fact most of them are not.

>>Kranar+Zr6
Right; I meant finite integer.

>>tromp+YF6
What is the 100th busy beaver number? I believe this is an integer, and I also believe it is not computable

>>TheNew+Bu7
As a number, N=BB(100) is trivially computable by the program "output N". What you really mean is that the function BB(.) itself is uncomputable.

>>tromp+tC7
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.