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

Количество вопросов - 264

Существует ли Паскаль-программа, инвертирующая свой текст?

Сложение чисел x, y ((x,y) \to x+y) реализует рекурсия:

Характеристическая функция множества X:

Образцом является:

Нумерация множества X - это отображение:

Счетное число непересекающихся перечислимых множеств попарно неотделимых разрешимым множеством:

Умножение чисел x, y ((x,y) \to x*y) реализует рекурсия:

Теорема Поста:

Множества X и Y, для которых X\neg \le_T Y и Y\neg \le_T X:

Если два множества неотделимы разрешимыми множествами, то:

Если X \le_m Y,Y \in \Pi_n, то:

Пересечение перечислимых множеств - всегда:

Какая программа печатает свой текст?

Прообраз множества X для частичной функции f(n) - это:

Последовательность i \mapsto f_i вычислима, если существует:

Множество X \subset N перечислимо тогда и только тогда, когда:

Элемент - это:

Для универсального перечислимого множества W-перечислимо множество:

Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f:

Частичная функция вычислима относительно всюду определенной функции тогда и только тогда, когда она:

Дополнение к универсальному множеству \Pi_2 будет:

Самая трудная в мире задача разрешения:

Определению главной универсальной функции адекватно утверждение:

Отношение эквивалентности - это всегда отношение:

Таблица переходов машины Тьюринга - функция:

Отрицания свойств из класса \Sigma_n:

Если дополнение неразрешимого множества перечислимо, то само множество:

Функция m=f(n), m,n \in N вычислима, если существует алгоритм A(f):

В теореме Роджерса утверждается, что трансляторы, сводящие главные нумерации друг к другу выбираемы:

Если X \le_T Y, то:

Функция m=f(n), m,n \in N вычислима, если существует алгоритм A(f):

Вычислима функция:

Множество X из N разрешимо, если существует алгоритм:

Множество перечислимо, если:

Объединение перечислимых множеств А и В всегда перечислимо:

Множество X из N перечислимо тогда и только тогда, когда:

Функция перечислима тогда и только тогда, когда

Всякое бесконечное перечислимое множество:

Вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента:

Перечислимое неразрешимое множество;

Счетное число непересекающихся перечислимых множеств, никакие два из которых неотделимы разрешимым множеством:

Множество - простое, если:

Равенство f(n)=d(n) может означать, что:

Непересекающиеся множества X и Y отделяются множеством Z, если:

Бесконечное множество, не содержащее бесконечных разрешимых подмножеств является:

Нумерация, соответствующая главной универсальной функции называется:

Последовательность i \mapsto f_i вычислима, если:

Если нумерация является вычислимой, то последовательность i \mapsto f_i

Всякая универсальная функция для класса вычислимых одноместных функций задает:

Если функция f дает по номеру m функции другой номер s этой функции, то:

Вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов:

По любому номеру любого вычислимого действительного числа, номер вычислимой функции десятичного его разложения:

По программам функций f и g получить их композицию:

Множество номеров нигде не определенной функции:

Если Y - класс вычислимых одноместных функций, а X \subset Y, то множество \{n\colon U_n \in X\}:

Любые две нумерации перечислимых множеств:

Верно утверждение:

Для перечисляемых образцов и вычислимой универсальной функции, множество номеров всех функций, продолжающих хоть один образец:

Образец является:

Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

Теорема Клини о неподвижной точке:

Существуют ли Паскаль-программы А и В, печатающие, соответственно, тексты В и А?

По любой вычислимой функции можно указать:

Два главных универсальных множества для класса перечислимых подмножеств N:

Если X=[0;3], Y=[3;0], то  f\colon X\to Y будет:

Отношение "x\mod y=0,  x, y \in N" является:

Для m-сводящей X к Y функции f используют обозначение:

Если X \le_m Y и Y - перечислимо, то:

Если f сводит Х к Y, то она сводит:

Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:

Если универсальное множество - главное, то его:

Если Y \le_m X, то:

Два образца - совместны, если:

Множество X - \alpha-перечислимо тогда и только тогда, когда для некоторого перечислимого множества E:

"Оракул" для множества X может быть реализован вызовом внешней:

Несравнимые по Тьюрингу перечислимые множества:

Указание - это кортеж \langle A^+,A^-,B^+,B^- \rangle, в котором:

Если B(x,y) - некоторое разрешимое свойство, то свойства вида A(x) \Leftrightarrow \forall y : B(x,y) определяют свойства:

Свойство A принадлежит классу \Pi_n, если для некоторого разрешимого свойства В:

Если  X,Y \in \Sigma_n, то:

Если X,Y \in \Pi_n, то:

Класс \Sigma_n является:

Для любого n в классе \Sigma_n:

Универсальное \Sigma_n множество:

Машина Тьюринга включает объект:

Таблица переходов машины Тьюринга - функция:

Головка машины Тьюринга может передвигаться на:

Если T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}, то это множество:

