Главная / Алгоритмы и дискретные структуры / Основы теории вычислимых функций

Основы теории вычислимых функций - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Функция m=f(n), math вычислима, если существует алгоритм A(f):
(1) останавливающийся и печатающий m=f(n)
(2) преобразующий число n в число n+1 для любого m
(3) преобразующий число n в число n+m для любого m
Работу всякой машины Тьюринга промоделировать другой машиной Тьюринга:
(1) можно всегда
(2) нельзя всегда
(3) можно для не вычислимых функций
Операция: h(x1,x2,…,xk,0) = f(x1,x2,…,xk,) h(x1,x2,…,xk,y+1) = g(x1,x2,…,xk,y,h(x1,x2,…,xk,y)) называется:
(1) рекурентностью
(2) рекурсией
(3) итерацией
Функция U(n,m), math - универсальна для класса вычислимых функций одного аргумента, если для каждого n:
(1) math
(2) math
(3) math
Нумерация множества X - это отображение:
(1) всюду определенное math
(2) частично определенное math
(3) заданное на множестве XхN
Если U - главная универсальная функция, а X - множество натуральных чисел n, где Un - нигде не определена, то Un:
(1) неразрешимо
(2) разрешимо
(3) универсально
Если U - главная вычислимая универсальная функция для класса вычислимых одноместных функций, то существует для произвольной вычислимой одноместной функции h:
(1) Un=Uh(n)
(2) Uh=Un(h)
(3) U(h(n))n=U
Для доказательства неразрешимости множества X достаточно доказать, что:
(1) любое перечислимое множество - разрешимо
(2) некоторое перечислимое множество - разрешимо
(3) N перечислимо вместе с X
Если math, то:
(1) Y сводимо к X по Тьюрингу
(2) X сводимо к Y по Тьюрингу
(3) Y сводимо к T по модулю Y
Множество math перечислимо тогда и только тогда, когда:
(1) math - разрешимое
(2) X - проекция Y
(3) X совпадает с N
Машина Тьюринга включает объект:
(1) алфавит
(2) пустой символ
(3) множество выполняемых условных команд перехода
Вычислима функция:
(1) f(n)=sin(n)
(2) f(n)=sign(x+n)
(3) f(n)=n+1
Всякая функция, вычислимая программой с конечным числом переменных:
(1) вычислима на машине Тьюринга
(2) не вычислима на машине Тьюринга
(3) тождественна единице
Функция f(xn)=f(xn-1)+x:
(1) рекурсивна
(2) не рекурсивна
(3) несовершенна
Вычислимая всюду определенная функция двух аргументов, универсальная для класса всех вычислимых функций одного аргумента:
(1) не существует
(2) существует, если всюду определена
(3) существует
Главная универсальная функция:
(1) не существует
(2) существует
(3) определена только для конечных множеств
Если Y - класс вычислимых одноместных функций, а math, то множество math:
(1) разрешимо
(2) неразрешимо
(3) универсально
Если U(n,x) - главная вычислимая универсальная функция для класса всех вычислимых одноместных функций, то тогда:
(1) для всех x существует p: U(p,x)=p
(2) существует одно лишь x и одно лишь p: U(p,x)=p
(3) не для всех x существует p: U(p,x)=p
Если math и Y - разрешимо, то:
(1) X - разрешимо
(2) Y - m-разрешимо
(3) X - не разрешимо
Частичная функция f вычислима относительно всюду определенной функции g тогда и только тогда, когда она:
(1) вычислима относительно math
(2) вычислима относительно math
(3) вычислима относительно math
Свойство A принадлежит классу math, если для некоторого разрешимого свойства В:
(1) math
(2) math
(3) math
Таблица переходов машины Тьюринга - функция:
(1) одного числа
(2) пар чисел
(3) троек чисел
Множество X из N разрешимо, если существует алгоритм:
(1) определения, принадлежит ли math множеству X
(2) вычисления math по заданному math
(3) поиска наибольшего n
Для любых math можно найти такие числа a и b, что:
(1) xi = a mod b(i+1) + 1
(2) xi = a mod b(i+1)
(3) xi = a mod bi + 1
Умножение чисел x, y math реализует рекурсия:
(1) p(x,0)=0, p(x, y)=s(x, y)*x
(2) p(x,0)=0, p(x,y+1)=p(x, y)+x
(3) p(x,x)=0, p(x,y)=p(y,x)
Вычислимая функция со значением {0,1} и не имеющая всюду определенного вычислимого продолжения:
(1) существует
(2) не существует
(3) не определена
Если нумерация является вычислимой, то последовательность math
(1) вычислима
(2) конечна
(3) невычислима
В теореме Успенского - Райса утверждается, что в главной нумерации:
(1) множество номеров любой функции не разрешимо
(2) множество номеров любой функции бесконечно
(3) множество номеров любой функции счетно
Какая программа печатает свой текст?
(1) Паскаль: Writeln('Writeln');
(2) Бейсик: 10 LIST
(3) Паскаль: End.
m-сводящей X к X будет функция:
(1) тождественная
(2) единичная (для любого аргумента равна 1)
(3) характеристическая
Два образца - совместны, если:
(1) объединение их графиков - график функции
(2) пересечение их графиков - график функции
(3) их графики имеют хотя бы одну точку пересечения
Отрицания свойств из класса math:
(1) принадлежат math
(2) принадлежат math
(3) не принадлежат math
Головка машины Тьюринга может передвигаться на:
(1) 1 позицию влево
(2) 1 позицию вправо
(3) n>0 позиций влево
Множество натуральных чисел X перечислимо, если оно:
(1) перечисляется по некоторому алгоритму
(2) сортируемо алгоритмом обменами
(3) счетно
Любое арифметичное множество может лежать в классе:
(1) math
(2) math
(3) универсальном
Примитивно рекурсивно для примитивно рекурсивных операндов:
(1) дополнение
(2) декартово произведение
(3) характеристическая функция
(4) инверсия
Иммунное множество - это множество:
(1) бесконечное
(2) не содержащее бесконечные перечислимые подмножества
(3) содержащее бесконечные перечислимые подмножества
Различным операциям над множествами соответствуют:
(1) вычислимые преобразования номеров
(2) перечислимые операнды операции
(3) различные вычислимые функции
Верно утверждение:
(1) нетривиальные свойства функций - не разрешимы
(2) нетривиальные свойства функций - разрешимы
(3) разрешимые функции имеют только нетривиальные свойства
Теорема о неподвижной точке гарантирует существование:
(1) хотя бы одной неподвижной точки
(2) единственной всегда неподвижной точки
(3) счетного множества неподвижных точек
Неверно для произвольных множеств:
(1) math
(2) math
(3) math
Множеством, перечислимым относительно всюду определенной вычислимой функции f является множество:
(1) область определения f
(2) область изменения f
(3) пар (x, f(x))
Если math, то:
(1) math
(2) math
(3) math
Ассоциативное исчисление - это:
(1) конечный набор любых правил
(2) конечный набор правил-продукций
(3) любой набор слов и словарного запаса языка
Пересечение перечислимых множеств - всегда:
(1) перечислимо
(2) перечислимо или неопределенно
(3) пусто
Множество всех истинных арифметических формул без параметров:
(1) не перечислимо
(2) перечислимо
(3) универсально
Формула х+1 mod n = [if x+1=n then 0 else x+1] :
(1) прибавляет единицу по модулю n
(2) находит остаток от деления x на n
(3) округляет x
Область определения универсальной функции будет:
(1) перечислимым
(2) универсальным
(3) иммунным
Нумерация - вычислима, если вычислима:
(1) универсальная функция
(2) область определения и область изменения
(3) только область определения
Для перечисляемых образцов и вычислимой универсальной функции, множество номеров всех функций, продолжающих хоть один образец:
(1) перечислимо
(2) не перечислимо
(3) пусто
Два главных универсальных множества для класса перечислимых подмножеств N:
(1) вычислимо изоморфны
(2) вычислимо не изоморфны
(3) совпадают
Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:
(1) существует всегда
(2) существует не всегда
(3) не существует всегда
Множество - 0' - разрешимо, если оно:
(1) сводимо к m - полному перечисленному множеству
(2) совпадает с m - перечислимым множеством
(3) не сводимо к m - полному перечисленному множеству
Класс math является:
(1) наследственным вниз
(2) наследственным вверх
(3) наследственным и вниз, и вверх
Если math, то:
(1) Т - разрешимо для любого исчисления
(2) есть исчисление, для которого Т не разрешимо
(3) Т - всегда конечно
Перечислимо всякое множество, если оно:
(1) разрешимо
(2) есть подмножество N
(3) равномощно N
Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:
(1) теорема Геделя
(2) теорема Черча
(3) тезис Тьюринга
Если свойство R(x, y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:
(1) math
(2) math
(3) math
Перечислимое множество с неперечислимым дополнением:
(1) существует
(2) не существует
(3) простое
Вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов:
(1) существует
(2) не существует
(3) аддитивна
Образцом является:
(1) двоичное слово
(2) дельта - функция
(3) характеристическая функция
Структура на множестве X - это отношение типа:
(1) упорядочивания.
(2) транзитивное
(3) рефлексивное
Если универсальное множество - главное, то его:
(1) диагональ - m-полна
(2) дополнение и пересечение с N - тоже
(3) дополнение и объединение с N - тоже
Множества X и Y, для которых math и math:
(1) существует
(2) не существует
(3) несравнимы
Если math, то:
(1) math
(2) math
(3) X и Y - совпадают
Ассоциативное исчисление - двустороннее, если оно содержит правила:
(1) math
(2) math
(3) math
Функция перечислима тогда и только тогда, когда
(1) ее график перечислим
(2) ее график - множество изолированных точек
(3) ее график совпадает с проекцией графика на N
Множество доказательств:
(1) разрешимо
(2) не разрешимо
(3) универсально
Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное время:
(1) примитивно рекурсивна
(2) возвратно рекурсивна
(3) Тьюрингова
Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:
(1) X={x: d(x)=1} - не перечислимо
(2) X={x: d(x)=1} - перечислимо
(3) E(d) - перечислимо
Вычислимые универсальные функции, не являющиеся главными:
(1) существуют
(2) не существуют
(3) обратимыми
Образцом не является (n - натуральное, x - вещественное число):
(1) sign(n+n2)
(2) math
(3) int(x)
Если X=[-2;5], Y=[0;2], то math будет:
(1) числовой функцией
(2) множеством
(3) отображением
Множество X - эффективно бесконечное, если алгоритм конструирования по любому n различных элементов из X:
(1) существует
(2) не существует
(3) существует только для простых n
Фрагмент - это всегда:
(1) функция
(2) множество
(3) отношение
Для любого n в классе math:
(1) существует множество, универсальное для множеств math
(2) не существует множество, универсальное для множеств math
(3) есть класс math
Конкатенация - это операция:
(1) приписывания слова к слову слева
(2) приписывания слова к слову справа
(3) вставки слова в слово
Верно утверждение для множества диафантовых уравнений:
(1) перечислимо, если разрешимы уравнения
(2) перечислимо, если они неразрешимы
(3) всегда перечислимо
Программу А со свойством "никакая программа В не является доказуемо различной с А":
(1) можно построить
(2) нельзя построить
(3) можно верифицировать
Частично рекурсивны функции получаемые из базисных с помощью:
(1) минимизации
(2) характеристической
(3) суперпозиции
Счетное число непересекающихся перечислимых множеств попарно неотделимых разрешимым множеством:
(1) существует
(2) не существует
(3) счетно
По программам функций f и g получить их композицию:
(1) алгоритмически нельзя
(2) алгоритмически можно
(3) можно лишь математически (теоретически)
Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:
(1) существует функция - образец из Y
(2) не существует функции - образца из Y
(3) все вычислимые суперпозиции Y имеют образцы
Отношение "math" является:
(1) симметричным, рефлексивным, транзитивным
(2) симметричным, нерефлексивным, транзитивным
(3) несимметричным, нерефлексивным, транзитивным
Для универсального перечислимого множества W-перечислимо множество:
(1) math
(2) math
(3) math
Элемент - это:
(1) пара множеств
(2) пара любых конечных множеств
(3) пара конечных множеств натуральных чисел
Универсальное math множество:
(1) принадлежит math
(2) не принадлежит math
(3) не существует для всех n
Совокупность элементов X и определённых над ними операции F, удовлетворяющих аксиомам, называется:
(1) арифметикой
(2) алгеброй
(3) множеством
Функция m=f(n), math вычислима, если существует алгоритм A(f):
(1) останавливающийся для неопределенного f(n)
(2) не останавливающийся для неопределенного f(n)
(3) не останавливающийся для определенного f(n)
Лента машины Тьюринга может быть:
(1) бесконечной
(2) только конечной
(3) полубесконечной (бесконечной только в одну сторону)
Функции, получаемые с помощью операций подстановки и рекурсии из константы 0, операции прибавления единицы k штук k-местных функций math называют:
(1) базово рекурсивной
(2) примитивно рекурсивной
(3) универсально рекурсивной
Вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента:
(1) существует
(2) не существует
(3) не определена
Если V(m,x)=U(s(m),x), m, x - любые, то U называется:
(1) определяющей функцией
(2) универсальной функцией
(3) главной универсальной функцией
Множество номеров нигде не определенной функции:
(1) неразрешимо
(2) неперечислимо
(3) разрешимо
Теорема Клини о неподвижной точке:
(1) все программы эквивалентно преобразуемы друг к другу
(2) есть алгоритм преобразования программы к ней эквивалентной
(3) нет алгоритма преобразования программы к ней эквивалентной
Множество math m-сводится к math, если существует:
(1) вычислимая функция y=f(x), где x, y - натуральные:
(2) math
(3) всюду определенная вычислимая math
Если math, то:
(1) math
(2) math
(3) math
Свойство A(x), math перечислимо тогда и только тогда, когда:
(1) math-разрешимое
(2) math-разрешимое
(3) math-неразрешимо
Машина Тьюринга включает объект:
(1) множество состояний
(2) команду присваивания
(3) команду цикла
Вычислима функция:
(1) f(n)=cos(n)
(2) f(n)=n sign(n+x)
(3) f(n)=n-1
График любой функции, вычислимой программой с конечным числом переменных:
(1) является арифметическим множеством
(2) не является арифметическим множеством
(3) представляет прямую линию
Функция f(x,0)=x, f(x,y+1)=f(x,y)+1:
(1) рекурсивна
(2) не рекурсивна
(3) линейна
Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:
(1) существует
(2) не существует
(3) существует, если имеет один аргумент
Последовательность math вычислима, если:
(1) F(i, n)=fi(n) - вычислима
(2) F(i,n)=E(fi) х E(fi) - вычислима
(3) f(i,n) - вычислима
Функция math, где K -перечислимое и неразрешимое, является:
(1) вычислимой
(2) невычислимой
(3) неопределенной
Существует ли Паскаль-программа, инвертирующая свой текст?
(1) да
(2) нет
(3) да, но только для задач обработки текстов
Если math и Y - перечислимо, то:
(1) X - перечислимо
(2) Y - m-разрешимо
(3) X - не перечислимо
Частичная функция вычислима относительно всюду определенной функции тогда и только тогда, когда она:
(1) f вычислима относительно графика g
(2) g вычислима относительно графика f
(3) fg вычислима относительно графиков f и g
Свойство A принадлежит классу math, если для некоторого разрешимого свойства В:
(1) math
(2) math
(3) math
Таблица переходов машины Тьюринга - функция:
(1) math
(2) math
(3) math
Характеристическая функция множества X:
(1) math
(2) math
(3) math
При любом n любое множество из класса math:
(1) арифметично
(2) пусто
(3) универсально
Множество является примитивно рекурсивной, если его характеристическая функция:
(1) примитивно рекурсивна
(2) частично рекурсивна
(3) равна нулю
Два пересекающихся перечислимых множества, не отделимые разрешимым множеством:
(1) существуют
(2) не существуют
(3) не пересекаются
Нумерация - вычислимая, если:
(1) перечислимое math задает нумерацию
(2) math является счетным
(3) X=N
В теореме Роджерса утверждается, что трансляторы, сводящие главные нумерации друг к другу выбираемы:
(1) взаимно обратным образом
(2) взаимно противоположным образом
(3) независимо друг от друга
Если программа на каждом входе зацикливается, то для неё:
(1) справедлив принцип неподвижной точки
(2) не справедлив принцип неподвижной точки
(3) некорректен входной набор
Если f сводит Х к Y, g - Y к Z, то:
(1) math
(2) math
(3) math
Множество X - корректно, если:
(1) в X нет противоречащих троек
(2) в X нет противоположных троек
(3) все тройки принадлежат X
Каждая операция проектирования:
(1) уменьшает размерность на 1
(2) увеличивает размерность на 1
(3) не изменяет размерность
Если входной алфавит машины Тьюринга состоит 0, 1 и пробела, то входным будет:
(1) 01110 11
(2) 110101
(3) 111111
Множество перечислимо, если:
(1) оно есть область определения вычислимой функции
(2) оно состоит только из натуральных чисел
(3) его характеристическая функция имеет значение 0
Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:
(1) всегда
(2) только для math
(3) только для math
Примитивно рекурсивно свойство:
(1) x=y
(2) x2=y2
(3) x>y+sin(x)
Множество - простое, если:
(1) оно перечислимое
(2) его дополнение иммунное
(3) оно конечное
Композиция двух вычислимых функций является:
(1) вычислимой
(2) характеристической
(3) нелинейной
Верно утверждение:
(1) некоторые свойства функций перечислимы
(2) все свойства функций перечислимы
(3) нет перечислимых свойств функции
Если преобразователь программ вычислимо зависит от некоторого параметра, то:
(1) неподвижная точка вычислимо зависима от параметра
(2) неподвижная точка вычислимо независима от параметра
(3) не вычислима неподвижная точка
Неверно для произвольных множеств:
(1) math
(2) math
(3) math
Множество X - math-перечислимо тогда и только тогда, когда для некоторого перечислимого множества E:
(1) math
(2) math
(3) math
Если math, то:
(1) math
(2) math
(3) math
В алфавите X слово P выводимо из слова Q, если:
(1) math
(2) math
(3) math
Объединение перечислимых множеств А и В всегда перечислимо:
(1) для конечных А и В
(2) для всех таких А и В
(3) или универсально
Теорема Тарского:
(1) множество арифметических истин не арифметично
(2) множество арифметических истин не перечислимо
(3) во множестве арифметических истин есть пустое
Рекурсия 0 mod n=0, (x+1) mod n=(x mod n)+1 mod n определяет:
(1) x mod n
(2) n mod x
(3) НОД(x,y)
Равенство f(n)=d(n) может означать, что:
(1) значения f(n) и d(n) не определены
(2) значения f(n) и d(n) определены и равны
(3) f(n) и d(n) тождественны на D(f) и на D(d)
Термину "k - местная" удовлетворяет функция:
(1) f (1,2, ,.., k)
(2) f (x1, x2, …, xk)
(3) f=k
Любое перечислимое свойство:
(1) открыто
(2) замкнуто
(3) гомеоморфно другому
Множество А является I-соответствующей множеству В, если:
(1) В - образ А при биекции I
(2) В - прообраз А при биекции I
(3) биекция I переводит любое подмножество А в В
m-полное множество относительно m-сводимости - это множество:
(1) наибольшее
(2) наименьшее
(3) дополнение
Самая трудная в мире задача разрешения:
(1) существует в единственном числе
(2) не существует
(3) существует в конечном числе
Класс math является:
(1) наследственным вниз
(2) наследственным вверх
(3) наследственным и вниз, и вверх
Инструкции "находясь в состоянии math и читая символ math перейти в состояние для всех math, напечатать символ math и сдвинуться влево" соответствует:
(1) math
(2) math
(3) math
Теорема Поста:
(1) разрешимые множества перечислимы со своими дополнениями
(2) перечислимые множества разрешимы со своими дополнениями
(3) либо само множество, либо его дополнение всегда перечислимо
Утверждение "Любой алгоритм, перечисляющий множество формул арифметики порождает некоторую ложную формулу, либо не порождает некоторой истинной формулы" - это:
(1) теорема о полноте Кантора
(2) теорема о неполноте Геделя
(3) теорема о существовании универсальной машины Тьюринга
Функция f примитивна рекурсивна, если одновременно выполнено:
(1) график f примитивно рекурсивен
(2) значения f ограничены сверху примитивно рекурсивной функцией g
(3) D(f), E(f) - перечислимы
Проблема остановки состоит в выяснении того, что:
(1) программа остановится на данном входе
(2) программа зацикливается на данном входе
(3) программа устойчива
Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:
(1) U(c(p,q),x)=U(p,U(q,x))
(2) U(c(p),c(q),x)=U(p,U(q),x)
(3) U(c(p),q),x)=U(p)U(q,x))
Образцом является:
(1) номера слов по порядку
(2) лексикографически упорядоченный список слов
(3) длины слов расположенные по их возрастанию
Отношение эквивалентности - это отношение:
(1) транзитивное, рефлексивное, симметричное
(2) не транзитивное, рефлексивное, симметричное
(3) транзитивное, не рефлексивное, симметричное
Множество всех самоприменимых программ:
(1) m-полно
(2) не m-полно
(3) пусто
"Оракул" для множества X отвечает на вопрос:
(1) принадлежат ли числа X множеству Y
(2) конечно ли множество X
(3) бесконечно ли множество X
Если math, то:
(1) math
(2) math
(3) X - пусто
Двухстороннее исчисление, для правил которого нет алгоритма, выясняющегося, можно ли получить одно слово из другого:
(1) не существует
(2) существует
(3) неопределенно
Образ множества X для частичной функции f(n) - это:
(1) math
(2) math
(3) math
Парадокс лжеца отражает утверждение:
(1) данный вариант ответа неправильный
(2) данный вариант ответа правильный
(3) утверждение, высказанное в этом варианте - ложно
Функции, вычисляемые программой с полным ветвлением и циклом "для", но без циклов "пока":
(1) примитивно рекурсивны
(2) не примитивно рекурсивны
(3) просты
Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:
(1) X={x: d(x)=0} - не перечислимо
(2) X={x: d(x)=0} - перечислимо
(3) E(d) - неперечислимо
По любому номеру любого вычислимого действительного числа, номер вычислимой функции десятичного его разложения:
(1) можно построить
(2) нельзя построить
(3) можно упростить
Образец является:
(1) конструктивным объектом
(2) конструктивной функцией
(3) конструктивным множеством
Если X=[0;3], Y=[3;0], то math будет:
(1) числом
(2) отображением
(3) множеством
Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f:
(1) math
(2) math
(3) math
Множество X согласовано с фрагментом x, если:
(1) дополнение X продолжает x
(2) характеристическая функция X продолжает x
(3) x принадлежит X
Свойства класса math имеют вид:
(1) math-разрешимое свойство
(2) math-разрешимое свойство
(3) math-разрешимое свойство
Свободная полугруппа - это полугруппа:
(1) слов с операцией конкатенации
(2) слов с операцией вставки
(3) в которой еще не определена операция
Всякое бесконечное перечислимое множество:
(1) содержит разрешимое множество
(2) разрешимо
(3) неразрешимо
Непознаваемая программа:
(1) существует
(2) не существует
(3) тестируема
Частично рекурсивная и всюду определенная функция называется:
(1) общерекурсивной
(2) определенно рекурсивной
(3) совершенно рекурсивной
(4) эквивалентностью
Бесконечное множество, не содержащее бесконечных разрешимых подмножеств является:
(1) иммунным
(2) несчетным
(3) счетным
Для описания свойств вычислимых функций, из перечисленных ниже наиболее подходит язык:
(1) Рефал
(2) Паскаль
(3) Бейсик
Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
(1) math
(2) math
(3) math
Отношение "math" является:
(1) симметричным, рефлексивным, транзитивным
(2) симметричным, нерефлексивным, транзитивным
(3) несимметричным, рефлексивным, транзитивным
Множества с эффективно неперечислимыми дополнениями:
(1) существуют
(2) не существуют
(3) не существуют только для простых дополнений
Элемент math продолжает элемент math, если:
(1) math
(2) math
(3) math
Универсальное math множество:
(1) не принадлежит math
(2) принадлежит math
(3) не существует для всех n
Совокупность операций алгебры A называется:
(1) кортежем
(2) носителем
(3) сигнатурой
Функция m=f(n), math вычислима, если существует алгоритм A(f):
(1) останавливающийся для определенного f(n)
(2) не останавливающийся для неопределенного f(n)
(3) вычисляющий цифры m
Стек - это:
(1) структура данных
(2) структура команд
(3) устройство установки
Функция fn(x)=fn-1(x)+x:
(1) рекурсивна
(2) не рекурсивна
(3) совершенна
Множество X из N×N - универсальное, если:
(1) все сечения принадлежит этому классу
(2) других множеств в классе нет
(3) все сечения из этого класса и других множеств в классе нет
Нумерация, соответствующая главной универсальной функции называется:
(1) геделевой
(2) тьюринговой
(3) постовской
Если дополнение неразрешимого множества перечислимо, то само множество:
(1) перечислимо
(2) не перечислимо
(3) универсально
Программа, печатающая свой текст:
(1) реализуема на всех современных процедурных языках
(2) нереализуема ни на одном процедурном языке
(3) реализуема только в "рекурсивных" языках (например, Рефал)
Для m-сводящей X к Y функции f используют обозначение:
(1) math
(2) math
(3) math
Если math, то:
(1) math
(2) math
(3) math
Если B(x,y) - некоторое разрешимое свойство, то свойства вида math определяют свойства:
(1) отрицания которых перечислимы
(2) отрицания которых не перечислимы
(3) дополнения которых перечислимы
Машина Тьюринга включает объект:
(1) таблицу выходных сигналов
(2) таблицу переходов
(3) заключительное состояние
Не вычислима функция:
(1) f(n)=1
(2) f(n)=sign(n+1)
(3) f(n)=n
Для любого k и последовательности b+1, 2b+2, 3b+1, … (b<0 - некоторое целое):
(1) попарно просты b и числа b+1, 2b+2, 3b+1,…, kb+1
(2) просты все числа b+1, 2b+2, 3b+1, …, kb+1
(3) кратны попарно числа (k, b), (b+1, kb+1)
Сложение чисел x, y math реализует рекурсия:
(1) s(x,0)=x, s(x,y+1)=s(x, y)+1
(2) s(x,0)=0, s(x,y+1)=s(x, y)
(3) s(x,x)=0, s(x,y)=1
Перечислимое неразрешимое множество;
(1) существует
(2) не существует
(3) существует, если перечислимо его дополнение
Последовательность math вычислима, если существует:
(1) конечный ряд сi, i=0, 1, …, n, ci=fi
(2) вычислимая f(i) , i=1,2,…
(3) вычислимые ci, i=0,1,… , где ci - номер fi
Универсальную вычислимую функцию, для которой каждая вычислимая функция имеет ровно один номер:
(1) можно построить алгоритмически
(2) нельзя построить алгоритмически
(3) можно описать математически, но не алгоритмически
Существуют ли Паскаль-программы А и В, печатающие, соответственно, тексты В и А?
(1) да
(2) нет
(3) да, но только для задач обработки текстов
Если math и math, то:
(1) math
(2) math
(3) math
Образец - это функция из N в N, определенная:
(1) на всем N
(2) на конечном подмножестве N
(3) не для всех множеств из N
Отрицания свойств из класса math:
(1) принадлежат math
(2) принадлежат math
(3) не принадлежат math
Конфигурация машины Тьюринга в каждый момент времени складывается из:
(1) содержимого ленты
(2) текущей позиции головки
(3) текущего состояния машины
Множество натуральных чисел X разрешимо, если:
(1) вычислима math для math
(2) вычислима math для math
(3) оно универсально
При любом n любое множество из класса math:
(1) не арифметично
(2) арифметично
(3) пусто
Примитивно рекурсивно для примитивно рекурсивных операндов:
(1) перечисление
(2) объединение
(3) декартово произведение
Счетное число непересекающихся перечислимых множеств, никакие два из которых неотделимы разрешимым множеством:
(1) существуют
(2) не существуют
(3) не пересекаются
Универсальное перечислимое множество из N × N:
(1) не существует
(2) существует
(3) существует и несчетно
Любые две нумерации перечислимых множеств:
(1) изоморфны
(2) гомеоморфны
(3) взаимообратны
Теорема о неподвижной точке называется также теоремой:
(1) о рекурсии
(2) об итерации
(3) стабильности
Если f сводит Х к Y, то она сводит:
(1) N\X к N\Y
(2) math к math
(3) math к math
Процедура замены вычислимых функции на функции, вычислимые относительно всюду определенной функции называется:
(1) реляционной
(2) релятивизацией
(3) реальной
Если math, то:
(1) math
(2) math
(3) math
Тезис Тьюринга:
(1) всякая функция вычислима на машине Тьюринга
(2) всякая вычислимая функция вычислима на машине Тьюринга
(3) всякая вычислимая функция моделирует машину Тьюринга
Множество перечислимо, если оно:
(1) есть область значений вычислимой функции
(2) содержит область значений вычислимой функции
(3) совершенно
Множество всех истинных арифметических формул без параметров:
(1) арифметично
(2) не арифметично
(3) универсально
Примитивно рекурсивно свойство:
(1) x>y
(2) math
(3) x=x+6
Простое множество:
(1) всегда существует
(2) не всегда существует
(3) совпадает с его дополнением
Всякая универсальная функция для класса вычислимых одноместных функций задает:
(1) нумерацию класса
(2) характеристическую функцию класса
(3) отношение эквивалентности
Верно утверждение:
(1) образец - конечный список пар <аргумент, значение>
(2) образец - функция характеристическая
(3) образец - подмножество множества пар <смысл, значение>
По любой вычислимой функции можно указать:
(1) бесконечно много неподвижных точек
(2) лишь конечное множество неподвижных точек
(3) бесконечно много точек, где не определена функция
Неверно для произвольных множеств:
(1) math
(2) math
(3) math
Для math - всюду определенной функции, math-вычислимая функция двух аргументов являющаяся универсальной:
(1) не существует
(2) существует
(3) универсальна
Если math, то:
(1) math
(2) math
(3) math
Если math, то это множество:
(1) перечислимо
(2) не перечислимо
(3) универсально
Декартово произведение перечислимых множеств А и В перечислимо:
(1) если math
(2) всегда
(3) или неопределенно всегда
Теорема Геделя:
(1) множество арифметических истин не арифметично
(2) множество арифметических истин не перечислимо
(3) арифметика - перечислима
Если свойство R(x,y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:
(1) math
(2) math
(3) math
Равенство f(n)=U(n,n) определяет:
(1) диагональную функцию
(2) диаметр множества N
(3) декартово произведение
Если функция f дает по номеру m функции другой номер s этой функции, то:
(1) fm=fs(m)
(2) fs=fm
(3) fm(s)=fs
Образец - это:
(1) функция с натуральными аргументами
(2) множество из натуральных чисел
(3) свойство вычислимых функций
В языке Паскаль существует ряд программ Pi, i=1,2,…,n таких, что:
(1) каждая предыдущая в ряде может печатать следующую
(2) каждая следующая в ряде печатает предыдущую
(3) каждая предыдущая не сможет напечатать предыдущую
m-полнота - это отношение:
(1) транзитивное
(2) не транзитивное
(3) нерефлексивное
Любые два множества:
(1) несравнимы
(2) сравнимы
(3) сравнимы по модулю
Если math, то:
(1) math
(2) math
(3) X и Y - совпадают
Инструкция "находясь в состоянии s и читая символ x, перейти в состояние p, напечатать символ y и сдвинуться вправо" порождает правило:
(1) math
(2) math
(3) math
Множество X из N перечислимо тогда и только тогда, когда:
(1) X - проекция некоторого разрешимого множества
(2) Y - множество натуральных чисел
(3) верно и а), и б)
Если в одноместную формулу с номером n подставить значение n, то получим:
(1) формулу без параметра
(2) истинное высказывание
(3) ложное высказывание
Выводящие из класса примитивно рекурсивных функций схемы рекурсии:
(1) не существует
(2) существует
(3) не определены
Непересекающиеся множества X и Y отделяются множеством Z, если:
(1) math
(2) math
(3) math
Определению главной универсальной функции адекватно утверждение:
(1) существует транслятор с языка, для которого есть интерпретатор
(2) существует интерпретатор с любого компилятора
(3) не существует транслятора с языка, у которого есть интерпретатор
Образцом является (n - натуральное, x - вещественное число):
(1) sign(n)
(2) math
(3) sin(x)
Отношение эквивалентности - это всегда отношение:
(1) классифицирующее
(2) не классифицирующее
(3) над декартовым произведением
Множество всех программ, останавливающихся хотя бы на одном входе является:
(1) m-полным
(2) не m-полным
(3) универсальным
"Оракул" для множества X может быть реализован вызовом внешней:
(1) функции
(2) процедуры
(3) записи
Классы math и math:
(1) совпадают при одинаковых n
(2) различаются при различных n
(3) совпадают для простых n
Непустое множество с ассоциативной операцией типа умножения и единичным элементом называется:
(1) группой
(2) полугруппой
(3) полем
Прообраз множества X для частичной функции f(n) - это:
(1) math
(2) math
(3) math
Две программы A, В доказуемо различны, если:
(1) есть вход с различными результатами А и В
(2) нет входа с различными результатами А и В
(3) верифицированы A и В
Частично рекурсивны функции, получаемые из базисных с помощью:
(1) подстановки
(2) примитивной рекурсии
(3) итерации
Если два множества неотделимы разрешимыми множествами, то:
(1) ни одно из них неразрешимо
(2) каждая из них разрешима
(3) либо оба разрешимы, либо оба неразрешимы
Для любого перечислимого множества X из декартового квадрата N существует вычислимая math:
(1) math
(2) math
(3) math
Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:
(1) вычислимое продолжение функции Y принадлежит Y
(2) вычислимое продолжение функции Y не принадлежит Y
(3) вычислимые композиции функций Y принадлежат Y
Соответствие - это:
(1) порядок
(2) отображение
(3) множество
Если math и X - эффективно неперечислимо, то:
(1) math и X\Y - эффективно неперечислимы
(2) math и X\Y - эффективно неперечислимы
(3) Y - эффективно неперечислима
Несравнимые по Тьюрингу перечислимые множества:
(1) не существуют
(2) существуют
(3) не пересекаются
Дополнение к универсальному множеству math будет:
(1) универсальным для math
(2) универсальным для math
(3) пустым
Гомоморфизм полугрупп - это отображение:
(1) мультипликативное, с неподвижной точкой x=1
(2) ассоциативное, с неподвижной точкой x=1
(3) обратимое
Множество всех показателей n, для которых существует целое решение уравнения xn+yn=zn всегда:
(1) перечислимо
(2) пусто
(3) совпадает с N
Утверждение: "Средствами формальной системы нельзя доказать ее непротиворечивость" - это:
(1) первая теорема Геделя
(2) вторая теорема Геделя
(3) десятая проблема Гильберта
Всякая частично рекурсивная функция:
(1) вычислима на машине Тьюринга
(2) представима в виде f(x)=xf(x - 1)
(3) регулярна
Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:
(1) определенным
(2) простым
(3) универсальным
Верны утверждения:
(1) всякая универсальная функция для класса вычислимых одноместных функций задает нумерацию класса
(2) существует универсальное перечислимое подмножество декартова квадрата множества натуральных чисел
(3) нумерацию класса можно задать любой однозначной функцией
Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
(1) math
(2) math
(3) math
Отношение "math" является:
(1) рефлексивным
(2) симметричным
(3) антисимметричным
Перечислимое множество m-полно тогда и только тогда, когда его дополнение:
(1) эффективно неперечислимо
(2) эффективно перечислимо
(3) совпадает с ним
Указание - это кортеж math, в котором:
(1) math
(2) math
(3) math
Класс эквивалентных множеств называют:
(1) m - разностью
(2) m - степенью
(3) эквивалентностью
Совокупность операндов алгебры A называется:
(1) кортежем
(2) носителем
(3) множеством