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

Заказать решение
Количество вопросов 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 для частичной функции 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):

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

Свойство A принадлежит классу \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 является:

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

Для любых х_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 и сдвинуться влево" соответствует:

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

Если свойство 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, если:

перейти к ответу ->>

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

перейти к ответу ->>

Функция 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 называют:

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>

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

перейти к ответу ->>