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

О вычислимости частично рекурсивных функций 7 Таким образом, получаем обобщение алгоритма Дэна для решения проблемы равенства слов для (6) − 1 / 3 − групп, которое выражается в последовательной замене в слове не только подслова определяющего слова, но и произведения двух частей определяющих слов на более короткие слова. Геометрическая интерпретация мало сократимых групп приводит к понятию функции Дэна. Значение функции Дэна ( ) для конечного задания группы определяется как макси- мальное количество слов, сопряжённых к определяющим словам, при перемножении которых получается любое слово, равное единице в группе , длины не больше . Её невычислимость равносильна неразрешимости в группе проблемы равенства слов. Заметим, что группы, для которых функция Дэна является линейной, – гиперболичны. Более того, как показано в [7], для всякой гиперболической группы имеется возможность конечного задания, для которого проблема равенства решается с помощью алгоритма Дэна. 3. Заключение Одним из самых важных аспектов изучения этих вопросов является демонстрация важ- ности приложений их формального представления к решению конкретных задач предметной области. И только в этом случае может идти речь о заинтересованном продуктивном подходе к исследованию сложных математических структур. СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ 1. Гильберт Д., Аккерман В. Основы теоретической логики: пер. с нем. – М., 1947. 2. Есаян А. Р. Теория и методика обучения алгоритмизации на основе рекурсии в курсе информатики педагогического вуза: автореф. дисс. . . . докт.пед. наук – М., 2001. 3. Марков А. А., Нагорный Н.М. Теория алгорифмов М.: «Наука», 1984. 217с. 4. Мендельсон Э. Введение в математическую логику: Пер. с англ. – М.: «Наука», 1976. 161с. 5. Чёрч А. Введение в математическую логику: Пер. с англ. – М.: «Иностранная литерату- ра», 1960 485 с. 6. Линдон Р., Шупп П. Комбинаторная теория групп. – М., 1980. 368с. 7. Лысёнок И. Г. О некоторых алгоритмических свойствах гиперболических групп // Изв. АН СССР. Сер. матем. 1989. Т. 53. Выпуск 4. С. 814–832. REFERENCES 1. Gilbert D., Ackerman V., 1947, "Fundamentals of theoretical logic" : trans. with him. – M.. 2. Yesayan A. R., 2001 "Theory and methodology of teaching algorithmization based on recursion in a computer science course at a pedagogical university: abstract of thesis. diss. . . . doc.ped. Sciences" – M.. 3. Markov A. A., Nagorny N. M., 1984, "Theory of algorithms" M.: “Nauka”, 217 p. 4. Mendelssohn E., 1976, "Introduction to mathematical logic" : Transl. from English - M.: “Science”, 161 p.