Несколько уровней бесконечности

Некоторые программисты не видят значительной значимости в теоретических классах CS (особенно мои ученики). Вот что я считаю очень актуальным. Позвольте мне собрать его на куски для тех, кто не видел его раньше...

A) Проблемы программирования могут быть переформулированы как вопросы о языках.

B) Машины Turing распознают языки.

C) Машины Turing могут быть закодированы как (большие) целые числа.

D) Поэтому число возможных машин Тьюринга счетно бесконечно

E) Набор мощности набора - это всего лишь все возможные подмножества этого множества.

F) Если множество счетно бесконечно, его множество мощности больше, т.е. несчетно бесконечно.

G) Поэтому, если язык бесконечен, он имеет бесчисленное множество подмножеств. Каждая из них представляет проблему. Но есть только множество машин Тьюринга, с помощью которых можно решить эти проблемы. И если мы не сможем решить проблему с машиной Тьюринга, она не может быть решена.

Заключение... мы можем разрешить бесконечно малую долю всех проблем.

Мой вопрос почти здесь...

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

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

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

Final Edit: Я многому научился, задав этот вопрос, и я ценю отзывы. Я потратил слишком много времени, пытаясь выяснить, что такое "Вики-сообщество" на самом деле. Я узнал, что у некоторых людей есть неотъемлемая предвзятость в отношении вопросов теории, которые, как я чувствую, являются просто ошибкой, потому что так много того, что мы делаем сегодня, было теорией вчера. Но это смещение естественное, и, хотя я не согласен с ними в отношении теории, у меня нет проблем с этим, и это помогает мне понять, откуда идут мои ученики. Я действительно думаю, что комментарий BS не нужен.

Я не считаю, что этот вопрос вообще был опросом или вопросом об исключениях для 2009 года. Те из вас, кто хочет только кодировать вопросы с ответами на кодирование, могут захотеть пересмотреть это требование. Я переместил этот вопрос на wiki сообщества, но сильно чувствую, что я был вынужден сделать это ненадлежащим применением силы.

Ответ 1

Я думаю, что ваше объяснение является самым простым, так я узнал. Это почти так, как если бы реальные числа имели множество измерений бесконечности. Он бесконечен в одном направлении, но и в другом.

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

Я думаю, что принцип "Кардинальность континуума" также полезен, хотя, возможно, может быть упрощен до уровня новичка. Показывая, что существует нечто большее, чем простые реальные целые числа, потенциально может помочь чему-то 'click'.

Ответ 2

Мой рекомендуемый первый шаг для обучения уровням бесконечности людям с ограниченным математическим фоном: "Почему математики говорят, что набор четных чисел и набор целых чисел одного размера?" Это вводит "если вы можете связать каждый элемент множества A с одним членом множества B, математики говорят, что множества имеют одинаковый размер". Далее следует, что каждая фракция (каждое рациональное число) может быть связана с одним номером счета, используя диагональный метод. Как только они доволен этим, я поднимаю & pi;, который, как известно, имеет бесконечное количество неповторяющихся цифр в десятичном выражении, что означает, что он не может быть выражен как дробь, поэтому он будет оставлен, и это означает, что множество иррациональных чисел больше, чем множество счетных чисел. Некоторые wiseguys возражают, что & pi; имеет конечное число цифр, если вы работаете в base & pi;, а именно 1 _{& pi;}, но вы можете вернуться к ним с помощью "okay, brainiac", записать количество дней в неделю в базе & pi;. "

Ответ 3

Где "очень важная" часть?

Изменить: Хорошо, я профессионально пишу код в течение 13 лет, и я бы не назвал уровни бесконечности, относящиеся ко всему, что я когда-либо работал.

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

Звучит для меня как есть бесконечное (счетное или несчетное, похоже, не имеет значения) количество проблем. Поэтому наше ремесло не ограничено - мы не сможем решить проблемы.

Ответ 4

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

Ответ 5

Простите плохо написанные метафоры ниже.

Я лично считаю, что дихотомия счетности/несчетности очень тесно связана с парадоксом Зено в стреле.

Множество всех натуральных чисел счетно, существует конкретный метод генерации "следующего" целого числа, и он даст вам шаг вперед. В этом смысле счетные множества являются движущимися вперёд. Он почти как если бы он имел скорость ,, он продолжает двигаться вперед.

Множество всех действительных чисел несчетно, например zeno arrow.

Если вам нужно переместиться между началом (0) и пунктом назначения (1 == 2 ^-0), вы должны сначала пройти через середину (1/2 == 2 ^-1).

Теперь ваш пункт назначения равен 1/2; Если вы должны пройти между началом (0) и (1/2), вы должны пройти через середину (1/4 == 2 ^-2)

Итак, и т.д., поэтому, чтобы добраться между 0 и 1, вы должны сначала получить между чем-то между ними, которые вы должны сначала получить между чем-то между ними. Нет конечного метода вычисления "следующего" шага, поэтому скорость (в отличие от скорости натуральных чисел) на самом деле не существует, ваш следующий шаг не приведет вас никуда.

Edit:

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

Ответ 6

G) Поэтому, если язык бесконечен, он имеет бесчисленное множество подмножеств. Каждый из них представляет проблему.

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

Ответ 7

Программисты (или, по крайней мере, я) не часто беспокоятся о бесконечности таким образом. Когда вы помещаете конечную коробку над любой частью машинной представляемой строки реального номера, вы получаете конечное количество действительных чисел. =)

Например, double precision variable имеет конечное число возможных значений: 2 ^ 64.

Ответ 8

Вот пример вычислимой проблемы: в начале шахматной игры можно ли белому заставить выиграть?

Число возможных ходов и встречных движений конечно. Все, что нам нужно сделать, это построить деревья и обрезать их. Мы еще этого не сделали, только потому, что с нынешней технологией потребуется миллиарды лет.

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

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

Мы не вычислить невычислимые. Мы производим приблизительный результат (точно так же, как мы вычисляем и используем приблизительное значение pi, другое неоспоримое число). Мы продолжаем обновлять результат, когда поступает больше информации. Что это за оптические иллюзии. Когда вы смотрите на картину "ваза, или это два лица?" ваша визуальная система говорит: "Это ваза. Нет. Подождите, это два лица. Нет. Подождите, это ваза". Вы видите, что это переключение между двумя интерпретациями.

Просто потому, что что-то не вычислимо, нет причин не делать этого.

Ответ 9

Заключение... мы можем разрешить бесконечно малую долю всех проблем.

Вы должны быть веб-дизайнером.