1)Что не является математическим определением алгоритма Выберите один ответ: a. теория рекурсивных функций b. нормальный алгоритм Маркова c. машина Тьюринга d. теория множеств 2)Функцию Х & Y всегда можно получить из суперпозиции функций системы { 0, 1, X, Y, 7X, 7Y, f(X1,…Xn ), если Выберите один ответ: a. функция f( X1,…,Xn ) будет линейная b. функция f( X1,…,Xn ) будет нелинейная c. функция f( X1,…,Xn ) = Xi d. функция f( X1,…,Xn ) будет константой 3)Правило вывода – правило заключения (Modus Ponens) это Выберите один ответ: a. A следует B |--- 7A следует 7B b. A следуетB , B следует C |--- A следует C c. A следует B |--- 7B следует 7A d. A , A следует B |--- B 4)Какая запись не может являться командой машины Тьюринга с состоянием останова qZ Выберите один ответ: a. a2q2 следует a1q1L b. a1q2 следует a3qZR c. a1q2 следует a3q1R d. a1q2 следует a4q1S 5)Для слова 101 в алфавите А = { 0 , 1 } Гёделевским номером будет число Выберите один ответ: a. 18 b. 5 c. 300 d. 10
