Теория списков и Σ-определимость
| Авторы: | А. А. Гаврюшкина, |
| Аннотация: | Списочной алгеброй над некоторым множеством S называется двусортная модель, основное множество которой состоит из множества S и списочной надстройки IS над множеством S — множества списков элементов из S ∪ IS, снабженная естественными отношениями и операциями на списках (отношение принадлежности элемента списку, отношение подсписка, операции взятия головы и хвоста списка, операция присоединения элемента к списку). В данной работе показано, что операции в списочных алгебрах, которые могут быть заданы рекурсивно как по длине так и по глубине списка, являются Σ-определимыми. |
| Ключевые слова: | теория списков, Σ-определимость, теорема о рекурсии |
| УДК: | 510.5 |
| Литература: |
1. Гончаров С. С. Замечание об аксиомах списочной надстройки GES / С. С. Гончаров // Логические вопросы теории типов данных. – Новосибирск, 1986. – С. 11–15. –(Вычислительные системы, вып. 114). 2. Гончаров С. С. Σ-программирование / С. С. Гончаров, Д. И. Свириденко // Логико-математические проблемы МОЗ. – Новосибирск, 1985. – С. 3—29. – (Вычислительные системы, вып. 107). 3. Ершов Ю. Л. Определимость и вычислимость / Ю. Л. Ершов // Сибирская школа алгебры и логики. – Новосибирск : Научная книга, 1996. 4. Ершов Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин. – СПб. : Лань, 2004. 5. Малых А.А, Манцивода А.В, Ульянов В.С. Логические архитектуры и объектно-ориентированный подход // Вестник НГУ. Сер. Математика, механика, информатика. – 2009. – Т.9, вып. 3. -– С. 64–85. 6. А.А. Малых, А.В. Манцивода. Объектно-ориентированная дескриптивная логика // Изв. Иркут. гос. ун-та. Сер. Математика.– 2011. – Т.4, № 1. – С. 57–72. 7. J. Barwise. Admissible Sets and Structures. Perspectives in Mathematical Logic, Springer-Verlag Berlin Heidelberg NewYork, 1975. 8. Ershov, Yu.L, Goncharov, S.S., Sviridenko, D.I. Semantic Programming. Information processing, Proc. IFIP 10th World Comput. Congress, Dublin, vol. 10. pp 1093-1100, 1986. |