Докажем сабж .
1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи
2) программ на C++ — счётное число
3) таким образом множество вещественных чисел счётно

Найдите баг в доказательстве.

Здравствуйте, Olegator, Вы писали:

O>Докажем сабж .
O>1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи

Проблема в том, что нельзя задать такое соотвествие. Например, какая программа будет соответствовать вещественному числу, n-ая цифра которого равна 1, если программа с номером n останавливается, и 0, если она зацикливается?
Или какая программа будет соответствовать вещественному числу, n-ая цифра которого равна 1, если высказывание с номером n в некоторой формальной теории, включающей арифметику, является теоремой этой теории, и 0 в противном случае?

Olegator wrote:

> 1) каждому вещественному числу поставим в соответствие программу на C++,
> вычисляющую его n-ю цифру в десятичной записи
Угу, тут косяк.
Можно почитать о [не]конструктивных вещественных числах.
http://www.synset.com/steps/gedel/gedel.html

Здравствуйте, Olegator, Вы писали:

O>Докажем сабж .
O>1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи

Сперва надо доказать эту лемму.

Здравствуйте, Olegator, Вы писали:

O>Докажем сабж .
O>1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи
O>2) программ на C++ — счётное число
O>3) таким образом множество вещественных чисел счётно

O>Найдите баг в доказательстве.

Баг во втором пункте. Почему программ — счетное число? Это еще нужно доказать.

Здравствуйте, rpaskomid, Вы писали:

R>Баг во втором пункте. Почему программ — счетное число? Это еще нужно доказать.

Это-то как раз справедливо. Множество программ — это подмножество конечных строк на конечном алфавите. А множество конечных строк — счётно.

Здравствуйте, Olegator, Вы писали:

O>Докажем сабж .
O>1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи
Напиши на С++ программу, вычисляющую знаки константы Хайтина

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, rpaskomid, Вы писали:

R>>Баг во втором пункте. Почему программ — счетное число? Это еще нужно доказать.

К>Это-то как раз справедливо. Множество программ — это подмножество конечных строк на конечном алфавите. А множество конечных строк — счётно.

Условие задачи не оговаривает уникальность множества программ.

Здравствуйте, Olegator, Вы писали:
O>1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи
Осталось доказать, что такое соответствие существует.

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, Olegator, Вы писали:
O>>1) каждому вещественному числу поставим в соответствие программу на C++, вычисляющую его n-ю цифру в десятичной записи
MC>Осталось доказать, что такое соответствие существует.

Можно поставить в соответствие программу, выводящую надмножество из десяти цифр, среди которых будет и искомое. Тогда кстати понадобится не так уж и много программ =).

Для популяризации идеи можно пойти ещё дальше, и поставить в соответствие каждому вещественному числу, скажем, свою зажигалку. После чего заявить аудитории что существует лишь одно вещественное число, и что оно заключено именно в вашей зажигалке. Зауважают сразу =).

Здравствуйте, rpaskomid, Вы писали:

R>>>Баг во втором пункте. Почему программ — счетное число? Это еще нужно доказать.
К>>Это-то как раз справедливо. Множество программ — это подмножество конечных строк на конечном алфавите. А множество конечных строк — счётно.
R>Условие задачи не оговаривает уникальность множества программ.

Ну и что? Каждая программа (множество которых счётно) за время своей бесконечной работы способна вывести счётное же количество чисел.
алеф0 * алеф0 = алеф0.

Даже если мы каждый экземпляр программы запустим счётное количество раз (с разными параметрами), снова получим алеф0^3 = алеф0.
А количество параметров счётно, потому что
— Конечные строки — их количество счётно.
— Бесконечные строки — руками мы породить не можем, значит, их порождают другие программы, инициализированные вручную. А про них мы уже знаем, что у них на выходе счётное количество строк. Итого опять счётность.

Здравствуйте, Кодт, Вы писали:

К>Ну и что? Каждая программа (множество которых счётно) за время своей бесконечной работы способна вывести счётное же количество чисел.
К>алеф0 * алеф0 = алеф0.
"Aleph-null bottles of beer on the wall, Aleph-null bottles of beer, Take one down, and pass it around, Aleph-null bottles of beer on the wall" (c) народное.