Критерий счётного множества

[fractalon]

Верно ли, что если возможно написать программу, которая за конечное количество шагов может вывести на экран любой элемент некоторого бесконечного множества A, то A - счётно?

[gris]

Такой программы быть не может. Экран компьютера может отобразить только конечное число различных образов. Это если понимать под конечными шагами построение образа и однократный вывод его на экран.
Если Вы понимаете под отображением конечное число вывода на экран, например, последовательный показ цифр номера объекта, то да. Любое счётное множество можно отобразить, хотя бы отображая номера элементов в некоторой нумерации. А несчётное так отобразить не удасться.

[fractalon]

Да, предполагается, что программа может работать сколько требуется времени и отображать сколько требуется чисел.
Так вот. Суть вопроса даже не в этом. Это мне понятно было сразу, я просто сомневался.
Вопрос в том, счётно ли множество Кантора?
Потому что для его вывода на компьютер программу составить можно и очень просто.

[nikvic]

fractalon в сообщении #761700 писал(а):

Верно ли, что если возможно написать программу, которая за конечное количество шагов может вывести на экран любой элемент некоторого бесконечного множества A, то A - счётно?

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

[Oleg Zubelevich]

fractalon в сообщении #761737 писал(а):

опрос в том, счётно ли множество Кантора?

континуально

[gris]

Множество Кантора несчётно, и я не представляю, как можно вывести на экран компьютера какое-либо иррациональное число, ему принадлежащее. Описание числа не считается (в детском смысле слова. Да и с помощью описаний можно вывести только счётное число чисел).

[fractalon]

А разве к нему принадлежат иррациональные числа? Я просто пытаюсь понять - не доказываю.

Вот такая, например, программа какое число из множества Кантора никогда не выведет?

#include <iostream>
#include <conio.h>

int main()
{
   int i,j;
   int N=2;
   int a[1000];
   long long three=3;
   a[0]=1;
   a[1]=2;
   while (1)
   {
      for (i=0;i<N;i++)
      {
         printf("%d/%d ",a[i],three);
         a[2*N-1-i]=three*3-a[i];
      }
      printf("\n");
      N*=2;
      three*=3;
   }
}

На всякий случай привожу пример вывода первых чисел:

1/3 2/3
1/9 2/9 7/9 8/9
1/27 2/27 7/27 8/27 19/27 20/27 25/27 26/27
1/81 2/81...

[gris]

Конечно, принадлежат. Например: $(0.20020002000020000020000002...)$ в троичной записи. Вот его Ваша программа и не выведет.

[fractalon]

Но ведь программа его в конце-концов когда-нибудь выведет.
Если не ошибаюсь, при делении рационального числа на 3 в ответе будет рациональное? А других операций кроме деления на три при формировании множества Кантора не происходит.

[gris]

Не выведет, увы. Оно не имеет представления в форме дроби. Вы, наверное, имеете в виду построение Канторова множества в виде аттрактора, то есть замыкания некоторого опорного счётного множества. Но переход к пределу не является арифметической операцией.

[fractalon]

Ясно. Спасибо за объяснения.

[Deggial]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

fractalon, формулы набирайте $\TeX$ом, а для оформления код используйте тег code. Код выше я оформил.