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

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

Сложение чисел 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-сводимо к множеству всех истинных арифметических формул без параметров:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Операция:

h(x₁,x₂,…,x_k,0) = f(x₁,x₂,…,x_k,)h(x₁,x₂,…,x_k,y+1) = g(x₁,x₂,…,x_k,y,h(x₁,x₂,…,x_k,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, для которых существует целое решение уравнения xⁿ+yⁿ=zⁿ всегда:

Множество 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, где U_n - нигде не определена, то U_n:

Функция $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:

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

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

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

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

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

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

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

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

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

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

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

Если , то:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если , то:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношение "" является:

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

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

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

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

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

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

Если , то:

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

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

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

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

Указание - это кортеж , в котором:

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

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

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

Умножение чисел 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$ , то:

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

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

Дополнение к универсальному множеству $\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):

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

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

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

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

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

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

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

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

Указание - это кортеж $\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 \}$ , то это множество:

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

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

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

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

Операция:
h(x₁,x₂,…,x_k,0) = f(x₁,x₂,…,x_k,)h(x₁,x₂,…,x_k,y+1) = g(x₁,x₂,…,x_k,y,h(x₁,x₂,…,x_k,y))
называется:

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

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

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