Этюд

Этюд 1. Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}.

Этюд 2. Реализация при помощи исчисления Маркова задачи сортировки слова по возрастанию в алфавите {0,1,2}.

Этюд 3. Убрать два первых знака из бинарного слова при помощи исчисления Маркова. Задачу переработки слов попытаться решить без расширения алфавита.

Этюд 4. Пусть существует следующая машина Тьюринга, которая печатает на чистой ленте последовательность ….Построить соответствующий алгоритм Маркова. Найти код данного алгоритма (гёделизация).

Этюд 5. Целое число определить как упорядоченную пару натуральных чисел (m, n), понимая, что целое число равно m-n. Но при этом нельзя писать целое число таким образом (компьютерная семантика). Разработать основные правила работы с целыми числами и операции над ними (алгебру).

Этюд 6. Рациональное число определить в виде отношения двух целых чисел: p/q, где q не равно 0. Но при этом нельзя писать рациональное число таким образом (компьютерная семантика). Разработать основные правила работы с целыми числами и операции над ними (алгебру).

Этюд 6. Действительные числа – числа, которые являются суммой сходящихся рядов (компьютерная семантика). Разработать основные правила работы с целыми числами и операции над ними (алгебру), на основе алгебры целых и рациональных чисел. Вспомним, что в разных системах исчисления действительные числа можно представить в виде: b0+b1/r +b2/r2 +…+bn/rn (это общий вид сходящегося ряда, где r – база системы исчисления).

Этюд 7. Алеф-нуль (À0) –первое трансфинитное число (равно мощности множества всех натуральных чисел). Доказать свойства трансфинитных чисел: À0 +À0=À0; À0*À0=À0 .

Этюд 8. Кантор создал шкалу трансфинитных чисел (À0 – первое трансфинитное число): À0, 2^ À0, 2^ 2^ À0, … Равномощны ли множества соответствующие этим числам?

Этюд 9. Рациональное число p/q - это частное двух целых чисел. Все рациональные числа вычислимы. Описать алгоритм их вычисления с любой степенью точности.

Этюд 10. Алгебраическое число это корень алгебраического уравнения с рациональными коэффициентами. Описать алгоритм их вычисления с любой степенью точности.

Этюд 11. Примитивная рекурсивность суммы.

Этюд 12. Примитивная рекурсивность факториала.

Этюд 13. Имеется оператора минимизации μ. Например, для функции разности f(x, y)=x-y, для всех x, y имеем: x-y=μz(y+z=x). Каково значение выражения μy(y(y-(x+1))=0)?

Этюд 14. Называя сложение, умножение и возведение в степень действиями 0-й, 1-й и 2-й ступени, вводим для них обозначения:

P0 (a, x)=a+x,

P1 (a, x)=a*x,

P2(a, x)=ax.

Функции Р0, Р1, Р2 связаны следующими соотношениями:

P1(a, x+1)=P0(a, P1(a, x)), P1(a, 1)=a;

P2(a, x+1)=P1(a, P2(a, x)), P2(a, 1)=a;

….

Pn+1(a, x+1)=Pn(a, Pn+1(a, x)), Pn+1(a, 1)=a.

Чтобы функции Pn(a, x) были определены всюду, положим Pn+1(a, 0)=1 (n=1, 2,…). Например, имеем: P3(a, 0)=1, P3(a, 1)=a, P3(a, 2)=aa, P3(a, 3)=(aa)a. Вводим функции - функцию Аккермана B(n, x)=Pn(2,x), а также A(x)=B(x, x) – диагональную функцию Аккермана. Какова система уравнений, определяющая рекурсивно функцию А(х)?

Этюд 15. Сложность машины Тьюринга для вычисления функции f(n)=2n+3.

Машина работает так:

1)  Копирует каждую «палочку» в значении аргумента дважды, что дает 2n+2 палочек в значении функции.

2)  Прибавляет к ним еще две «палочки» и возвращается в начальную клетку.

Сколько тактов затратит машина на первый этап и второй этап (размер задачи - значение аргумента n)?

Этюд 16. Сложность машины Тьюринга для вычисления функции f(n)=2n+3.

Машина работает так:

3)  Копирует каждую «палочку» в значении аргумента дважды, что дает 2n+2 палочек в значении функции.

4)  Прибавляет к ним еще две «палочки» и возвращается в начальную клетку.

Какова временная T(n) и пространственная сложность S(n) задачи (размер задачи - значение аргумента n)? Показать, что функции T(n) и S(n) суть полиномиальные функции.

Замечание: В общем случае задача может иметь много входных слов данного размера. Временная сложность Т(n) машины есть наибольшее время её работы при входных словах размера n. Пространственная, сложность S(n) машины есть наибольший путь (наибольше число клеток), проходимой ею при входных словах размера n.

Этюд 17. Метод Дедикинда.

Действительное число: сечение множества рациональных чисел, т. е. упорядоченная пара двух множеств рациональных чисел (А, В). Каждое число множества А меньше каждого числа множества В, а в сумме они составляют все множество рациональных чисел. Определите число .

Этюд 18. Метод Вейштрасса.

Действительное число – предел сходящейся последовательности рациональных чисел. Существует признак сходимости – каждая сходящаяся последовательность дает некоторое действительное число. Определите число . Почему ?

Этюд 19. Метод Кантора

Действительное число – предел бесконечной систематической дроби.

Систематическая дробь: выражение числа через последовательные степени данного основания. Систематическая дробь всегда есть сходящийся ряд. Ряд может сходиться к пределу, который не является рациональным числом. Определите число .

Этюд 20. Построить машину Тьюринга, вычисляющую функцию:

