Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Теоремы о неподвижных точках
Классическая теория вычислимости


Что: Лекция
Когда: Среда, 21 сентября 2016, 11:50–13:20
Где: 2-й учебный корпус К(П)ФУ, ауд. 1011

Описание

Второй день: теоремы о неподвижных точках. Оказывается, неразрешимы не только какие-то выделенные свойства программ. Неразрешимы вообще любые свойства, которые не зависят от текста программы, а зависят лишь от результата её работы. В этом заключается теорема Успенского-Райса. Она тесно связана с теоремой Клини: каким бы ни было преобразование программ, найдётся программа, которая до преобразования делает то же, что и после. Как следствие, в любом языке программирования можно написать программу, печатающую собственный текст.