Привет. Сегодня мы поговорим о том, что такое функция и как ее описать. В мире существует множество различных явлений. Каждую секунду происходит множество различных событий, как хороших или нейтральных, так и плохих: выпадение дождя, смена дня и ночи, а также сезонов года, распространение звука и света, и т.д. Всё это, все эти явления подчиняются какому-то то определенному своему закону. Даже то, что ты ложишься спать и встаёшь по утрам это тоже подчиняется какому-то определенному правилу. Все эти правила, законы и как их не назови в математике или физике описываются какой-то функцией...

Интуитивно хочется верить, что любую функцию можно запрограммировать — дать ей вход, дождаться ответа. Но в реальности существует класс функций, которые нельзя вычислить никаким алгоритмом. Вообще. Даже если дать бесконечно много времени. Типичный пример — функция Busy Beaver, но она растёт столь стремительно, что кажется далёкой от жизни. Гораздо интереснее функция, поведение которой можно себе представить — медленно растущая и при этом невычислимая. Её мы и разберём. Представим: дана задача — напечатать число n...