0

I've been reading about Chatin's Constant, and some of the information there seems to contradict what I've heard before.

It says that the digits of Chatin's Constant can not be computed. This means that if we had a set of all the digits of Chatin's constant, let's call it $C$, there is no function that exists as a bijection between the natural numbers and $C$, because if there was, we know the natural numbers and could just plug them in to that function to compute the digits of Chatin's constant. But, this seems to go against what I've heard. On this site and others, I've been told that every set can be described by a function or rule, and therefore no sequence of numbers is truly random. If that is true, how can $C$ not be described by a function?

On the wikipedia page it says "informally represents the probability that a randomly constructed program will halt." So my theory on the answer to this question is that the constructed program already assumes true randomness, so the fact that the probability of that program halting is random should follow. But, I don't think this is true because even if the constructed program is truly random, Chatin's Constant is a real constant with digits that are also constants, and then it goes back to my above points about how if that is true it can't be random, so it seems to be a circular argument.

So, how can the digits of Chatin's constant be not describable by a function when any set of numbers can be?

Nico A
  • 4,934
  • 4
  • 23
  • 49
  • There is a function, just not a computable function. – Akiva Weinberger Nov 07 '15 at 23:55
  • 1
    Since this constant is a number, its digits are described by a mathematical function; simply let $f(n)$ be the $n^{th}$ digit, as you said. Whether or not this function can be computed with a finite algorithm is a different story. – TorsionSquid Nov 07 '15 at 23:56
  • @TorsionSquid So what you are saying is that a function does describe it, just not a finite one? – Nico A Nov 07 '15 at 23:57
  • Yes. And by "finite" we mean that you could create a finite computer program that inputs $n$ and outputs $f(n)$. – TorsionSquid Nov 07 '15 at 23:59
  • @TorsionSquid Ok Thanks! My only other question is that there must be a finite function that describes the first, say, 10 digits of the constant. Because the function is finite, I believe it must be computable, and doesn't that mean we can solve the halting problem for programs up to a length of 10? – Nico A Nov 08 '15 at 00:03
  • This is possible, but, as the Wiki article says, it is very hard to compute past the first few digits. The point of the halting problem is that there isn't a general algorithm to see if a program halts. However, if we look at all programs of fixed length $n$, there is an algorithm (worst case: have a table with $2^n$ entries). – TorsionSquid Nov 08 '15 at 00:19
  • @TreFox For each $n$, $\Omega$ up to the $n$th digit is given by some computable function (call it "$f_n$"). However, we can't "paste these together" to get a whole computation of $\Omega$, since we don't know what $f_n$ is, we just know that some computable function is $f_n$! – Noah Schweber Jun 02 '17 at 01:09

0 Answers0