Главная » Хабрахабр » Гугология (это не опечатка) для программистов

Гугология (это не опечатка) для программистов

О математике (так, чтобы было интересно) писать сложнее, чем о физике. Однако я надеюсь, что вы дочитаете хотя бы до примеров сумасшедших программ на C.

image

Из совершенно безобидных вещей могут вырастать монстры. Возьмем, например, игру в substrings. Напишем строку из букв a и b и выделим подстроки с символа 1 до символа 2, с 2 до 4, с трех до 6, с n до 2n, пока хватит длины основной строки. Наша задача сделать так, чтобы в этих подстроках более короткая не входила в любую более длинную. Я даже написал анализатор на SQL:

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

Вот пример вывода:

Мы можем убрать последний символ, и получившаяся строка из 11 символов 'abbbaaaaaaa' проверку пройдет. Как видно, подстроки 1 и 5 не прошли проверку. Оказывается, что это и самая длинная возможная строка в алфавите из двух символов, которая удовлетворяет данному условию.

Оказывается, максимальная длина конечна для алфавита из любого количества букв. Для алфавита из одного символа максимальная длина строки равна 3, и то по чисто техническим соображениям. Итак, мы имеем:

$f(1) = 3 $

$f(2) = 11 $

$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/9a8/a69/872/9a8a69872974160f7e89c87357c0256d.svg" alt="$f(3) = ???

Проверьте свою интуицию, какой длины строку можно соорудить в алфавите из трех букв. 100? 1000? На самом деле много больше, чем Гугол, и много больше, чем ГуголПлех.

$f(3) > 2 \uparrow^ 158836$

И мне придется потратить время, чтобы показать силу стрелок.

Стрелки (гипероперации)

Мы используем умножение, чтобы не писать много операций сложения:

$2*5 = 2 + 2 + 2 + 2 + 2$

Мы используем возведение в степень, чтобы не писать много умножений:

$2^3 = 2 * 2 * 2$

Считая сложение операцией уровня 0, умножения — 1, возведения в степень — 2, мы можем ввести операцию «стрелка», например,

$3 \uparrow 3 = 3^{(3^3)} = 3^{27} = 7'625'597'484'987$

Обратите внимание, что здесь уже важны скобки. Следующим уровнем является операция две скобки:

$3 \uparrow \uparrow 3 = 3 \uparrow (3 \uparrow 3) = 3 \uparrow 7625597484987 = 3^{3^{...^3}}$

Последняя пирамида троек имеет в высоту 7 биллионов, и это число уже намного, намного больше и гугола и гуголплекса. Обозначим это огромное число как Тьма (было такое числительное в старом русском языке) и попробуем сделать еще один шаг:

\uparrow 3$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/6e9/9d2/c68/6e99d2c68ef3ca67b13f10eaced63099.svg" alt="$3 \uparrow^3 3 = 3 \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow (3 \uparrow \uparrow 3) = 3 \uparrow \uparrow {тьма} = 3 \uparrow 3 \uparrow 3 ...

(и так тьма раз)… Тут уже даже представить, сколь велико это число. Обратите внимание, что когда стрелок много, мы пишем повторитель вверху. Так что вы можете понять, сколь велико

$f(3) > 2 \uparrow^{7198} 158836$

И еще больше

С помощью стрелок создаются лишь самые маленькие из больших чисел, если так можно сказать. Скорость роста функций измеряется по некоей шкале — путем сравнения со быстрорастущими функциями. Первая функция в этой иерархии соответсвует сложению, вторая — умножению, третья — стрелке, n-ная — n-2 стрелкам (приблизительно, не точно). Но можно определить

$f_w (n) = f_n(n)$

Такая функция для для n=3 сравнима с одной стрелкой, для n=4 с двумя стрелками, а при росте параметра n опережает рост функии с любым статическим количеством стрелок.

Картинка со структурой начальных порядковых чисел предваряет статью, но они простираются куда дальше, и дальше начинается Можно пойти еще дальше: $f_w, f_{w+1}, f_{w+n}, f_{w2}, f_{w^2}, f_{w^w}, f_{w^{w^{w}}}, f_\epsilon$Функции эти индексируются ординалами, или в русской литературе — порядковыми числами.

