Читаю первый том Кнута "Искусство программирования". Нахожу там вот такую формулировку:
Итак, пусть A - это ограниченное множество букв, а A* - множество всех строк, определенных на множестве A, т. е . множество всех упорядоченных последовательностей x1x2 ... xn, где n≥0, и xiÎA для 1 ≤ i ≤ n. Идея заключается в том, чтобы закодировать состояния вычислений таким образом, чтобы они были представлены строками из множества A*. Тогда пусть N - целое неотрицательное число, а Q - множество всех пар (σ, i), σÎA*, а i целое число. 1 ≤ i ≤ N.
Пусть I - подмножество пар из Q, для которых i=0, а Ω - подмножество пар из Q, для которых i=N. Если θ и σ строки из A*, то мы будем говорить, что θ входит в σ, если σ имеет вид αθω, где  α и ω - некоторые строки.
Теперь построим функцию f при помощи строк  &#952;i, &#966;i и целых чисел ai, bi, 0 &#8804; i < N:
f(&#963;, i) = (&#963;, ai), если &#952;i не входит в &#963;.
f(&#963;, i) = (&#945;&#966;i&#969;, bi), если &#945; является самой короткой строкой, для которой &#963;=&#945;&#952;i&#969;.
f(&#963;, N)=(&#963;, N).

Только вот я не совсем понял смысл всего этого. Может кто объяснить простыми словами? Особенно смысл последних трех формул?

В последних трёх формулах смысл забибикан матофильтром.

картинки надо вставлять, а не нечитаемые символы.

Вот картинка
https://yadi.sk/i/UeMKkO8JkE2Pn

(0) лично считаю что сам Кнут этого тоже не понял, иначе бы нормально расписал (в виде алгоритма), а не этой математики

Вырвал кусок фразы из контекста и спрашивает "что это?"
Вообще, многие вещи в современной математике простыми словами объяснить невозможно, поскольку под ними нет "физического смысла". В данном случае описывается отображение с некоторыми характеристиками, предполагается, что оно обладает некоторыми свойствами, которые позволяют моделировать изучаемую сущность.

Тут, как в анекдоте "Сколько будет 0.5 + 1/2? Нутром чую, что литр, но доказать не могу..."
вроде всё понятно, но объяснить на пальцах даже себе не смогу...

(8) видишь средний палец? вооот! ©

(5) А писал он эти формулы типа для красоты?

(6) До этого было вот что:
https://yadi.sk/i/BYlzWNNqkEBzY
https://yadi.sk/i/56yN79DCkEC3n
Я это понял так:
"мы подставляем в функцию f пару (m,n) и получаем набор (m,n,0,1). Это первый шаг алгоритма. Подставив в функцию первый шаг, мы получим данные для второго шага: f((m,n,r,1))=(m,n, остаток от деления m на n,2). А вот подставив в функцию второй шаг, мы получаем либо результат, либо данные для третьего шага: f((m,n,r,2))=(n) если r=0, иначе (m,n,r,3). На а третий шаг переводит множество Q в вид, необходимый для первого шага: f((m,n,p,3))=(n,p,p,1). Здесь на месте m стоит n, а на месте n - остаток от деления m на n. "
Тут речь идет об алгоритме Евклида.
Но вот с теми последними формулами что-то затрудняюсь понять их смысл.

(11) Кнут приводит пример формализации алгоритма Эвклида. Формализацию алгоритма "вообще" сделать невозможно, поскольку "алгоритм" — это нематематическое понятие.

(0) дайка весь кусок с самого начала и до самого конца, читал 3 томика Кнута на 1 курсе... штырило!

(12) НОД что-ли?

(13) https://yadi.sk/i/QACTDyRDkEEzB
стр. с 19 по 27

(15) слушайте, а почему-бы вам не начать с каких-то более простых вещей... например с одноленточной Машины Тьюринга?

(16) Эх! Помнится где-то в начале 90х я написал машину реализацию машины Тьюринга на Sinclair Basic.

(17) а какой клон ZX был? что оригинальный фирменный синклер не верю ))

(18) Точное название не помню, беленький, маленький, аккуратненький (у одноклассника была "Дельта-СА", она больше). Но надпись Didaktik Skalica буду помнить до старости.

(0) Забей на смысл. Главное, прочитать достаточно страниц, чтобы похвастаться перед собутыльниками в кабаке, что читал Кнута. Никакой ценности, кроме как исторической, данное произведение не представляет.

(19) Это был чешский синклер помоему

(17) (19) в школе что-ли? Силён!