Формально об алгоритмах. Вычислительные модели

Кузюрин Н.Н., Фомин С.А.
- М.: Институт системного программирования РАН, 2010. – 26 слайдов. Содержание:
RAM — random access machine.
RAM: набор команд.
RAM: моделирование FOR через GOTO.
RAM: меры сложности алгоритмов.
Машина Тьюринга.
Симулятор Машины Тьюринга.
Машина Тьюринга: Удвоение строки.
Машина Тьюринга: Унарное сложение.
Машина Тьюринга: Распознавание четных строк.
Машина Тьюринга: «Одинаковое количество 0 и 1?»
Универсальная Машина Тьюринга.
Вычислимость и разрешимость.
Неразрешимость.
Неразрешимость проблемы остановки.
Упражнения.
«Карта памяти» лекции.