Инструкция "находясь в состоянии s и читая символ x, перейти в состояние p, напечатать символ y и сдвинуться вправо" порождает правило:

Ассоциативное исчисление - двустороннее, если оно содержит правила:

Конкатенация - это операция:

Совокупность операндов алгебры A называется:

Стек - это:

Для любого k и последовательности b+1, 2b+2, 3b+1, … (b<0 - некоторое целое):

При любом n любое множество из класса \Pi_n:

Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:

Теорема Геделя:

Утверждение "Любой алгоритм, перечисляющий множество формул арифметики порождает некоторую ложную формулу, либо не порождает некоторой истинной формулы" - это:

Множество доказательств:

Непознаваемая программа:

Функция fn(x)=fn-1(x)+x:

Примитивно рекурсивно свойство:

Формула х+1 mod n = [if x+1=n then 0 else x+1] :

Выводящие из класса примитивно рекурсивных функций схемы рекурсии:

Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное время:

Частично рекурсивны функции получаемые из базисных с помощью:

Множество является примитивно рекурсивной, если его характеристическая функция:

Если преобразователь программ вычислимо зависит от некоторого параметра, то:

Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:

Машина Тьюринга включает объект:

Теорема о неподвижной точке называется также теоремой:

В языке Паскаль существует ряд программ Pi, i=1,2,…,n таких, что:

Свободная полугруппа - это полугруппа:

Если f сводит Х к Y, g - Y к Z, то:

Конфигурация машины Тьюринга в каждый момент времени складывается из:

Лента машины Тьюринга может быть:

Функция f(xn)=f(xn-1)+x:

Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:

Неверно для произвольных множеств:
(Ответ считается верным, если отмечены все правильные варианты ответов.)

Теорема Тарского:

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

Множество - 0' - разрешимо, если оно:

Множество натуральных чисел X перечислимо, если оно:

Вычислимые универсальные функции, не являющиеся главными:

Операция:
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))
называется:

Верны утверждения:

"Оракул" для множества X отвечает на вопрос:

Всякая функция, вычислимая программой с конечным числом переменных:

Множество X - корректно, если:

Рекурсия 0 mod n=0, (x+1) mod n=(x mod n)+1 mod n определяет:

Тезис Тьюринга:

Область определения универсальной функции будет:

Отношение "х+5=y, x,y \in N" является:

Если X=[-2;5], Y=[0;2], то f\colon X \to Y будет:

Верно утверждение для множества диафантовых уравнений:

Нумерация - вычислимая, если:

Если в одноместную формулу с номером n подставить значение n, то получим:

Вычислима функция:

Множество перечислимо, если оно:

Множество всех показателей n, для которых существует целое решение уравнения xn+yn=zn всегда:

Множество X из N×N - универсальное, если:

Вычислимая всюду определенная функция двух аргументов, универсальная для класса всех вычислимых функций одного аргумента:

Два пересекающихся перечислимых множества, не отделимые разрешимым множеством:

Простое множество:

Равенство f(n)=U(n,n) определяет:

Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

Различным операциям над множествами соответствуют:

Для описания свойств вычислимых функций, из перечисленных ниже наиболее подходит язык:

Универсальную вычислимую функцию, для которой каждая вычислимая функция имеет ровно один номер:

Верно утверждение:

Любое перечислимое свойство:

Образцом является (n - натуральное, x - вещественное число):

Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:

Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:

Если U - главная вычислимая универсальная функция для класса вычислимых одноместных функций, то существует для произвольной вычислимой одноместной функции h:

Теорема о неподвижной точке гарантирует существование:

Множество А является I-соответствующей множеству В, если:

Соответствие - это:

Множество X \subset N m-сводится к Y \subset N, если существует:

Неверно для произвольных множеств:

m-полнота - это отношение:

Если  X \le_m Y и X - эффективно неперечислимо, то:

Множества с эффективно неперечислимыми дополнениями:

Образец - это функция из N в N, определенная:

Процедура замены вычислимых функции на функции, вычислимые относительно всюду определенной функции называется:

Для \alpha - всюду определенной функции, \alpha-вычислимая функция двух аргументов являющаяся универсальной:

Множество X согласовано с фрагментом x, если:

Свойство A принадлежит классу \Sigma_n, если для некоторого разрешимого свойства В:

Каждая операция проектирования:

Класс \Pi_n является:

Если X \in \Sigma_n, то:

Класс эквивалентных множеств называют:

Машина Тьюринга включает объект:

Если входной алфавит машины Тьюринга состоит 0, 1 и пробела, то входным будет:

В алфавите X слово P выводимо из слова Q, если:

Если T = \{(x,y)\colon x \in s(X),y \in s(Y), x \to y \}, то:

Непустое множество с ассоциативной операцией типа умножения и единичным элементом называется:

Работу всякой машины Тьюринга промоделировать другой машиной Тьюринга:

График любой функции, вычислимой программой с конечным числом переменных:

Для любых х_0, х_1, \ldots , х_n \in N можно найти такие числа a и b, что:

