(1) Доказать, что конечное множество разрешимо. (2) Где используется конечность?

Тут так рассуждать?

Насколько я понимаю, надо придумать алгоритм, который будет принимать х и говорить, принадлежит ли х нашему множеству. Но поскольку множество конечно, можно этот алгоритм определить так, что он будет принимать х и перебирать все элементы конечного множества, сверяя их с х. Если совпадений нет, то он выдаст "нет", а если есть, то "да". Если бы множество было бесконечным, то при принятии элемента х не из нашего множества он бы за конечное время не выдал ответ "нет".

задан 21 Окт '19 8:27

@logic: разумеется, так и есть -- алгоритм сверяет число x на входе с конечным списком. Само по себе утверждение тривиально. Разве что для конкретных языков могло требоваться формальное доказательство.

(21 Окт '19 9:43) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×7

задан
21 Окт '19 8:27

показан
218 раз

обновлен
21 Окт '19 9:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru