Билет №2
1. Тезисы Тьюринга и Черча. Статус этих тезисов и взаимосвязь между ними.
2. Теорема Райса-Успенского: формулировка и смысл теоремы.
3. Является ли разрешимой проблема остановки произвольной
машины Тьюринга, если она стартует на ленте, на которой записано
слово 1101001?
4.3. Критерии оценивания к экзамену
Оценка «отлично»: точные формулировки алгоритмов, теорем и правильные
доказательства; точные определения математических объектов и ясные и
правильные определения объектов, характеризующихся неформализованными
понятиями.
Оценка «хорошо»: при ответе на один вопрос даны точные
формулировки алгоритмов, теорем и правильные доказательства; точные
определения математических объектов и ясные
и правильные определения
объектов,
характеризующихся неформализованными понятиями; при ответе на второй вопрос имеются неточности
формулировки алгоритмов, теорем или пробелы в правильных
доказательствах; недостаточно точные определения математических
объектов или неясные и не совсем правильные определения объектов,
характеризующихся неформализованными понятиями. Оценка
«удовлетворительно»: при ответе на оба вопроса имеются неточности
формулировки алгоритмов, теорем или пробелы в правильных
доказательствах; недостаточно точные определения математических
объектов или неясные и не совсем правильные определения объектов,
характеризующихся неформализованными понятиями. Оценка
«неудовлетворительно»: отсутствует ответ хотя бы на один из вопросов или
имеются существенные неточности в формулировках алгоритмов, теорем,
приведены неправильные
доказательства;
неверные определения
математических
объектов
и неправильные
определения
объектов,
характеризующихся неформализованными
понятиями.
Достарыңызбен бөлісу: