Используем унарную систему счисления (0 - 1 палочка)

Индукция по построению ч.р. схемы для f

«Не рекомендую так подробно записывать, если кто-то пытается, все это можно почитать» (C)

Усилим утверждение: докажем, что любая ч.р.ф вычислима по Тьюрингу в сильном смысле

*пошел треш, угар и содомия*

Сегодня на сайт выложат дз, после 5 часов
6 задач
Все подробно будет написано в условии

Если не сказано иного, надо полностью расписывать все алгоритмы

Входной алфавит != ленточный алфавит (важно!)

"Пытаемся перейти к общей теории рекурсии. Хз, как далеко уйдем, но базу обсудим"

Описывать алгоритмы будем неформально

Рассказали три теоремы, которые "хорошо бы запомнить"

Говорим про вычислимые множества
Дали определение, строим невычислимое теперь (конструкция в лучших традициях Кантора)