Мышление, вычисления и искусственный интеллект для школьников

Упражнение 1:

Номер 1

Решением проблемы остановки будет являться:

Ответ:

(1) создание программы, оценивающей возможность корректной остановки любой программы на основании анализа ее кода и входных данных

(2) создание программы, останавливающей другие программы

(3) остановка программы, обладающей искусственным интеллектом

Номер 2

Доказательство возможности создания программы, решающей проблему остановки...

Ответ:

(1) существует

(2) не существует, поскольку это неверное утверждение

(3) не требуется, , поскольку это утверждение является аксиомой

Номер 3

Доказательство невозможности создания программы, решающей проблему остановки...

Ответ:

(1) существует

(2) не существует, поскольку это неверное утверждение

(3) не требуется, , поскольку это утверждение является аксиомой

Упражнение 2:

Номер 1

Вычислимые языки - это языки, для которых существуют программы (алгоритмы), ...

Ответ:

(1) определяющие принадлежность к данному языку каждого слова этого языка и всегда завершающиеся при любых других входных словах

(2) определяющие принадлежность к данному языку каждого слова этого языка и не всегда завершающиеся при любых других входных словах

(3) позволяющие вывести в произвольном порядке все слова этого языка

Номер 2

Язык, для которого существует программа, определяющая принадлежность к данному языку каждого слова этого языка и всегда завершающаяся при других входных словах ...

Ответ:

(1) называется полувычислимым

(2) называется вычислимым

(3) называется перечислимым

Номер 3

Как "ведет" себя программа для любого вычислимого языка?

Ответ:

(1) не всегда завершается

(2) всегда завершается

(3) выводит все слова этого языка

Упражнение 3:

Номер 1

Полувычислимые языки - это языки, для которых существуют программы (алгоритмы), ...

Ответ:

(1) определяющие принадлежность к данному языку каждого слова этого языка и всегда завершающиеся при любых других входных словах

(2) определяющие принадлежность к данному языку каждого слова этого языка и не всегда завершающиеся при любых других входных словах

(3) позволяющие вывести в произвольном порядке все слова этого языка

Номер 2

Язык, для которого существует программа, определяющая принадлежность к данному языку каждого слова этого языка и не всегда завершающаяся при других входных словах ...

Ответ:

(1) называется вычислимым

(2) называется полувычислимым

(3) называется перечислимым

Номер 3

Как "ведет" себя программа для любого полувычислимого языка?

Ответ:

(1) всегда завершается

(2) выводит все слова этого языка

(3) не всегда завершается

Упражнение 4:

Номер 1

Перечислимые языки - это языки, для которых существуют программы (алгоритмы), ...

Ответ:

(1) позволяющие вывести в произвольном порядке все слова этого языка

(2) определяющие принадлежность к данному языку каждого слова этого языка и всегда завершающиеся при любых других входных словах

(3) определяющие принадлежность к данному языку каждого слова этого языка и не всегда завершающиеся при любых других входных словах

Номер 2

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

Ответ:

(1) называется перечислимым

(2) называется вычислимым

(3) называется полувычислимым

Номер 3

Как "ведет" себя программа для любого перечислимого языка?

Ответ:

(1) выводит все слова этого языка

(2) всегда завершается

(3) не всегда завершается

Упражнение 5:

Номер 1

Любой вычислимый язык является ...

Ответ:

(1) перечислимым

(2) невычислимым

(3) полувычислимым

Номер 2

Любой полувычислимый язык является ...

Ответ:

(1) невычислимым

(2) перечислимым

(3) вычислимым

Номер 3

Любой перечислимый язык является ...

Ответ:

(1) полувычислимым

(2) вычислимым

(3) невычислимым

Упражнение 6:

Номер 1

Укажите правильное утверждение?

Ответ:

(1) слова состоят из цифр, алфавит состоит из слов

(2) слова состоят из символов, алфавит состоит из слов

(3) слова состоят из символов, язык состоит из слов

Номер 2

Что такое алфавит?

Ответ:

(1) совокупность, набор символов из которых состоят слова языка

(2) совокупность символов в строке

(3) совокупность слов в языке

Номер 3

Что называется алфавитом некоторого языка?

Ответ:

(1) совокупность части символов, используемых в словах(строках) данного языка

(2) совокупность всех символов, используемых в словах(строках) данного языка

