Определим отношение

-> <= Conf(M) x Conf(M)
 M

C_1 ->_M C_2 - конфигурация С_1 переходит в конфигурацию С_2 за 1 шаг работы М

1. \delta(q, a) = (q', a', S)
qa -> q'a'S

AqaB ->_M Aq'a'B

2. \delta(q, a) = (q', a', R)
qa -> q'a'R'

2.1 B = b B' != /\
AqaB ->_M Aaq'bB'

2.2 B = /\
AqaB ->_M Aa'a'#

3.qa -> q'a'L

3.1 AqaB ->_M A'q'ba'B
A = A', b != /\
3.2 A = /\ AqaB ->_M q'#a'B

C_1 -»_M C_2 - C_1 переходит в C_2 за несколько шагов (это то, что называется вычислением МТ)

*происходит какая-то дичь во время обсуждения, когда машина зацикливается

Дали определение вычислимой МТ функции

Сейчас будем доказывать, что функции нат аргументов вычислимы на МТ (т.е. что частично рекурсивные функции и функции, вычислимые МТ - одно и то же)
Доказать не факт что сможем, но попробуем

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

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

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

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

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

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

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

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

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

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

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

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