Парадокс лжеца отражает утверждение:

Программу А со свойством "никакая программа В не является доказуемо различной с А":

Примитивно рекурсивно для примитивно рекурсивных операндов:

Примитивно рекурсивно свойство:

Если свойство R(x,y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:

Функция f примитивна рекурсивна, если одновременно выполнено:

Функции, вычисляемые программой с полным ветвлением и циклом "для", но без циклов "пока":

Множество всех программ, останавливающихся хотя бы на одном входе является:

Совокупность операций алгебры A называется:

Инструкции "находясь в состоянии s \in S и читая символ x \in X перейти в состояние для всех z \in X,p \in S, напечатать символ y \in X и сдвинуться влево" соответствует:

Если Y \le_m X, то:

Всякая частично рекурсивная функция:

Множество всех истинных арифметических формул без параметров:

Образцом является:

Отношение эквивалентности - это отношение:

Утверждение: "Средствами формальной системы нельзя доказать ее непротиворечивость" - это:

Если X \le_m Y и Y \le_m Z, то:

Если свойство R(x, y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:

Образ множества X для частичной функции f(n) - это:

Вычислимая функция со значением {0,1} и не имеющая всюду определенного вычислимого продолжения:

Проблема остановки состоит в выяснении того, что:

Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:

Если V(m,x)=U(s(m),x), m, x - любые, то U называется:

Термину "k - местная" удовлетворяет функция:

Если U - главная универсальная функция, а X - множество натуральных чисел n, где Un - нигде не определена, то Un:

Функция f(n,x)=\{\mbox{if } n \in K \mbox{ then } \xi (x) \mbox{ else неопределенно} \}, где K -перечислимое и неразрешимое, является:

Структура на множестве X - это отношение типа:

Множество X - эффективно бесконечное, если алгоритм конструирования по любому n различных элементов из X:

Множеством, перечислимым относительно всюду определенной вычислимой функции f является множество:

Элемент \langle C,D \rangle продолжает элемент \langle A,B\rangle, если:

Если  X \le_m Y,Y \in \Sigma_n, то:

Классы \Sigma_n и \Pi_n:

Ассоциативное исчисление - это:

Функция f(x,0)=x, f(x,y+1)=f(x,y)+1:

Частично рекурсивны функции, получаемые из базисных с помощью:

Частично рекурсивная и всюду определенная функция называется:

Декартово произведение перечислимых множеств А и В перечислимо:

Отрицания свойств из класса \Pi_n:

Нумерация - вычислима, если вычислима:

Множество всех истинных арифметических формул без параметров:

Любое арифметичное множество может лежать в классе:

Свойства класса \Pi_2 имеют вид:

Перечислимое множество m-полно тогда и только тогда, когда его дополнение:

Функции, получаемые с помощью операций подстановки и рекурсии из константы 0, операции прибавления единицы k штук k-местных функций (x_1,x_2, \ldots ,x_n) \to x_i называют:

Если  X,Y \in \Sigma_n, то:

В теореме Успенского - Райса утверждается, что в главной нумерации:

Частичная функция f вычислима относительно всюду определенной функции g тогда и только тогда, когда она:

Функция m=f(n), m,n \in N вычислима, если существует алгоритм A(f):

Не вычислима функция:

Иммунное множество - это множество:

Композиция двух вычислимых функций является:

Для любого перечислимого множества X из декартового квадрата N существует вычислимая f\colon N \to N :

Если программа на каждом входе зацикливается, то для неё:

m-полное множество относительно m-сводимости - это множество:

Любые два множества:

Фрагмент - это всегда:

Гомоморфизм полугрупп - это отображение:

Совокупность элементов X и определённых над ними операции F, удовлетворяющих аксиомам, называется:

Если X,Y \in \Pi_n, то:

Верно утверждение:

Функция U(n,m), n,m \in N - универсальна для класса вычислимых функций одного аргумента, если для каждого n:

m-сводящей X к X будет функция:

Неверно для произвольных множеств:

Множество всех самоприменимых программ:

Свойство A(x), x \in N перечислимо тогда и только тогда, когда:

Универсальное \Pi_n множество:

Примитивно рекурсивно для примитивно рекурсивных операндов:

Для доказательства неразрешимости множества X достаточно доказать, что:

Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:

Перечислимое множество с неперечислимым дополнением:

Множество натуральных чисел X разрешимо, если:

Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:

Образец - это:

При любом n любое множество из класса \Sigma_n:

Программа, печатающая свой текст:

Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:

Если U(n,x) - главная вычислимая универсальная функция для класса всех вычислимых одноместных функций, то тогда:

Главная универсальная функция:

Отношение "x>y, x, y \in N" является:

Перечислимо всякое множество, если оно:

Образцом не является (n - натуральное, x - вещественное число):

Если X \le_m Y и Y - разрешимо, то:

Две программы A, В доказуемо различны, если:

Универсальное перечислимое множество из N × N: