Все вопросы к тесту (html) Математическая логика и теория алгоритмов



w-непротиворечивая формальная система является

Автомат, однократно считывающий входную строку слева направо, называется

В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s недоказуемо; 2) Øs доказуемо - из перечисленного

В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо

В системе Пеано единственным неопределимым отношением является

Внутреннее состояние машины Тьюринга обозначается

Внутренним алфавитом машины Тьюринга называется

Временные или пространственные характеристики процесса вычисления называются

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

Всякое непустое ___ множество является ___ некоторой всюду определенной вычислимой функции

Входной алфавит определяется как

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

Выражением называется

Геделевский номер, равный 23, имеет функция

Дополнение к области определения некоторой вычислимой функции ___ рекурсивно перечислимым

Если A рекурсивно, а B - рекурсивно перечислимо, то ___ рекурсивно

Если множество не является множеством значений никакой функции, то оно

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

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

Если множество рекурсивно, то оно является ___ всюду определенной вычислимой функции

Идея использования рекурсии для решения задач, связанных с основаниями математики, предложена

Имена и предложения называются фразами

Каждая п.р.ф имеет число номеров

Класс примитивно рекурсивных функций

Команда машины Тьюринга состоит из элементарных действий

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

Конечному автомату соответствует грамматика, порождающая

Лента машины Тьюринга

Любая непротиворечивая система арифметики с рекурсивной системой аксиом

Любая неразрешимая алгоритмическая проблема дает пример множества

Марковский алгоритм - это алгоритм

Машина Тьюринга есть совокупность компонент

Множество ___ тогда и только тогда, когда оно является ___ некоторой вычислимой функции

Множество аксиом вместе с явным определением доказательства составляют

Множество всевозможных осмысленных утверждений языка является

Множество всех истинных утверждений языка L является

Множество доказуемых утверждений формальной системы арифметики

Множество истинных утверждений

Множество натуральных чисел является

Множество номеров несамоприменимых машин Тьюринга

Множество номеров самоприменимых машин Тьюринга

Множество простых чисел является

Множество составных чисел является

Множество, если его характеристический предикат является вычислимым, называется

Множество, если оно является множеством значений некоторой вычислимой функции, называется

Не сохраняет примитивную рекурсивность оператор

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

Осмысленные конечные последовательности символов из алфавита L называются

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

Полнота - это условие, что для любого утверждения s одно из утверждений s и Øs

Пусть R - рекурсивность, а P - рекурсивная перечислимость. Тогда

Символы, которые машина Тьюринга читает и пишет на ленте, образуют

Система Пеано содержит аксиом

Способ видения объектов формальных систем как конкретных объектов при условии, что содержательные объекты сохраняют структуру формальных, называется

Средство для соединения фраз для преобразования других фраз называется

Существует команд машины Тьюринга

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

Теорема Геделя о неполноте арифметики поколебала оптимистические надежды Гильберта на полное решение вопросов оснований математики с помощью

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

Теория алгоритмов является частью

Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется

Утверждение арифметики Пеано называется неразрешенным, если оно

Формализованный язык для однозначной записи алгоритмов называется

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

Фразы, соединяемые функтором, называются

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

Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки - из перечисленного

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

Функция, вычисляемая некоторой машиной Тьюринга с входным и выходным алфавитами, называется

Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется

Функция, полученная из вычислимой с помощью рекурсии, является

Функция, равная единице тогда и только тогда, когда предикат истинен, называется

Частично вычислимая функция

Челночный алгоритм является алгоритмом

Язык, на котором описывается другой язык, называется