Небольшая мистика

Бесконечная пирамида из 'омег' дает некий ординал $\epsilon_0$. Почитайте про функцию, рост которой измеряется этим ординалом. Выясняется, что функция растет так быстро, что формальная арифметика не может в принципе доказать, что такая функция вообще определена!

Но, как правило, единственный пример такого утверждения, это само построение Геделя («я недоказуемо»). Вы, конечно, знаете про теорему Геделя, что есть недоказуемые утверждения. Теорема Goodstein — хороший пример такого утверждения.

'Сила' формальной арифметики равна $\epsilon_0$, упрощенная теория множеств Крипке-Платека имеет силу ординала Фефермана-Шутте итд. Более того, оказывается, что ординалы неким образом измеряют силу теорий.

Жесть — Математики жгут — Соревнование на языке C

Было проведено соревнование по генерации больших чисел. Нет, программирование для машины Тьюринга — это все-таки слишком жестоко, поэтому использовался язык C для некоей абстрактной бесконечной машины, у которой sizeof(int)=бесконечности. Можно также было использовать malloc(), причем объем памяти, как и стека, не ограничен. Ограничена была лишь длина программы — программа должна была укладываться в 512 байт (без учета пробелов), но допускалось использование препроцессора (#define).

Заодно зацените дизайн сайта настоящего математика. Результаты опубликованы на сайте математика. Вот текст программы, занявшей второе место, дающей число около Результаты тут.

$f_{w^w}(10^{500})$

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) ;}

Текст программы победителя более длинен, я просто хотел показать, с чего он начинается:

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

Но оценить, насколько большое число получилось, затруднился даже организатор конкурса (написано very big)

Busy Beavers

Ладно, хватит заниматься крошечными числами, займемся большими. Представьте, что организован вселенский конкрус на написание программы по генерации самого большого числа. Так как число программ не длиннее 512 символов конечно, обязательно есть абсолютный победитель. Обезначим его как BB(512) — busy beaver function.

Но как быстро растет сама функция BB? Ясно, что BB(1024) >> BB(512). Сама функция BB алгоритмически неразрешима, ее нельзя рассчитать на компьютере. Оказывается, она растет быстрее чем все, с чем мы встречались. Так что BB растет быстрее, чем любая алгоритмически разрешимая функция. Но при увеличении длины допустимой программы мы можем реализовать все больше и больше новых идей.

BIG FOOT

Ладно, хватит заниматься крошечными числами, займемся большими. Ах, я это уже говорил? Было бы классно запустить BB(BB(n)). Но так как BB невычислима, с этим есть технические сложности (такая функция вычислима в машинах Тьюринга с оракулами — не путать орАкулов с СУБД Оракл).

Формуле с кванторами не важно, вычислимо что-то или нет. Но можно поступить проще, вместо программы рассмотреть формулу с кванторами длины n. И это только то, что первым пришло в голову. Так можно хоть взять функцию BB(10000000000), и применять ее к себе BB(BB(BB(1000000))) раз.

Самое большое число, которое можно обозначить формулой не более n символов, обозначается FOOT(n).

$BIG FOOT = FOOT^{10}(10^{100})$

P.S.

Для следующей статьи хотелось бы понять, на что ориентироваться, поучаствуйте в опросе пожалуйста


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] История транзистора, часть 2: из горнила войны

Другие статьи цикла: История реле История электронных компьютеров История транзистора Горнило войны подготовило почву для появления транзистора. С 1939 по 1945 года технические знания из области полупроводников невероятно сильно разрослись. И тому была одна простая причина: радар. Самая важная технология ...

Что можно сделать через разъем OBD в автомобиле

Ни для кого не секрет, что в современных автомобилях все системы под завязку забиты различной электроникой, даже простой стеклоподъемник имеет собственный микроконтроллер и адрес в общей сети. Мне, как интересующемуся владельцу, стало интересно, что же можно сделать имея просто доступ ...