close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Задача №1
Дан алфавит Г={v, n, w, m}. Написать первые двадцать слов этого алфавита. Расположите
слова данного алфавита vmwvvvwmv, mvwnvvwv, mvwmnvnw, mwvzvw в
лексикографическом порядке.
Задача №2
Дан алфавит Г={v, w, n, m}. Найти слово с номером 23. Определите номер слова nvnmw.
Задача №3
Запишите первые двадцать упорядоченных пар натуральных чисел. Найдите канторовский
номер упорядоченной четвёрки (2, 0, 3, 1).
Задача №4
Запишите первые десять упорядоченных троек натуральных чисел. Найдите канторовский
номер упорядоченной пары (34, 12).
Задача №5
Определите стандартный номер конечного множества {0, 3, 5, 8, 9, 12}.
Задача №6
Найдите конечное множество со стандартным номером 3745.
Задача №7
Дана последовательность конфигураций: 1q010111 11q0 0111 110q1111 111q2 011
1110q211.
а) определите машину Т, выполнявшую вычисление;
б) приведите пример команды, которая может содержаться в машине Т, но не
использовалась в данном вычислении;
в) приведите пример команды, которой не может быть в этой машине.
Задача №8
Дана машина Т={ q010q2 , q1 0Rq3 , q2 0Rq2 , q210q1 , q31Lq1 }. Каким будет результат
применения машины Т к конфигурациям U1  1q211011 и U1  101q2101?
Задача №9
Дана машина Т={ q0 0Rq2 , q010q0 , q110q3 , q2 0Lq2 , q21Rq1 }. Вычислите T(1) 3 и
T(2) 0, 2, 4 .
Задача №10
Докажите, что функция  x, y  y  2 вычислима по Тьюрингу.
Задача №11
Запишите аналитическое выражение функции t, x, s , полученной из функций
1 x1 , x2 , x3   S I 21x2 , x3    x1  ,
 x1 , x2   x1  x2 ,
 2 x1 , x2 , x3   x2  S x3   I 32 x1 , x2 , x3  применением оператора суперпозиции.
Задача №12
Функция x, s получена из функций  t   C2 t  и  x, y, z  z  xy применением
оператора примитивной рекурсии. Найдите 3, 4 .
Задача №13
Функция z, x получена из функций   y  SS y и  t, s, z  Sz  ts , применением
оператора примитивной рекурсии. Найдите  4, 3 .
Задача №14
Пусть функция  t   2S t . Найдите  10 и  13, если  x  y  y  x.
Задача №15
Докажите, что функция x  3x является ЧРФ.
1/--страниц
Пожаловаться на содержимое документа