Автомат, однократно считывающий входную строку слева направо, называется
В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений
В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо
В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s недоказуемо; 2) Øs доказуемо - из перечисленного
В системе Пеано единственным неопределимым отношением является
Внутреннее состояние машины Тьюринга обозначается
Внутренним алфавитом машины Тьюринга называется
Временные или пространственные характеристики процесса вычисления называются
Всякая вычислимая функция является вычислимой по Тьюрингу согласно
Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции
Входной алфавит определяется как
Входят в алфавит формального логического языка символы
Выражение является
Выражением называется
Геделевский номер, равный 23, имеет функция
Геделевский номер, равный , имеет функция
Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым
Если , то функция в рекуррентной формуле равна
Если , то функция в рекуррентной формуле равна
Если и рекурсия проводится по переменной , то функция равна
Если и рекурсия проводится по переменной , то функция равна
Если и рекурсия проводится по переменной , то функция равна
Если и рекурсия проводится по переменной , то функция равна
Если и рекурсия проводится по переменной , то функция равна
Если и рекурсия проводится по переменной , то функция равна
Если и рекурсия проводится по , то функция равна
Если и рекурсия проводится по , то функция равна
Если , то функция в рекуррентной формуле равна
Если и рекурсия проводится по , то функция равна
Если и рекурсия проводится по , то функция равна
Если и рекурсия проводится по , то функция равна
Если и рекурсия проводится по , то функция равна
Если , то функция (n,m) в рекуррентной формуле равна
Если A и B - рекурсивные множества, то рекурсивны также множества I. II. III.
Если A рекурсивно, а B - рекурсивно перечислимо, то _____ рекурсивно
Если множество не является множеством значений никакой функции, то оно
Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции
Идея использования рекурсии для решения задач, связанных с основаниями математики, предложена
Имена и предложения называются фразами
Каждая п.р.ф имеет число номеров
Класс примитивно рекурсивных функций
Команда машины Тьюринга состоит из элементарных действий
Композиция и равна
Конечное множество команд, имеющих попарно различные начальные пары символов, называется
Конечному автомату соответствует грамматика, порождающая
Лента машины Тьюринга
Любая непротиворечивая система арифметики с рекурсивной системой аксиом
Любая неразрешимая алгоритмическая проблема дает пример множества
Марковский алгоритм - это алгоритм
Машина Тьюринга есть совокупность компонент
Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции
Множество аксиом вместе с явным определением доказательства составляют
Множество всевозможных осмысленных утверждений языка является
Множество всех истинных утверждений языка L является
Множество доказуемых утверждений формальной системы арифметики
Множество истинных утверждений
Множество натуральных чисел является
Множество номеров несамоприменимых машин Тьюринга
Множество номеров самоприменимых машин Тьюринга
Множество простых чисел является
Множество составных чисел является
Множество, если его характеристический предикат является вычислимым, называется
Множество, если оно является множеством значений некоторой вычислимой функции, называется
Не сохраняет примитивную рекурсивность оператор
Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно
Осмысленные конечные последовательности символов из алфавита L называются
Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру
Полнота - это условие, что для любого утверждения s одно из утверждений s и Øs
Пусть R - рекурсивность, а P - рекурсивная перечислимость. Тогда
Символы, которые машина Тьюринга читает и пишет на ленте, образуют
Система Пеано содержит аксиом
Способ видения объектов формальных систем как конкретных объектов при условии, что содержательные объекты сохраняют структуру формальных, называется
Средство для соединения фраз для преобразования других фраз называется
Существует команд машины Тьюринга
Существуют три основных класса фраз: имена, предложения и
Теорема Геделя о неполноте арифметики поколебала оптимистические надежды Гильберта на полное решение вопросов оснований математики с помощью
Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой
Теория алгоритмов является частью
Усеченная разность равна
Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется
Утверждение формально записывается как
Утверждение формально записывается как
Утверждение арифметики Пеано называется неразрешенным, если оно
Формализованный язык для однозначной записи алгоритмов называется
Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой
Фразы, соединяемые функтором, называются
Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной
Функция имеет Гёделевский номер, равный
Функция имеет гёделевский номер, равный
Функция является
Функция вычисляется по формуле
Функция имеет гёделевский номер, равный
Функция равна
Функция имеет гёделевский номер, равный
Функция называется частично рекурсивной, если она либо принадлежит к числу исходных п.р.ф., либо может быть получена из них с помощью операторов
Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки - из перечисленного
Функция, вычислимая по Тьюрингу, является
Функция, вычисляемая некоторой машиной Тьюринга с входным и выходным алфавитами, называется
Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется
Функция, полученная из вычислимой с помощью рекурсии, является
Функция, равная единице тогда и только тогда, когда предикат истинен, называется
Частично вычислимая функция
Челночный алгоритм является алгоритмом
Язык, на котором описывается другой язык, называется
w-непротиворечивая формальная система является