Главная /
Основы теории вычислимых функций
Основы теории вычислимых функций - ответы на тесты Интуит
Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции).
Список вопросов:
-
#
Функция m=f(n),
![math]()
вычислима, если существует алгоритм A(f):
-
#
Функция m=f(n),
![math]()
вычислима, если существует алгоритм A(f):
-
#
Функция m=f(n),
![math]()
вычислима, если существует алгоритм A(f):
- # Вычислима функция:
- # Вычислима функция:
- # Не вычислима функция:
- # Множество X из N разрешимо, если существует алгоритм:
- # Характеристическая функция множества X:
- # Множество натуральных чисел X разрешимо, если:
- # Множество натуральных чисел X перечислимо, если оно:
- # Множество перечислимо, если:
- # Множество перечислимо, если оно:
- # Пересечение перечислимых множеств - всегда:
- # Объединение перечислимых множеств А и В всегда перечислимо:
- # Декартово произведение перечислимых множеств А и В перечислимо:
- # Перечислимо всякое множество, если оно:
- # Теорема Поста:
- # Множество X из N перечислимо тогда и только тогда, когда:
- # Функция перечислима тогда и только тогда, когда
- # Образ множества X для частичной функции f(n) - это:
- # Прообраз множества X для частичной функции f(n) - это:
- # Верно утверждение для множества диафантовых уравнений:
- # Всякое бесконечное перечислимое множество:
- # Множество всех показателей n, для которых существует целое решение уравнения xn+yn=zn всегда:
- # Работу всякой машины Тьюринга промоделировать другой машиной Тьюринга:
- # Лента машины Тьюринга может быть:
- # Стек - это:
- # Всякая функция, вычислимая программой с конечным числом переменных:
- # График любой функции, вычислимой программой с конечным числом переменных:
- # Для любого k и последовательности b+1, 2b+2, 3b+1, … (b<0 - некоторое целое):
-
#
Для любых
![math]()
можно найти такие числа a и b, что:
-
#
При любом n любое множество из класса
![math]()
:
-
#
При любом n любое множество из класса
![math]()
:
- # Любое арифметичное множество может лежать в классе:
- # Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:
- # Множество всех истинных арифметических формул без параметров:
- # Множество всех истинных арифметических формул без параметров:
- # Теорема Тарского:
- # Теорема Геделя:
- # Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:
- # Утверждение "Любой алгоритм, перечисляющий множество формул арифметики порождает некоторую ложную формулу, либо не порождает некоторой истинной формулы" - это:
- # Если в одноместную формулу с номером n подставить значение n, то получим:
- # Множество доказательств:
- # Парадокс лжеца отражает утверждение:
- # Две программы A, В доказуемо различны, если:
- # Программу А со свойством "никакая программа В не является доказуемо различной с А":
- # Непознаваемая программа:
- # Утверждение: "Средствами формальной системы нельзя доказать ее непротиворечивость" - это:
- # Операция: 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)) называется:
-
#
Функции, получаемые с помощью операций подстановки и рекурсии из константы 0, операции прибавления единицы k штук k-местных функций
![math]()
называют:
- # Функция fn(x)=fn-1(x)+x:
- # Функция f(xn)=f(xn-1)+x:
- # Функция f(x,0)=x, f(x,y+1)=f(x,y)+1:
-
#
Сложение чисел x, y
![math]()
реализует рекурсия:
-
#
Умножение чисел x, y
![math]()
реализует рекурсия:
- # Множество является примитивно рекурсивной, если его характеристическая функция:
- # Примитивно рекурсивно для примитивно рекурсивных операндов:
- # Примитивно рекурсивно для примитивно рекурсивных операндов:
- # Примитивно рекурсивно свойство:
- # Примитивно рекурсивно свойство:
- # Формула х+1 mod n = [if x+1=n then 0 else x+1] :
- # Рекурсия 0 mod n=0, (x+1) mod n=(x mod n)+1 mod n определяет:
- # Если свойство R(x,y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:
- # Если свойство R(x, y) - примитивно рекурсивно, то примитивно рекурсивно и свойство:
- # Функция f примитивна рекурсивна, если одновременно выполнено:
- # Выводящие из класса примитивно рекурсивных функций схемы рекурсии:
- # Любая функция, вычислимая на машине Тьюринга не более чем за примитивно рекурсивное время:
- # Функции, вычисляемые программой с полным ветвлением и циклом "для", но без циклов "пока":
- # Частично рекурсивны функции, получаемые из базисных с помощью:
- # Частично рекурсивны функции получаемые из базисных с помощью:
- # Частично рекурсивная и всюду определенная функция называется:
- # Всякая частично рекурсивная функция:
-
#
Функция U(n,m),
![math]()
- универсальна для класса вычислимых функций одного аргумента, если для каждого n:
- # Вычислимая функция двух аргументов, являющаяся универсальной функцией для класса вычислимых функций одного аргумента:
- # Множество X из N×N - универсальное, если:
- # Вычислимая всюду определенная функция двух аргументов, универсальная для класса всех вычислимых функций одного аргумента:
- # Вычислимая функция, не имеющая всюду определенного вычислимого продолжения:
- # Перечислимое неразрешимое множество;
- # Вычислимая функция со значением {0,1} и не имеющая всюду определенного вычислимого продолжения:
- # Два пересекающихся перечислимых множества, не отделимые разрешимым множеством:
- # Счетное число непересекающихся перечислимых множеств, никакие два из которых неотделимы разрешимым множеством:
- # Иммунное множество - это множество:
- # Множество - простое, если:
- # Простое множество:
- # Область определения универсальной функции будет:
- # Равенство f(n)=d(n) может означать, что:
- # Равенство f(n)=U(n,n) определяет:
- # Перечислимое множество с неперечислимым дополнением:
- # Проблема остановки состоит в выяснении того, что:
- # Непересекающиеся множества X и Y отделяются множеством Z, если:
- # Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:
- # Если d - вычислимая функция, E(d)={0,1} и не имеет всюду определенного вычислимого продолжения, то:
- # Если два множества неотделимы разрешимыми множествами, то:
- # Счетное число непересекающихся перечислимых множеств попарно неотделимых разрешимым множеством:
- # Бесконечное множество, не содержащее бесконечных разрешимых подмножеств является:
- # Перечислимое множество, для которого прямой пересчет его дополнения неограничен сверху вычислимой функцией является:
- # Нумерация множества X - это отображение:
- # Если V(m,x)=U(s(m),x), m, x - любые, то U называется:
- # Нумерация, соответствующая главной универсальной функции называется:
- # Главная универсальная функция:
-
#
Последовательность
![math]()
вычислима, если:
-
#
Последовательность
![math]()
вычислима, если существует:
-
#
Если нумерация является вычислимой, то последовательность
![math]()
- # Нумерация - вычислимая, если:
- # Универсальное перечислимое множество из N × N:
- # Различным операциям над множествами соответствуют:
- # Композиция двух вычислимых функций является:
- # Всякая универсальная функция для класса вычислимых одноместных функций задает:
- # Нумерация - вычислима, если вычислима:
- # Термину "k - местная" удовлетворяет функция:
- # Если функция f дает по номеру m функции другой номер s этой функции, то:
- # Вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов:
- # Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:
- # Определению главной универсальной функции адекватно утверждение:
- # Вычислимые универсальные функции, не являющиеся главными:
- # По любому номеру любого вычислимого действительного числа, номер вычислимой функции десятичного его разложения:
-
#
Для любого перечислимого множества X из декартового квадрата N существует вычислимая
![math]()
:
- # По программам функций f и g получить их композицию:
- # Для описания свойств вычислимых функций, из перечисленных ниже наиболее подходит язык:
- # Верны утверждения:
- # Если U - главная универсальная функция, а X - множество натуральных чисел n, где Un - нигде не определена, то Un:
- # Множество номеров нигде не определенной функции:
- # Если дополнение неразрешимого множества перечислимо, то само множество:
-
#
Если Y - класс вычислимых одноместных функций, а
![math]()
, то множество ![math]()
:
-
#
Функция
![math]()
, где K -перечислимое и неразрешимое, является:
- # Универсальную вычислимую функцию, для которой каждая вычислимая функция имеет ровно один номер:
- # В теореме Успенского - Райса утверждается, что в главной нумерации:
- # В теореме Роджерса утверждается, что трансляторы, сводящие главные нумерации друг к другу выбираемы:
- # Любые две нумерации перечислимых множеств:
- # Верно утверждение:
- # Верно утверждение:
- # Верно утверждение:
- # Для перечисляемых образцов и вычислимой универсальной функции, множество номеров всех функций, продолжающих хоть один образец:
- # Любое перечислимое свойство:
- # Образец - это:
- # Образцом является:
- # Образцом является:
- # Образцом является (n - натуральное, x - вещественное число):
- # Образцом не является (n - натуральное, x - вещественное число):
- # Образец является:
- # Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:
- # Если X - класс вычислимых одноместных функции, а Y - его подмножество, то верно утверждение:
- # Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
- # Если X - класс вычислимых одноместных функции, Y из X, Z - перечислимое неразрешимое множество, U - главная функция, то существует всюду определенная функция f со свойством:
- # Если U - главная вычислимая универсальная функция для класса вычислимых одноместных функций, то существует для произвольной вычислимой одноместной функции h:
- # Теорема Клини о неподвижной точке:
- # Программа, печатающая свой текст:
- # Если U(n,x) - главная вычислимая универсальная функция для класса всех вычислимых одноместных функций, то тогда:
- # Существует ли Паскаль-программа, инвертирующая свой текст?
- # Существуют ли Паскаль-программы А и В, печатающие, соответственно, тексты В и А?
- # Какая программа печатает свой текст?
- # Если программа на каждом входе зацикливается, то для неё:
- # Теорема о неподвижной точке называется также теоремой:
- # Теорема о неподвижной точке гарантирует существование:
- # Если преобразователь программ вычислимо зависит от некоторого параметра, то:
- # По любой вычислимой функции можно указать:
- # Два главных универсальных множества для класса перечислимых подмножеств N:
- # Множество А является I-соответствующей множеству В, если:
- # В языке Паскаль существует ряд программ Pi, i=1,2,…,n таких, что:
- # Структура на множестве X - это отношение типа:
- # Отношение эквивалентности - это отношение:
- # Отношение эквивалентности - это всегда отношение:
-
#
Если X=[-2;5], Y=[0;2], то
![math]()
будет:
-
#
Если X=[0;3], Y=[3;0], то
![math]()
будет:
- # Соответствие - это:
-
#
Отношение "
![math]()
" является:
-
#
Отношение "
![math]()
" является:
-
#
Отношение "
![math]()
" является:
- # Для доказательства неразрешимости множества X достаточно доказать, что:
-
#
Множество
![math]()
m-сводится к ![math]()
, если существует:
- # Для m-сводящей X к Y функции f используют обозначение:
-
#
Если
![math]()
и Y - разрешимо, то:
-
#
Если
![math]()
и Y - перечислимо, то:
-
#
Если
![math]()
и ![math]()
, то:
- # m-сводящей X к X будет функция:
- # Если f сводит Х к Y, g - Y к Z, то:
- # Если f сводит Х к Y, то она сводит:
- # Неверно для произвольных множеств:
- # Неверно для произвольных множеств:
- # Неверно для произвольных множеств:
- # Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:
- # m-полное множество относительно m-сводимости - это множество:
- # m-полнота - это отношение:
- # Если универсальное множество - главное, то его:
- # Множество всех самоприменимых программ:
- # Множество всех программ, останавливающихся хотя бы на одном входе является:
- # Множество X - эффективно бесконечное, если алгоритм конструирования по любому n различных элементов из X:
- # Множество X - эффективно неперечислимо, если существует всюду определенная вычислимая W-универсальная функция f:
-
#
Если
![math]()
и X - эффективно неперечислимо, то:
- # Для универсального перечислимого множества W-перечислимо множество:
- # Множества с эффективно неперечислимыми дополнениями:
- # Перечислимое множество m-полно тогда и только тогда, когда его дополнение:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
- # Частичная функция f вычислима относительно всюду определенной функции g тогда и только тогда, когда она:
- # Частичная функция вычислима относительно всюду определенной функции тогда и только тогда, когда она:
- # Образец - это функция из N в N, определенная:
- # Два образца - совместны, если:
- # Множество X - корректно, если:
- # Процедура замены вычислимых функции на функции, вычислимые относительно всюду определенной функции называется:
- # Множеством, перечислимым относительно всюду определенной вычислимой функции f является множество:
-
#
Множество X -
![math]()
-перечислимо тогда и только тогда, когда для некоторого перечислимого множества E:
-
#
Для
![math]()
- всюду определенной функции, ![math]()
-вычислимая функция двух аргументов являющаяся универсальной:
- # Множество - 0' - разрешимо, если оно:
- # Самая трудная в мире задача разрешения:
- # Любые два множества:
-
#
Множества X и Y, для которых
![math]()
и ![math]()
:
- # "Оракул" для множества X отвечает на вопрос:
- # "Оракул" для множества X может быть реализован вызовом внешней:
- # Фрагмент - это всегда:
- # Множество X согласовано с фрагментом x, если:
- # Несравнимые по Тьюрингу перечислимые множества:
- # Элемент - это:
-
#
Элемент
![math]()
продолжает элемент ![math]()
, если:
-
#
Указание - это кортеж
![math]()
, в котором:
-
#
Множество
![math]()
перечислимо тогда и только тогда, когда:
-
#
Свойство A(x),
![math]()
перечислимо тогда и только тогда, когда:
-
#
Если B(x,y) - некоторое разрешимое свойство, то свойства вида
![math]()
определяют свойства:
-
#
Свойство A принадлежит классу
![math]()
, если для некоторого разрешимого свойства В:
-
#
Свойство A принадлежит классу
![math]()
, если для некоторого разрешимого свойства В:
-
#
Отрицания свойств из класса
![math]()
:
-
#
Отрицания свойств из класса
![math]()
:
- # Каждая операция проектирования:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
-
#
Класс
![math]()
является:
-
#
Класс
![math]()
является:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
-
#
Если
![math]()
, то:
-
#
Классы
![math]()
и ![math]()
:
-
#
Для любого n в классе
![math]()
:
-
#
Свойства класса
![math]()
имеют вид:
-
#
Дополнение к универсальному множеству
![math]()
будет:
-
#
Универсальное
![math]()
множество:
-
#
Универсальное
![math]()
множество:
- # Класс эквивалентных множеств называют:
- # Машина Тьюринга включает объект:
- # Машина Тьюринга включает объект:
- # Машина Тьюринга включает объект:
- # Таблица переходов машины Тьюринга - функция:
- # Таблица переходов машины Тьюринга - функция:
- # Конфигурация машины Тьюринга в каждый момент времени складывается из:
- # Головка машины Тьюринга может передвигаться на:
- # Если входной алфавит машины Тьюринга состоит 0, 1 и пробела, то входным будет:
- # Тезис Тьюринга:
- # Ассоциативное исчисление - это:
- # В алфавите X слово P выводимо из слова Q, если:
-
#
Если
![math]()
, то это множество:
-
#
Если
![math]()
, то:
-
#
Инструкции "находясь в состоянии
![math]()
и читая символ ![math]()
перейти в состояние для всех ![math]()
, напечатать символ ![math]()
и сдвинуться влево" соответствует:
- # Инструкция "находясь в состоянии s и читая символ x, перейти в состояние p, напечатать символ y и сдвинуться вправо" порождает правило:
- # Ассоциативное исчисление - двустороннее, если оно содержит правила:
- # Двухстороннее исчисление, для правил которого нет алгоритма, выясняющегося, можно ли получить одно слово из другого:
- # Непустое множество с ассоциативной операцией типа умножения и единичным элементом называется:
- # Конкатенация - это операция:
- # Свободная полугруппа - это полугруппа:
- # Гомоморфизм полугрупп - это отображение:
- # Совокупность элементов X и определённых над ними операции F, удовлетворяющих аксиомам, называется:
- # Совокупность операций алгебры A называется:
- # Совокупность операндов алгебры A называется:
вычислима, если существует алгоритм A(f): 
можно найти такие числа a и b, что: 
: 
: 
называют: 
реализует рекурсия: 
реализует рекурсия: 
- универсальна для класса вычислимых функций одного аргумента, если для каждого n: 
вычислима, если: 
: 
, то множество 
: 
, где K -перечислимое и неразрешимое, является: 
будет: 
будет: 
" является: 
" является: 
" является: 
m-сводится к 
, если существует: 
и Y - разрешимо, то: 
, то: 
и X - эффективно неперечислимо, то: 
, то: 
, то: 
-перечислимо тогда и только тогда, когда для некоторого перечислимого множества E: 
и 
: 
продолжает элемент 
, если: 
, в котором: 
перечислимо тогда и только тогда, когда: 
определяют свойства: 
, то: 
, то: 
, то: 
, то: 
, то: 
имеют вид: 
, то это множество: 
и читая символ 
перейти в состояние для всех 
, напечатать символ 
и сдвинуться влево" соответствует: