Контрольная работа содержит два задания. На неё даётся 2 часа, проходить будет либо в среду утром(11:00), либо в четверг (11:00).

1) Построить машину Тьюринга для некоторой задачи и написать к ней комментарии. Программа должна быть написана в явном виде.

2) Доказать неразрешимость некоторого множества. Должно быть написано строгое доказательство с использованием m-сводимости.

Пример конкретной контрольной работы, и пример решения прикрепляются, либо отправлю в лс.