Серия скринкастов «Вычисления» — это насыщенное введение в ключевые концепции теории вычислений, представленное в практическом формате с использованием реального кода. От машин Тьюринга до иерархии Хомского, от лямбда-исчисления до фундаментальных ограничений вычислимости — курс помогает сформировать цельное понимание того, как работают вычислительные системы на самом базовом уровне.
Скринкасты структурированы так, чтобы постепенно провести вас от базовых идей к более сложным вычислительным моделям. Каждый урок — это сочетание теории, демонстраций и анализа ключевых примеров.
Краткий обзор основных тем серии: машины Тьюринга, лямбда-исчисление, проблема остановки, эквивалентность Тьюринга и иерархия Хомского. Этот модуль задаёт фундамент для дальнейшего изучения.
Создаем базовый симулятор машины Тьюринга и запускаем на нем первую простую программу. В процессе разбираем элегантные упрощения, предложенные Аланом Тьюрингом.
Показываем, как машины Тьюринга реализуют знакомые программистам концепции: циклы, условия, составные структуры данных. На основе этих возможностей выполняем сложение целых чисел и демонстрируем построение массивов, строк и вложенных структур.
Шаг за шагом превращаем функцию на Python в форму лямбда-исчисления, постепенно отказываясь от встроенных возможностей языка. В итоге получаем чистую модель вычислений на основе функций одного аргумента.
Строим числа и логические значения с нуля — исключительно через функции. Реализуем факториал без использования Python-примитивов. Обсуждаем преобразование Church numerals и оптимизацию выражений.
Изучаем проблемы, которые не может решить никакой компьютер — ни теоретический, ни реальный. Рассматриваем последствия неразрешимости для компиляторов, анализа кода и систем типов.
Погружаемся в регулярные языки: регулярные выражения, регулярные грамматики и конечные автоматы. Пошагово преобразуем одно и то же выражение через все три системы, показывая их эквивалентность.
Разбираем контекстно-свободные языки — основу синтаксиса Python, Lua и многих других. Анализируем примеры кода, сравнивая структурирование программы глазами человека и компилятора.
Завершаем разбор иерархии Хомского контекстно-зависимыми и неограниченными грамматиками. Показываем связь неразрешимых проблем с языковыми уровнями и приводим примеры реальных языков с теоретически неразрешимой грамматикой.
Обсуждаем удивительные вопросы «граммарности»: как описать синтаксис регулярных выражений или грамматик с помощью грамматик? Завершаем серией концептуальных связей между моделями Тьюринга, лямбда-исчислением и парадигмами программирования.
Курс помогает программистам, инженерам и любителям теории глубже понять природу вычислений. Эти знания:
Материал будет полезен:
Destroy All Software — это интересный и уже классический образовательный проект, в котором собраны лаконичные и содержательные видео по веб-разработке и смежным IT-направлениям. Несмотря на возраст, материалы остаются актуальными благодаря фокусу на фундаментальных принципах разработки, а не на быстро устаревающих технологиях.В рамках проекта рассматриваются реальные задачи программирования: работа с кодом, автоматизация, тестирование, архитектур