(3) совокупность всех символов, неиспользуемых в словах(строках) данного языка

Упражнение 7:

Номер 1

Доказательство того, что множество всех возможных языков - счетное, ...

Ответ:

(1) существует

(2) не существует, поскольку это неверное утверждение

(3) не требуется, поскольку это утверждение является аксиомой

Номер 2

Выберите правильное утверждение?

Ответ:

(1) число возможных языков равно числу возможных программ

(2) число возможных языков больше числа возможных программ

(3) число возможных языков меньше числа возможных программ

Номер 3

Доказательство того, что множество всех возможных языков - больше, чем счетное, ...

Ответ:

(1) существует

(2) не существует, поскольку это неверное утверждение

(3) не требуется, поскольку это утверждение является аксиомой

Упражнение 8:

Номер 1

Что предполагается при доказательстве нерешения программы остановки?

Ответ:

(1) программа, решающая проблему остановки, работает с пустым входом

(2) программа, решающая проблему остановки, существует

(3) программа, решающая проблему остановки, не существует

Номер 2

Предполагается ли при доказательстве нерешения проблемы остановки о существовании такой программы?

Ответ:

(1) да

(2) нет

Номер 3

Что дается на вход программе, предположительно решающей проблему остановки?

Ответ:

(1) только выходные данные проверяемой программы

(2) только входные данные проверяемой программы

(3) входные данные и код проверяемой программы

Упражнение 9:

Номер 1

Какой вывод делается в конце доказательства нерешения программы остановки?

Ответ:

(1) программа, решающая проблему остановки, не существует

(2) программа, решающая проблему остановки, существует

(3) существование такой программы недоказуемо в рамках данной формальной задачи

Номер 2

Что подается на вход исследуемой программе на последнем этапе доказательства нерешения проблемы остановки?

Ответ:

(1) код произвольной программы

(2) пустой вход

(3) собственный код

Номер 3

Какое противоречие возникает при окончании доказательства нерешения проблемы остановки?

Ответ:

(1) взаимоисключающая одновременность завершения и незавершения программы

(2) "Словесный парадокс"

(3) противоречие теории множеств

Упражнение 10:

Номер 1

Выберите отличие вычислимого от полувычислимого языка:

Ответ:

(1) программа вычислимого языка не всегда завершается

(2) программа вычислимого языка всегда завершается

(3) программа вычислимого языка выводит все слова своего языка

Номер 2

Выберите отличие вычислимого от невычислимого языка:

Ответ:

(1) программа вычислимого языка не завершается

(2) программа вычислимого языка не всегда завершается

(3) для любого вычислимого языка существует программа, идентифицирующая все слова этого языка

Номер 3

Выберите отличие перечислимого от вычислимого языка:

Ответ:

(1) программа перечислимого языка выводит все слова своего языка

(2) программа перечислимого языка не выводит все слова своего языка

(3) программа перечислимого языка всегда завершается

Упражнение 11:

Номер 1

Выберите отличия перечислимого от полувычислимого языка:

Ответ:

(1) программа перечислимого языка не завершается

(2) программа перечислимого языка не всегда завершается

(3) программа перечислимого языка не выводит все слова своего языка

Номер 2

Выберите отличие невычислимого от перечислимого языка:

Ответ:

(1) для невычислимого языка существует программа, идентифицирующая все слова этого языка

(2) для невычислимого языка не существует программы, идентифицирующей все слова этого языка

(3) программа невычислимого языка всегда завершается

Номер 3

Выберите отличие невычислимого от полувычислимого языка:

Ответ:

(1) для невычислимого языка не существует программы, идентифицирующей все слова этого языка

(2) для невычислимого языка существует программа, идентифицирующая все слова этого языка

(3) программа невычислимого языка не всегда завершается

Упражнение 12:

Номер 1

Если программа не всегда завершается при входных словах, не являющихся словами ее языка, то такой язык называется ...

Ответ:

(1) вычислимым

(2) полувычислимым

(3) перечислимым

Номер 2

Если программа всегда завершается при входных словах, не являющихся словами ее языка, то такой язык называется ...

Ответ:

(1) полувычислимым

(2) перечислимым

(3) вычислимым

Номер 3

Если программа выводит все слова своего языка, то такой язык называется ...

Ответ:

(1) перечислимым

(2) вычислимым

(3) невычислимым

Мышление, вычисления и искусственный интеллект для школьников - тест 2