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

Лекция 1. О понятии "доказательства" в теоретической информатике
Обзорный курс по теоретической информатике


Что: Лекция
Когда: Четверг, 08 сентября 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

Лекция начнется с неформального рассказа про взгляд теоретической информатики на понятие доказательства по мотивам статьи на хабре: https://habrahabr.ru/company/spbau/blog/217215/.

После перерыва мы узнаем, что такое система доказательств для языка, перечислимые языки (для которых существуют системы доказательств), разрешимые языки и поймем, что есть перечислимый язык, который не является разрешимым (задача об остановке алгоритма).