Продолжается цикл Объединенного заседания семинара ПОИС и семинара Моделирование и анализ информационных систем (ЯрГу)

Продолжает свою работу объединенное заседание семинара Научно-учебной лаборатории процессно-ориентированных информационных систем (ПОИС) факультета компьютерных наук и семинара Моделирование и анализ информационных систем кафедры теоретической информатики Ярославского государственного университета имени П.Г. Демидова.

"О проблеме конечной определимости многообразий, порождённых алгебрами вычислимых функций"

(On the problem of finite definability of the varieties generated by the algebras of computable functions)

Докладчик – Валерий Анатольевич Соколов, д.ф.-м.н. профессор, ЯрГУ

Аннотация.  Rafael Robinson showed that all primitive recursive functions of one variable and only they can be obtained from two functions s(x) = x+1 and q(x) = x – [ ]2 by using the operations of addition +, superposition * and iteration i. 

Julia Robinson proved that from the same two functions, using the operations of addition +, superposition * and operation -1 of the inversion of functions, we can obtain all general recursive functions (under a certain condition on the inversion operation) and all partially recursive functions. 

Based on these results, Academician Maltsev introduced the Rafael Robinson algebra of all unary primitive recursive functions and two Julia Robinson algebras: the algebra of all unary general recursive functions and the algebra of all unary partially recursive functions, and proposed to study the properties of these algebras, including the problem:  

find out whether a finite basis of identities exists in these algebras, i.e. are the corresponding varieties generated by these algebras finitely definable?

In the topic, we give a negative answer to this question. 

Язык семинара – русский (слайды на английском)