s(x) = x + 1;

Этюд 21. Построить машину Тьюринга, вычисляющую функцию:

0(x) = 0;

Этюд 22. Построить машину Тьюринга, вычисляющую функцию:

Imn(x1,…, xn) = xm (1 <= m <= n);

Этюд 23. Построить машину Тьюринга, вычисляющую функцию:

x + y;

Этюд 24. Построить машину Тьюринга, вычисляющую функцию:

p(x) = x - 1, если x > 0; 0, если x = 0;

Этюд 25. Построить машину Тьюринга, вычисляющую функцию:

sg(x) = 1, если x > 0; 0, если x = 0;

Этюд 26. Построить машину Тьюринга, вычисляющую функцию:

antisg(x) = 0, если x > 0; 1, если x = 0;

Этюд 27. Построить машину Тьюринга, вычисляющую функцию:

d(x) = x - y, если x >= y;0, если x < y;

Этюд 28. Построить машину Тьюринга, вычисляющую функцию:

x - y;

Этюд 29. Построить машину Тьюринга, вычисляющую функцию:

[x/2]

Этюд 30. Доказать, что следующая функция примитивно рекурсивна:

f(x, y) = xy;

Этюд 31. Доказать, что следующая функция примитивно рекурсивна:

f(x, y) = xy (здесь 00 = 1);

Этюд 32. Доказать, что следующая функция примитивно рекурсивна:

f(x) = x! (здесь 0! = 1);

Этюд 30. Доказать, что следующая функция примитивно рекурсивна:

sg(x) = 1, если x > 0; 0, если x = 0;

Этюд 33. Доказать, что следующая функция примитивно рекурсивна:

antisg(x) = 0, если x > 0; 1, если x = 0;

Этюд 34. Доказать, что следующая функция примитивно рекурсивна:

p(x) = x - 1, если x > 0; 0, если x = 0;

Этюд 35. Доказать, что следующая функция примитивно рекурсивна:

d(x) = x - y, если x >= y; 0, если x < y;

Этюд 36. Доказать, что следующая функция примитивно рекурсивна:

|x - y|;

Этюд 37. Доказать, что следующая функция примитивно рекурсивна:

max(x, y);

Этюд 38. Доказать, что следующая функция примитивно рекурсивна:

min(x, y).

Этюд 39. Доказать, что следующая функция частично-рекурсивна:

а) x - y;

Этюд 40. Доказать, что следующая функция частично-рекурсивна:

б) x/y ;

Этюд 41. Доказать, что следующая функция частично-рекурсивна:

в) ;

Этюд 42. Доказать, что следующая функция частично-рекурсивна:

г) x/2 ;

Этюд 43. Доказать, что следующая функция частично-рекурсивна:

д) [x/2].

Этюд 44. Доказать, что если функция f вычисляется программой без команд условного перехода, то найдется такое число m, что либо (x)f(x) = m, либо (x)f(x) = x + m.

Этюд 45. Доказать, что существует множество натуральных чисел, не являющееся перечислимым.

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

Этюд 46. Доказать, что каждое бесконечное перечислимое множество AN является множеством значений некоторой взаимно-однозначной вычислимой функции f:N N.

Этюд 45. Доказать, что график вычислимой функции разрешим.

Графиком функции f называется множество

Задача. Сосчитать количество единиц в двоичной записи числа i.

Задача 6.

Последовательность ... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т. е. 0-> 01 -> 0112 -> ->...Составить алгоритм, который по введенному N, (0<=N<=) определяет, какое число стоит на N-ом месте в последовательности.

Задача 11.Определим множества K[i] рекуррентно. Пусть K[0] = [0,1]. Разделим сегмент [0,1] на три части точками 1/3 и 2/3 и удалим из него интервал (1/3,2/3). Получим множество K[1], состоящее из двух оставшихся сегментов [0,1/3] и [2/3,1]. Каждый из них разделим на три части (точками 1/9 и 2/9 для первого сегмента, и точками 7/9 и 8/9 - для второго) и удалим средние интервалы (1/9,2/9) и (7/9,8/9). Таким образом получаем множество K[2], и т. д. Пусть мы построим множество K[i]. Поделим каждый оставшийся сегмент из K[i] на 3 части и удалим из этих сегментов средние интервалы. Получим, таким образом, из K[i] множество K[i+1].

Вводятся 3 целых числа n, a,b. Необходимо определить, принадлежит ли точка с координатой a/b множеству K[n].

Задача 12. Найти наибольший общий делитель и наименьшее общее кратное чисел a и b.

Задача 17. Вычислить число e (основание натурального логарифма) с точностью n значащих десятичных цифр после запятой. Можно использовать числовой ряд: e=1+1/1!+1/2!+...+1/А!...

Задача 18. Вывести на экран число 2^n, n<=10000, n - натуральное.

Задача 19. Определить количество повторений каждой из цифр 0,1,2,...,9 в числе NN, N <= 1000.

Задача 20. Найти все простые числа, не превосходящие N.

Задача 21. Вводится N. Необходимо найти, на сколько нулей оканчивается N!=1*2*3*...*N.

Задача 1. Построить алгоритм, выдающий без повторений все перестановки N чисел.

Задача 2. Сгенерировать все подмножества данного n-элементного множества {0, ..., n-1}.

Задача 3. Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}.

Пример: N=3, k=2, подмножества {1,2}, {1,3}, {2,3}.

Задача 4.1. Во время поездки на поезде девочка заменила в названии поезда каждую букву ее номером в русском алфавите и получила запись из единиц и двоек "1". Определить откуда и куда идет поезд?