City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Вычислимые функции
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 19 September 2012, 18:30–19:50
Where: ФМЛ 239, Актовый зал

Description

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

Video