Записки научных семинаров Тульской школы теории чисел. Вып. 2. 2023 г.

6 Б. П. Ваньков s(x,y+1) = х+(у+1) = (х+у)+1. Поэтому получаем вывод: 1. s(x,0)= J 1 1 (x) (исходная функция 3)) 2. s(x,y+1)= S(s(х, у) ) (исходная функция 2)) 3. s(x,y) (1, 2, III ) Таким образом, функция сложения является примитивно рекурсивной функцией, т.к. по- лучается из исходных функций: функции-проектора и функции следования при помощи опе- ратора примитивной рекурсии. Аналогично доказывается примитивная рекурсивность функций: ( , ) = · , ( , ) = , ( ) = ! , ( ) = {︂ 0 , если = 0 , 1 , если̸ = 0 , ( ) = {︂ 1 , если = 0 , 0 , если̸ = 0 . ( ) = . − 1 = {︂ 0 , если = 0 , − 1 , если̸ = 0 . (усечённое вычитание 1), ( , ) = . − = {︂ 0 , если < , − , если ⩾ . (усечённая разность), | − | , min { , } , max { , } , ( , ) (остаток от деления на ) , ( , ) (частное от деления на ). c учетом того, что суперпозиция примитивно рекурсивных функций является примитивно рекурсивной функцией. Конечно-определённая группа называется ( ) − 1 / − группой, если симметризованное множество всех её определяющих слов, то есть замкнутое относительно циклических пере- становок и обращения, удовлетворяет конъюнкции условий ′ (1 / ) и ( ) , где натуральные и образуют решения уравнения 1 + 1 = 1 2 ( ( , ) ∈ { (3 , 6) , 4 , 4) , (6 , 3) } ), то есть имеем 1 / 6 − группу, (4) − 1 / 4 − группу и (6) − 1 / 3 − группу, соответственно. Условие ′ (1 / ) означает, что при сокращении произведения любых двух не взаимно об- ратных определяющих слов поглощается меньше 1 / длины каждого из них. Условие ( ) означает, что, если каждое из , 3 ⩽ < , определяющих слов написать на одной стороне -угольника, то приведения не могут произойти одновременно на всех вершинах. Алгоритм Дэна решения проблемы равенства слов для 1 / 6 − групп и (4) − 1 / 4 − групп осно- вывается на лемме Гриндлингера [6], согласно которой нетривиальное слово, равное единице в этих группах, содержит более половины циклической перестановки некоторого определяю- щего слова или ему обратного. Алгоритм М. Дэна состоит в последовательном выполнении замен в данном слове таких подслов определяющего слова равным ему дополнением − 1 и получении таким образом более короткого слова, равного исходному. Так как (6) − 1 / 3 − группы и 1 / 6 − группы являются двойственными, имеем, что нетриви- альное слово, равное единице в (6) − 1 / 3 − группе, либо содержит более половины циклической перестановки некоторого определяющего слова или ему обратного, либо произведение двух подслов определяющих слов, длина которого больше длины несократимого произведения их дополнений.