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

Теоремы о неподвижных точках
Classical theory of computability

What: Lecture
When: Wednesday, 21 September 2016, 11:50–13:20
Where: 2-й учебный корпус К(П)ФУ, ауд. 1011

Description

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