Новини

• 
• 
• 
•  867

15 грудня 2016 року

Науковий семінар Дениса Олександровича Лісіна

У четвер, 15 грудня, на фізико-енергетичному факультеті відбувся семінар на тему «Busy beavers and the algorithms theory». З доповіддю виступав доцент кафедри інформаційних технологій в фізико-енергетичних системах Лісін Денис Олександрович.

Задача пошуку старанних бобрів пов’язана з проблемою дослідження важкообчислюваних функцій в теорії алгоритмів, при цьому сама функція старанного бобра є необчислюваною, що зумовлено нерозв’язаністю проблеми зупинки. Крім цього, функція старанного бобра є прекрасною ілюстрацією теореми Геделя про неповноту в застосуванні до теорії алгоритмів.

В ході доповіді були згадані питання пошуку старанних бобрів для числа станів машини Тьюринга більших за 4, доведення нерозв’язаності функцій старанних бобрів та інші. Студенти і викладачі, що були присутні на семінарі, з зацікавленістю сприйняли розповідь про цю малодосліджену область теорії алгоритмів.

• Анонси
• Новини
• Фотогалереї