Согласно тезису Чёрча-Клини:
а) каждая интуитивно вычислимая функция является частично рекурсивной.
б) каждая рекурсивная функция является вычислимой.
в) каждая интуитивно вычислимая функция является частично рекурсивной.
г) каждая интуитивно вычислимая функция является общерекурсивной.

2.Остановка МТ происходит, когда
а) выполнена последняя подстановка
б) в состоянии P0 машина остается на месте
в) не изменяется символ внутреннего алфавита
г) не изменяется символ внешнего алфавита, состояние МТ остается неизменным, сдвиг – нулевой

3.Команда машины Тьюринга состоит из
а) символа внешнего алфавита, символа внутреннего алфавита, сдвига
б) подстроки P, символа→, строки Q
в) номера состояния ленты МТ, символа алфавита и сдвига
г) номера команды, знака команды, номера следующей команды

4. Если алгоритм имеет экспоненциальную сложность то
а) при увеличении N можем не получить решение задачи физически, т.к. это займёт очень много времени.
б) имеет место значительное

1)

1 + «Кнопка 5» = 6 этаж

6 + «Кнопка -3» = 3 этаж

3 + «Кнопка 5» = 8 этаж

8 + «Кнопка -3» = 5 этаж

5 + «Кнопка -3» = 2 этаж

2 + «Кнопка 5» = 7 этаж

7 + «Кнопка -3» = 4 этаж

4 + «Кнопка 5» = 9 этаж

2)

Боря мог выиграть все 9 раз:

1. 3 раза Боря показал камень, Алёша – ножницы

2. 4 раза Боря показал ножницы, Алёша – бумагу

3. 2 раза Боря показал бумагу, Алёша – камень

Алёша мог выиграть не более 7 раз:

1. Алёша показывает камень, Боря показывает ножницы – 2 раза. - победа

2. Алёша показывает ножницы, Боря показывает бумагу – 2 раза. - победа

3. Алёша показывает бумагу, Боря показывает камень – 3 раза. - победа

4. Алёша показывает бумагу, Боря показывает ножницы – 1 раз. - поражение

5. Алёша показывает ножницы, Боря показывает ножницы – 1 раз. – поражение

Результат:

Боря мог выиграть 9 раз.

Алёша мог выиграть 7 раз.

3)

Камнев – К, Ножницын – Н, Бумагин - Б

1. Перевезти баулы К

2. Перевезти каждый баул Н по очереди с Н в лодке, баулы оставить, Н вернуть.

3. Перевезти каждый баул Б по очереди с Б в лодке, баулы оставить, Б вернуть.

4. Перевезти Б, Н и К

4)

Для каждой гирьки есть 3 возможных расположения: чаша с грузом (-1), противоположная чаша (1) или вообще не ставить (0). Расположение каждого груза можно выбирать независимо, поэтому если есть n грузов, то их можно разместить Исходя, из этого 3^2<10<3^3, 2 гирьки - как минимум 1 значение останется без решения, 3 гирьки - как минимум 1 будет иметь несколько решений. Оптимальным набором гирек является тот, который содержит в себе степени какого либо числа: Степени двойки не подходят потому как не используют обе части весов; Тройки же подходят, поскольку гири располагаются на разных чашах весов, то их вес относительно взвешиваемого груза может принимать и положительное, и отрицательное значение.

Если, к примеру, нужна гиря весом в 2 единицы, то нужно на чашу весов с грузом положить гирю с весом 1, а на противоположную с весом 3. Вес 1 вычитается из 3 и результат 2. Таким образом можно взвесить любую массу от 1 до 10.

Возьмем 3 гирьки массой: 1, 3, 9 (степени тройки)

Цифра со знаком «-» будет соответствовать гирьке на другой чашке весов.

Уравновешивания всех масс от 1 до 10:

1 = 1.

2 = 3 - 1,

3 = 3,

4 = 3 + 1,

5 = 3 + 3 - 1,

6 = 3 + 3,

7 = 9 - 1 - 1,

8 = 9 - 1,

9 = 9,

10 = 9 + 1

5)

Допустим, минимальное количество шагов получится если постоянно удваивать максимальное значение:

1) Х+Х=2Х 2) 2Х+2Х=4Х 3) 4Х+4Х=8Х(8X+8X>15X) 4)8Х+4Х=12Х 5)12Х+2Х=14Х 6)14Х+Х=15Х – 6 шагов

Иначе, получить максимальное кратное число (неравное 15): 1, 3, 5 – максимальное 5.

Что бы его получить нужно сделать как минимум 3 операции:

1) Х+Х=2Х 2) 2Х+2Х=4Х 3) 4Х+Х=5Х

Или

1) Х+Х=2Х 2) 2Х+Х=3Х 3) 3Х+2Х=5Х

Теперь, нужно сделать (15/5)-1 операций для получения самого числа

4) 5Х+5Х=10Х 5) 10Х+5Х=15Х

ответ(5 шагов):

1) Х + Х = 2Х

2) 2Х + Х = 3Х

3) 3Х + 2Х = 5Х

4) 5Х + 5Х = 10Х

5) 10Х + 5Х = 15Х

536_8= 101011110²=350_10=15Е_16
Объяснение:  Чтобы перевести число из восьмеричной сс(Так проще, нежели переводить сразу в 10сс), нужно каждую цифру числа заменить таким же числом из двоичной сс, так, чтобы каждое число заменялось
3-мя цифрами (5 - 101, 3 - 011, 6 - 110). Из 2сс в десятичную - мы расчитываем по формуле (x(основание) * 2 + 1/0)  см. картинку. Так же, чтобы перевести из 10сс в 16сс, надо делить полученное десятичное число на основание сс (16) и записываем остаток. 350/16 = 21 остаток  14 => 21 = 15, 14 = E