Можно ли найти последовательность с помощью ДА/НЕТ?

[macdonalds]

Для простоты будем оперировать с множеством всех натуральных чисел и целочисленными последовательностями. Очевидно, туда входит бесконечно много подмножеств, содержащих последовательности.
Например, загадаем любую последовательность, которую возьмем с энциклопедии OEIS. Пусть это будет A005097 (абсолютно наугад выбрал). Это:
1, 2, 3, 5, 6, 8 , 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36, 39, 41, 44, 48, 50, ....
Нам это известно, другому человеку неизвестно ничего, в том числе и числа входящие в его ряд.

Можно ли найти эту последовательность, задавая вопросы на которые возможен только ответ ДА/НЕТ? Если можно, какие вопросы, и какой алгоритм должен быть? Если невозможно, то почему?

[Mihr]

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

[mihaild]

Если разрешены только последовательности из OEIS - то очевидно можно: "это A000001?", "это A000002?", ..., "это A342859?".
Если разрешены произвольные последовательности - то за конечное число вопросов очевидно нельзя. За бесконечное - нужно уточнять протокол.

[macdonalds]

Цитата:

верно ли, что загадана последовательность A005097?

Нет, нет. Такой вопрос некорректный, просто оттуда удобно брать последовательности. Тем более, их бесконечно много, легко можно придумать свою.

-- 26.03.2021, 14:03 --

mihaild в сообщении #1511312 писал(а):

Если разрешены только последовательности из OEIS - то очевидно можно: "это A000001?", "это A000002?", ..., "это A342859?".
Если разрешены произвольные последовательности - то за конечное число вопросов очевидно нельзя. За бесконечное - нужно уточнять протокол.

Последовательности произвольные. Но, я не уверен, что за конечное число вопросов нельзя найти ее. Самое главное - нужен алгоритм и правильные вопросы.

[Mihr]

macdonalds в сообщении #1511317 писал(а):

Такой вопрос некорректный

Почему? Объясните, что Вы понимаете под "корректным" вопросом. Иначе говоря, вопросы какого типа разрешены.

-- 26.03.2021, 15:08 --

Объясните также, чего Вы ждёте от алгоритма: чтобы он гарантированно нашёл последовательность, или случайное её обнаружение тоже приветствуется?

[mihaild]

macdonalds в сообщении #1511317 писал(а):

Но, я не уверен, что за конечное число вопросов нельзя найти ее.

Пусть мы задаем произвольное, но всегда конечное число вопросов. Сколько вариантов ответов мы можем получить? А сколько последовательностей существует?

[macdonalds]

Mihr в сообщении #1511319 писал(а):

Объясните также, чего Вы ждёте от алгоритма: чтобы он гарантированно нашёл последовательность, или случайное её обнаружение тоже приветствуется?

Именно гарантированно.

Допустим, для последовательности выше можно легко сузить рамки, с помощь нескольких вопросов:
Содержит ли п-ь только нечетные числа?
Содержит ли п-ь только четные числа?
Содержит ли п-ь простые числа?
П-ь начинается с единицы?
В этой п-и однозначных чисел от 5 до 10?
В этой п-и двузначных чисел от 20 до 50?
и т.д.

[Mihr]

macdonalds в сообщении #1511323 писал(а):

Именно гарантированно.

Тогда попробуйте ответить на вопросы mihaild.

[macdonalds]

mihaild в сообщении #1511320 писал(а):

Пусть мы задаем произвольное, но всегда конечное число вопросов. Сколько вариантов ответов мы можем получить? А сколько последовательностей существует?

Предполагается, что последовательность, как бы это выразится, человечная что ли. В дебри бесконечностей и гуголов забредать не будем. Именно поэтому я и взял последовательность с OEIS.

-- 26.03.2021, 14:35 --

Давайте, если так проще: возьмем произвольную последовательность с сайта OEIS, можно ли ее найти с помощью логики, не задавая вопросов это A000001?", "это A000002?", ..., "это A342859?

[Aritaborian]

macdonalds в сообщении #1511327 писал(а):

В дебри бесконечностей и гуголов забредать не будем. Именно поэтому я и взял последовательность с OEIS.

Ну так там большинство последовательностей как раз бесконечные.

[macdonalds]

Aritaborian в сообщении #1511329 писал(а):

Ну так там большинство последовательностей как раз бесконечные.

Это разумеется. Но формулы их не бесконечные. Нет там дурацких формул вроде a(n) = 2n^43-n!, которую найти будет крайне трудно, там в основном короткие и компактные.

[Mihr]

Если последовательность выбирается из фиксированного конечного множества последовательностей, то, разумеется, её можно выделить, используя конечное число вопросов. Зная объём этого множества последовательностей, легко оценить достаточное число вопросов.

-- 26.03.2021, 15:48 --

macdonalds в сообщении #1511330 писал(а):

Нет там дурацких формул вроде a(n) = 2n^43-n!

Формулы дурацкими не бывают. Вам всё-таки стоило бы уточнить, какие вопросы Вы считаете разрешёнными. Пока Вы на этот вопрос не ответили.

[mihaild]

Ну если последовательность хотя бы арифметическая (вроде бы все последовательности с OEIS такие) - то, очевидно, можно. "Пусть $x$ - лексикографически наименьшая из самых коротких формул в алафвите [выбрать какой-нибудь хороший алфавит], задающих нашу последовательность. Верно ли, что $|x| < 1$? что $|x| < 2$? ...? [установили длину] Верно ли, что первый символ $x$ такой-то? ...".

macdonalds в сообщении #1511330 писал(а):

Нет там дурацких формул вроде $a(n) = 2n^{43}-n!$

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

[wrest]

macdonalds в сообщении #1511317 писал(а):

Последовательности произвольные. Но, я не уверен, что за конечное число вопросов нельзя найти ее. Самое главное - нужен алгоритм и правильные вопросы.

Вы знаете, это немного напоминает изобретателей вечных двигателей, которым всегда не хатает хорошей смазки и инструментов выточить ровную втулку :)

[macdonalds]

Mihr в сообщении #1511332 писал(а):

Если последовательность выбирается из фиксированного конечного множества последовательностей, то, разумеется, её можно выделить, используя конечное число вопросов. Зная объём этого множества последовательностей, легко оценить достаточное число вопросов.

Ок, ок, я понял свою ошибку.

Mihr в сообщении #1511332 писал(а):

какие вопросы Вы считаете разрешёнными

Любые вопросы, на которые можно ответить ДА/НЕТ и которые определяют свойства членов, входящих в ряд этой целочисленной последовательности. Например, про четные/нечетные,/простые/фибоначи/и т.д. Наводящий вопрос, является ли это A005097, запрещен, потому что он сразу определяет конкретный ряд, а не его члены.