Вычислимые и невычислимые функции

Тест разработан в качестве цифрового домашнего задания по теме "Алгоритмически неразрешимые задачи. Вычислимые и невычислимые функции"

Задание 1

В информатике существуют алгоритмически неразрешимые задачи. Соотнесите пример задачи с проблемой неразрешимости задачи.

Задание 2

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

Задание 3

Представлено число, записанное в единичной системе счисления (в виде цепочки единиц). Требуется определить, является ли данное число четным или нечетным. Является ли данная задача алгоритмически разрешимой?

Задание 4

Предложена задача: написать программу для машины Тьюринга (алгоритм), которая по тексту любой программы Р и ее входным данным Х определяет, завершается ли программа Р при входе Х за конечное число шагов или зацикливается. Является ли эта задача алгоритмически разрешимой или алгоритмически неразрешимой?

Задание 5

Международный математический конгресс в Париже, на котором известный математик Давид Гильберт сформулировал 23 неразрешённые математические проблемы, состоялся в ... году.

Задание 6

Соотнесите термины с определениями.

Задание 7

Сформулируйте знаменитую "десятую проблему Гильберта". Требуется найти , который позволяет определить, имеет ли решение числах.

Задание 8

Ученикам предложили написать нормальный алгоритм (алгорифм) Маркова [НАМ] для задачи, заменяющей во входном двоичном слове все нули на буквы "а" и все единицы на буквы "б". Андрей предложил вот такой вариант решения этой задачи: 0 => а 1 => б Предложите другой вариант решения поставленной задачи. Заполните пустые места в записи НАМ. => =>

Задание 9

Представлено число, записанное в единичной системе счисления (в виде цепочки единиц). Определить, является ли данное число четным или нечетным. Запишите нормальный алгоритм (алгорифм) Маркова для решения данной задачи. => => =>

Задание 10

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