Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Среда, 19 сентября 2012, 18:30–19:50
Где: ФМЛ 239, Актовый зал

Описание

Неразрешимость разных задач, сведение по Карпу, NP-полнота задачи об ограниченной остановке. Вычислимые функции, вычислимость функции и перечислимость ее графика, пример числа, которое является пределом вычислимой последовательности, но не приближается алгоритмически, диагональная функция и то, что ее нельзя продолжить до всюду определенной, главные нумерации вычислимых функций. Теорема Успенского-Райса. другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса.

Видео