Практика языка C (МФТИ, 2023-2024). Завершение: вычислимость.

Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики. На этом семинаре мы начнём с обычного ассемблера и будем его упрощать. Сначала на этом пути мы получим RAM-модель, далее машину Минского ну и в конце машину Тьюринга. Где-то там, на том краю, где программирование уже смыкается с математикой, мы рассмотрим фундаментальные проблемы вычислимости и познакомимся с быстро растущими функциями. Семинарист: Константин Владимиров. Дата: 13 мая 2024 года. Съёмка: Марк Гончаров. Звук: Юлий Тарасов. Предыдущий семинар: Timeline 00:00 Введение. Начнём с ассемблера. 04:36 Упрощаем: RAM-машина 10:10 Упрощаем далее: Ламберт-Минский 17:22 Финал упрощений: машина Тьюринга 28:07 Опыты в невычислимости 39:55 Тезис Черча-Тьюринга 44:40 На пути к теореме Райса 52:00 Статические анализаторы и их лживость 56:40 Быстро растущие функции и Busy Beaver 01:13:26 Завершение и напутственные слова Errata * Тут пока пусто