Gugology (this is not a typo) for programmers

It is more difficult to write about mathematics (so that it is interesting) than about physics. However, I hope you read at least the examples of crazy C programs.


Monsters can grow out of completely harmless things. Take, for example, the game of substrings. We write a string of letters a and b and select the substrings from character 1 to character 2, from 2 to 4, from three to 6, from n to 2n, until the length of the main string is enough. Our task is to make sure that in these substrings the shorter does not enter into any longer. I even wrote an SQL parser:

declare @s varchar(max) = 'abbbaaaaaaab'
declare @n int=1
declare @sub table (n int, sub varchar(max)) 
while @n*2<=len(@s) begin
  insert into @sub select @n,substring(@s,@n,@n+1)
  set @n=@n+1
  end
select *,(select max(sub) from @sub I where I.n>O.n 
  and charindex(O.sub,I.sub)>0) as FoundMatch
  from @sub O order by 1

Here is an example output:



As you can see, substrings 1 and 5 did not pass the test. We can remove the last character, and the resulting 11-character string 'abbbaaaaaaaa' will pass the test. It turns out that this is the longest possible string in the two-character alphabet that satisfies this condition.

For an alphabet of one character, the maximum string length is 3, and then for purely technical reasons. It turns out that the maximum length is finite for an alphabet of any number of letters. So we have:

$$

$$

$$

Test your intuition about how long a string can be made in a three-letter alphabet. 100? 1000? In fact, much more than Googol, and much more than GoogolPlekh.

$$

And I have to spend time to show the strength of the shooters.

Arrows (hyperoperation)

We use multiplication so as not to write many addition operations:

$$

We use exponentiation so as not to write many multiplications:

$$

Considering addition as an operation of level 0, multiplication as 1, exponentiation as 2, we can introduce the operation “arrow”, for example,

$$

Note that parentheses are already important here. The next level is the two arrow operation:

$$

The last pyramid of triples has a height of 7 billion, and this number is already much, much larger than googol and googolpleks. We denote this huge number as Darkness (it was such a numeral in the old Russian language) and try to take one more step:

$$

(and so many times) ... There is already even imagine how large this number is. Please note that when there are a lot of arrows, we write a repeater at the top. So you can understand how great

$$

And more

Using arrows, only the smallest of the large numbers are created, so to speak. The growth rate of functions is measured on a certain scale - by comparing with fast-growing functions . The first function in this hierarchy corresponds to addition, the second to multiplication, the third to the arrow, and the n-th to n-2 arrows (approximately, not exactly). But you can define

$$

Such a function for n = 3 is comparable with one arrow, for n = 4 with two arrows, and as the parameter n grows, it outstrips the growth of the function with any static number of arrows.

You can go even further:$$These functions are indexed by ordinals, or in Russian literature by ordinal numbers. The picture with the structure of the initial ordinal numbers precedes the article, but they extend much further, and further begins

Little mysticism

The endless pyramid of omega gives an ordinal $$. Read about the function whose growth is measured by this ordinal. It turns out that a function grows so fast that formal arithmetic cannot in principle prove that such a function is defined at all!

Of course, you know about Godel’s theorem that there are unprovable statements. But, as a rule, the only example of such a statement is Gödel’s construction itself (“I am unprovable”). Goodstein's theorem is a good example of such a statement.

Moreover, it turns out that ordinals in some way measure the power of theories . The 'strength' of formal arithmetic is$$, the simplified Kripke-Plateka set theory has the strength of the Feferman-Schutte ordinal, etc.

Tin - Maths tourniquet - C language competition

A competition was held to generate large numbers. No, programming for a Turing machine is still too cruel, so C was used for some abstract infinite machine with sizeof (int) = infinity. You could also use malloc (), and the amount of memory, like the stack, is unlimited. Only the program length was limited - the program had to fit in 512 bytes (excluding spaces), but the use of a preprocessor (#define) was allowed.

The results are published on the mathematics website . At the same time check out the design of the site of a real mathematician. The results are here . Here is the text of the program, which took second place, giving the number about

$$

typedef int	J;
J P(J x,J y)	{ return x+y ? x%2 + y%2*2 + P(x/2,y/2)*4 : 0 ;}
J H(J z)	{ return z ? z%2 + 2*H(z/4) : 0 ;}
J I(J f,J e,J r){ return f ? P(P(f,e),r) : r ;}
J M(J x,J e)	{ return x ? I(x%2, M(e,0), M(x/2, e+1)) : 0 ;}
J D(J,J);	 
J E(J f,J e,J r,J b)
{
    return e ? E(1, D(e,b), I(b-1, D(e,b), I(f-1,e,r)), b) : I(f-1,e,r) ;
}
J D(J x,J b)	{ return x ? E( H(H(x)), H(H(x)/2), H(x/2), b) : 0 ;}
J F(J x,J b)	{ return x ? F(D(x,b+1),b+1) : b ;}
J G(J x)	{ return F(M(x,9), 9) ;}
J f(J n,J x)	{ return n ? f(n-1, G(x ? f(n,x-1) : n)) : G(x) ;}
J g(J x)	{ return f(x,x) ;}
J h(J n,J x)	{ return n ? h(n-1, g(x ? h(n,x-1) : n)) : g(x) ;}
J main(void)	{ return h(g(9),9) ;}

The winner’s program text is longer, I just wanted to show where it starts:

#define R { return
#define P P (
#define L L (
#define T S (v, y, c,
#define C ),
#define X x)
#define F );}

But even the organizer of the contest found it difficult to evaluate how large the number turned out (written very big )

Busy beavers

Okay, enough to deal with tiny numbers, let's do big ones. Imagine that a universal contest has been organized to write a program for generating the largest number. Since the number of programs is no longer than 512 characters, of course, there is always an absolute winner. Let's designate it as BB (512) - busy beaver function .

It is clear that BB (1024) >> BB (512). But how quickly does the BB function grow? It turns out that it is growing faster than everything that we met. The BB function itself is algorithmically unsolvable; it cannot be calculated on a computer. But as the length of the valid program increases, we can implement more and more new ideas. So BB grows faster than any algorithmically decidable function.

BIG FOOT

Okay, enough to deal with tiny numbers, let's do big ones. Ah, did I say that already? It would be cool to run BB (BB (n)). But since BB is not computable, there are technical difficulties with this (such a function is computable in Turing machines with oracles - not to confuse oracles with Oracle DBMS).

But you can do it easier, instead of a program, consider a formula with quantifiers of length n. A quantifier formula does not matter if something is computable or not. So you can at least take the function BB (1,000,000,000), and apply it to yourself BB (BB (BB (1,000,000))) times. And this is only what first came to mind.

The largest number that can be denoted by a formula of at most n characters is denoted by FOOT (n).

$$

PS

For the next article I would like to understand what to focus on, take part in the survey please