2004-gre-cs-practice-book.pdf/Q61

Ссылки сюда (2) →

Вопрос: Q61-4c9f66

Какие из следующих задач являются разрешимыми?

1. Для конечной строки w, является ли w префиксом десятичного представления числа π?
2. При наличии программы и входных данных, является ли вывод программы десятичным представления числа π?
3. Для заданной программы, которая принимает в качестве входных данных префикс десятичного представления числа π, выяснить — всегда ли выходные данные программы одинаковы для каждого префикса?

Ответы

• Правильный ответ: Только 1
• Только 2
• Только 3
• 1 и 2
• 1, 2, 3

Объяснение

Исходники — вопрос 61 на 40 странице книги «2004-gre-cs-practice-book.pdf»

• 1 — генерим число пи до длины w, сверяем — возвращаем 0/1
• 2 — вообще неразрешимо, хотя перечислимо.
• 3 — также, как 1, неразрешимо, хотя и перечислимо.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.