# Практические задания
## Вопросы, которые могут встретиться на допуске к зачету
* понятие парадигмы программирования;
* фон-Неймановская архитектура;
* понятие ссылочной прозрачности;
* понятие чистой функции.

Кроме того, в допуске к зачету или в зачетном задании могут встретиться вопросы на понимание ссылочной прозрачности и чистоты функций и определения, является ли данный код на Java/Scala ссылочно прозрачным.

[Материалы по теме](https://docs.google.com/presentation/d/11WQnuEIif2BD971z5XJFoa-unyrRTAHO6Yy8A6d-4As/edit?usp=sharing). При подготовке по теме можно (и нужно) использовать и другие материал, т.к. презентация не является полным конспектом лекций, которые читались.

# Машина Тьюринга

## Вопросы, которые могут встретиться на допуске к зачету
* алгоритмические модели;
* определение вычислимости по Тьюрингу;
* какие элементы участвуют в задании одноленточной машины Тьюринга;
* как записывается правило перехода для одноленточной машины Тьюринга;
* как записывается правило перехода для многоленточной машины Тьюринга;
* что такое "детерминизм" в контексте машины Тьюринга;
* что такое "конфигурация" одноленточной машины Тьюринга;
* что такое "конфигурация" многоленточной машины Тьюринга;
* что такое "протокол" одноленточной машины Тьюринга;
* что такое "протокол" многоленточной машины Тьюринга;
* дайте определение "стандартной кофигурации" одноленточной машины Тьюринга;
* дайте определение "стандартной кофигурации" многоленточной машины Тьюринга;
* связь машины Тьюринга и конечных автоматов.

Кроме того, в допуске к зачету или в зачетном задании могут встретиться вопросы на понимание свойств машины Тьюринга и вычисляемым ими функций.

[Материалы по теме](https://docs.google.com/presentation/d/11LrR-3OSMmMpdhl2HDwQk7XtjyKfLBk-0sq5pV7wxcA/edit?usp=sharing). При подготовке по теме можно (и нужно) использовать и другие материал, т.к. презентация не является полным конспектом лекций, которые читались.

## Практические задания
## Алфавит
Для каждого задания алфавит `Α` ограничивает только **входное** слово, результат и процесс выполнения программы могут иметь символы не входящие в `Α`.

## Формат ответа
Предполагается, что **во всех задачах** машина Тьюринга находится в **стандартной конфигурации**.

Предположим, даные две задачи:
* Задача 1
Пусть `Α = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ∅}`; `P` — непустое слово. Требуется получить на ленте запись числа, которое на `1` больше числа `P`.
* Задача 2
Пусть `Α = {a, b, c, ∅}`; `P` — непустое слово. Если первый и последний символы (непустого) слова `Р` одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово.

Формат ответа должен соответствовать шаблону, описанному [здесь](https://docs.google.com/spreadsheets/d/1nPwJLFVvsZ3sTtUZv-u9cxAyb_eM7tXCg3HM4YgYcpo/edit?usp=sharing). Обратите внимание на комментарии.

Необходимо создать Google Spreadsheets, добавить ссылку на этот документ в качестве решения на Google Classroom, убедиться, что у меня есть права на просмотр документа.

## Задачи
### Одноленточная машина Тьюринга

#### Задача 1
`Α = {a, b, c}`. Приписать слева и справа к слову `P` символ `b` (т.е. `P → bPb`).
**1 балл**

#### Задача 2
`Α = {a, b, c}`. Приписать справа к слову `P` символы `bc` (т.е. `P → Pbc`).
**1 балл**

#### Задача 3
`Α = {a, b, c}`. Определить, входит ли в слово `P` символ `a`.
Возвращаемый результат: `1` — если входит, `0` — если не входит.
**2 балла**

#### Задача 4
`Α = {a, b, c}`. Заменить на `a` каждый третий символ в слове `P`.
**2 балла**

#### Задача 5
`Α = {a, b, 0, 1, 2}`. Определить, является ли слово P записью числа в троичной системе счисления (словом, возможно - пустым, состоящем только из цифр `0`, `1` и `2`).
Возвращаемый результат: `1` — если да, `0` — если нет.
**2 балла**

#### Задача 6
`Α = {0, 1, 2, 3}`. Для непустого слова P определить, является ли оно записью степени четверки (`1, 4, 16, ...`) в четверичной системе счисления.
Возвращаемый результат: `1` — если да, `0` — если нет.
**2 балла**

#### Задача 7
`Α = {a, b}`. Утроить слово `P` (например: `abb → abbabbabb`).
**4 балла**

#### Задача 8
`Α = {a, b}`. Перевернуть слово `P` (например: `abb → bba`).
**4 балла**

#### Задача 9
`Α = {a, b}`. Утроить каждый символ слова `P` (например: `bab → bbbaaabbb`).
**6 баллов**

#### Задача 10
`Α = {(, ), a, b}`. Определить, сбалансировано ли слово P по круглым скобкам: запись ((a)(bb)) считается сбалансированной, запись ((a)(b) считается несбалансированной, запись (), т.е. скобки без символов a или b внутри, считается некорректной.
Возвращаемый результат: `1` — если да, `0` — если нет.
**8 баллов**

#### Задача 11
`Α = {a, b}`. Если в `P` символов a больше, чем символов `b`, то выдать ответ `a`, если символов `a` меньше символов `b`, то выдать ответ `b`, а иначе в качестве ответа выдать пустое слово.
**8 баллов**

### Многоленточная машина Тьюринга
**Важно**: решения для одноленточных машин, результат работы которых просто переписыается на вторую ленут, засчитаны не будут.
#### Задача 12
`Α = {1, ∅}`. Для двухленточной машины Тьюринга напишите алгоритм, который будет складывать два числа, записанных в унарной системе счисления, разделенных пустым символом `∅`. Результат сложения выведите на вторую ленту.

#### Задача 13
`Α = {1, ∅, -}`. Для двухленточной машины Тьюринга напишите алгоритм, который будет вычитать два числа, записанных в унарной системе счисления, разделенных пустым символом `∅`. В случае отрицательного результата, перед числом поставьте символ `-`. Результат сложения выведите на вторую ленту.

#### Задача 14
`Α = {a, b, c}`. Для двухленточной машины Тьюринга напишите алгоритм проверки, является ли слово над алфавитом `A` палиндромом.

# Вычислимые функции
## Практические задания
* Может ли всякая вычислимая функция f с натуральными аргументами и значениями быть продолжена до всюду определённой вычислимой функции g: ℕ→ℕ? Докажите.
* Является ли данное множество разрешимым: {254, 5990, 4487, 3479, 685, 1774, 3850, 5426, 1695, 4106, 5449, 1768, 5493, 6540, 5778, 7956, 3644, 8181, 3746, 4429, 7246, 2701, 6251, 4756, 5795, 5897, 7109, 1514, 9601, 9978, 4192, 3684, 4883, 3176, 9666, 4244, 5312, 8252, 4317, 8710, 7846, 4550, 2772, 4319, 638, 2562, 3028, 5104, 1931, 4871, 6926, 2491, 6520, 6499, 8494, 4436, 3276, 2383, 5425, 1977, 1956, 3066, 8721, 5021, 963, 2937, 1188, 4099, 5269, 3266, 3622, 545, 7247, 5011, 8307, 3060, 4649, 7589, 7547, 9034, 9390, 6196, 418, 4803, 4528, 3614, 4957, 5690, 1022, 2721, 5784, 1836, 6933, 5082, 7077, 7056, 3252, 7260, 6396, 6875}? Докажите.
* Является ли множество {2ㆍx I x ∊ ℕ } разрешимым? Докажите.
* Является ли множество всех простых чисел разрешимым? Докажите.
* Является ли данное множество перечислимым: {254, 5990, 4487, 3479, 685, 1774, 3850, 5426, 1695, 4106, 5449, 1768, 5493, 6540, 5778, 7956, 3644, 8181, 3746, 4429, 7246, 2701, 6251, 4756, 5795, 5897, 7109, 1514, 9601, 9978, 4192, 3684, 4883, 3176, 9666, 4244, 5312, 8252, 4317, 8710, 7846, 4550, 2772, 4319, 638, 2562, 3028, 5104, 1931, 4871, 6926, 2491, 6520, 6499, 8494, 4436, 3276, 2383, 5425, 1977, 1956, 3066, 8721, 5021, 963, 2937, 1188, 4099, 5269, 3266, 3622, 545, 7247, 5011, 8307, 3060, 4649, 7589, 7547, 9034, 9390, 6196, 418, 4803, 4528, 3614, 4957, 5690, 1022, 2721, 5784, 1836, 6933, 5082, 7077, 7056, 3252, 7260, 6396, 6875}? Докажите.
* Является ли множество {2ㆍx I x ∊ ℕ } перечислимым? Докажите.
* Является ли множество всех простых чисел перечислимым? Докажите.
* Является ли функция f(x, y) = x + y примитивно рекурсивной? Докажите.
* Является ли функция f(x, y) = xy примитивно рекурсивной? Докажите.

# Бестиповое λ-исчисление
## Практические задания
### Расставьте скобки
* λv.vp λu.v u
* (λv.vp) λu.w λw.wupv
* λv.v u λv.uv

### Подчеркните все свободные переменные
* λv.v p λu.v u
* (λv. v p) λu. w λw. w u p v
* λv. v u λv. u v

### Примените β-редукцию (и α-конверсию там, где это необходимо) до тех пор, пока это возможно. В ответе укажите все этапы преобразования выражения
* (λp.p) (λu.u u) (λv.v s)
* (λp.p) (λp.p p) (λp.p u)
* (λv.λu.v u u) (λs.s) t
* (λv.λu.v u u) (λu.u) u
* (λv.v v) (λu.u v) p
* (λv. (λu. (v u)) u) p
* ((λv.v v) (λu.u)) (λu.u)
* (((λv. λu.(v u))(λu.u)) w)

### Покажите, что заданные выражения имеют несколько различных последовательностей редукции, найдите нормальную форму
* (λv.u) ((λu.u u u) (λv.v v v))
* (λvu.v) (λu.u) ((λv.v v) (λv.v v))

### Булевы операции
#### Пусть not ≡ λz.((z 𝔽) 𝕋)
* Докажите, что not (not 𝕋) = 𝕋.
* Докажите, что not (not 𝔽) = 𝔽.

#### Пусть and ≡ λx.λy. x y 𝔽
* Докажите, что and 𝕋 𝕋 = 𝕋.
* Докажите, что and 𝕋 𝔽 = 𝔽.
* Докажите, что and 𝔽 𝕋 = 𝔽.
* Докажите, что and 𝔽 𝔽 = 𝔽.
* Докажите, что or 𝕋 𝕋 = 𝕋.
* Докажите, что or 𝕋 𝔽 = 𝕋.
* Докажите, что or 𝔽 𝕋 = 𝕋.
* Докажите, что or 𝔽 𝔽 = 𝔽.

### Арифметические операции над нумералами Чёрча
#### Пусть cn≡ λf.λx. fn(x) — n-й нумерал Черча, и succ ≡ λx.λf.λp. f (x f p)
* Докажите, что succ 1 = 2.
* Докажите, что succ 4 = 5.

#### Пусть cn≡ λf.λx. fn(x) — n-й нумерал Черча и x + y ≡ λx.λy.λp.λq. x p (y p q)
* Докажите, что 1 + 2 = 3.
* Докажите, что 2 + 3 = 5.

#### Пусть cn≡ λf.λx. fn(x) — n-й нумерал Черча и x ⋅ y ≡ λx.λy.λz. x (y z)
* Докажите, что 1 * 2 = 2.
* Докажите, что 2 * 2 = 4.

# Scala
## Практические задания
TBD