What is the maximum number which can be written with fewer less than sixty five symbols?

82 Views Asked by At

If you try to write down all numbers with the symbols of any alphabet using at most 65 characters, then among them there must be a maximum. Let's call it $N$. But then the number described by the phrase "maximum number which can be written with fewer less than sixty five symbols" must be greater than it, which leads to a contradiction. This phrase also describes the number and itself uses 65 symbols while claiming that it sets this maximum number and it should be greater than $N$. Is it paradox like Russell's paradox?

1

There are 1 best solutions below

0
On BEST ANSWER

As Rahul says in the comments, this is known as the Berry paradox, and the problem is the ambiguity in the phrase "can be written." You can try to resolve that ambiguity by, for example, specifying a formal language such as Peano arithmetic in which to write down numbers, or specifying a programming language such as Python in which to write down programs which print out numbers.

What happens then is that

This is a proof by contradiction that your formal language cannot express "the largest number expressible by fewer than $N$ symbols in [your formal language]."

When applied to (Turing-complete) programming languages this is a proof that, as a function of $N$, this function is not computable (in fact it grows faster than any computable function), which is related to the unsolvability of the halting problem. When applied to Peano arithmetic this is related to the incompleteness theorem.