Вычислимые и невычислимые функции
Тест разработан в качестве цифрового домашнего задания по теме "Алгоритмически неразрешимые задачи. Вычислимые и невычислимые функции"
Задание 1
В информатике существуют алгоритмически неразрешимые задачи. Соотнесите пример задачи с проблемой неразрешимости задачи.
Задание 2
Выберите из предложенных характеристик те, которые относятся к вычислимым функциям.
Задание 3
Представлено число, записанное в единичной системе счисления (в виде цепочки единиц). Требуется определить, является ли данное число четным или нечетным. Является ли данная задача алгоритмически разрешимой?
Задание 4
Предложена задача: написать программу для машины Тьюринга (алгоритм), которая по тексту любой программы Р и ее входным данным Х определяет, завершается ли программа Р при входе Х за конечное число шагов или зацикливается. Является ли эта задача алгоритмически разрешимой или алгоритмически неразрешимой?
Задание 5
Международный математический конгресс в Париже, на котором известный математик Давид Гильберт сформулировал 23 неразрешённые математические проблемы, состоялся в ... году.
Задание 6
Соотнесите термины с определениями.
Задание 7
Сформулируйте знаменитую "десятую проблему Гильберта". Требуется найти , который позволяет определить, имеет ли решение числах.
Задание 8
Ученикам предложили написать нормальный алгоритм (алгорифм) Маркова [НАМ] для задачи, заменяющей во входном двоичном слове все нули на буквы "а" и все единицы на буквы "б". Андрей предложил вот такой вариант решения этой задачи: 0 => а 1 => б Предложите другой вариант решения поставленной задачи. Заполните пустые места в записи НАМ. => =>
Задание 9
Представлено число, записанное в единичной системе счисления (в виде цепочки единиц). Определить, является ли данное число четным или нечетным. Запишите нормальный алгоритм (алгорифм) Маркова для решения данной задачи. => => =>
Задание 10
В 1970 году советскому математику удалось доказать, что не существует общего алгоритма решения задачи нахождения универсального метода, который позволяет определить, имеет ли заданное алгебраическое уравнение с целыми коэффициентами решение в целых числах. Запишите фамилию советского математика.