Для всех тех, у кого несчётность R вызывает сомнения

[infoliokrat]

Ales в сообщении #279306 писал(а):

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

Возможно в школе достаточно натуральными числами считать ровно столько чисел, сколько получится, если взять существующие размеры видимой (мыслимой) расширяющейся Вселенной, разделить на понятную дробную часть наименьшей элементарной частицы с учетом найхудшего соотношения неопределенности, умножить на число всех жителей Земли за время работоспособности Солнца и умножить на число-факториал от количества нейронов самого тяжелого известного мозга (математика), вот и появится перспектива нынешней арифметики жизни. (Надеюсь факториал устроит самых придирчивых, ведь он для натурального "больше", чем 2 в степени натуральное). Вот и получится главное конечное натуральное... (Не раз встречал на форумах, какое натуральное самое большое).

Так что очень верным представляется решение, что по поводу счётности континуума "голосовать" пока рановато.

Что касается потерь от потери несчётности, то не скажете ли что за (какую) мощность по нынешним понятиям можно сосчитать, если кодировать дробные части номерами, получающимися от обратной записи всех значащих цифр (хоть в десятиричной, хоть в двоичной, а лучше- в единичной системе счисления). Число цифр дробной части любого периодического или иррационального числа считается счётным. И для каждого числа однозначно найдется свой сосед и слева и справа.
А влруг тогда прояснятся приобретения?
Ну а по поводу алгоритма машины Тьюринга естественно прибалдел маленько, когда попав в школу увидел, что его изучают в начальной школе!!!. ( Могу уточнить, в каком году это было, кажется в программе 2-го класса) З павагай ко всем, кто не заставляет это в начальной школе изучать.

[vek88]

AlexDem в сообщении #279347 писал(а):

vek88 в сообщении #279328 писал(а):

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

Где Вы видели программиста за машиной Тьюринга? А все конечные (и ограниченные) задачи мы решим

Программиста за машиной Тьюринга я не видел. И нигде не говорил об этом.

А Вам как программисту назову реальный в программировании пример, где важно знать об алгоритмической неразрешимости проблемы. Надеюсь, Вы слышали про язык программирования Пролог? Так вот, в строгом смысле невозможно написать интерпретатор для этого языка, даже для простейшего случая - Пролога без отрицания.

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

Замечу, что речь идет о вполне конечной и ограниченной задаче!

[AlexDem]

vek88 в сообщении #279386 писал(а):

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

Зачем так сложно? Я могу написать программу, которая циклится на любых входных данных. А вообще - если множества входных $A$ и выходных $B$ данных ограничены, то все возможные программы представимы функциями из $A$ в $B$, все они очевидно реализуемы в случае ограниченности.

[Xaositect]

Ну, в те времена, когда появилась теория вычислений, не было понятно, какие задачи решаются, а какие нет.
А с "очевидной" реализацией функции из конечного $A$ в конечное $B$ тоже есть проблема - это очевидная реализация не влезет в вашу память. Сложность алгоритмов сейчас активная область, и некоторые, если не сказать многие, основные приемы и конструкции взяты из теории вычислений.

[Ales]

infoliokrat в сообщении #279372 писал(а):

Возможно в школе достаточно

Я думаю, что вообще этим не надо сильно грузиться. А чисел всегда достаточно. Было бы что считать.

-- Вс янв 10, 2010 22:30:18 --

Xaositect в сообщении #279392 писал(а):

Ну, в те времена, когда появилась теория вычислений, не было понятно, какие задачи решаются, а какие нет.
А с "очевидной" реализацией функции из конечного $A$ в конечное $B$ тоже есть проблема - это очевидная реализация не влезет в вашу память. Сложность алгоритмов сейчас активная область, и некоторые, если не сказать многие, основные приемы и конструкции взяты из теории вычислений.

Сейчас тоже не все еще ясно.

-- Вс янв 10, 2010 22:34:56 --

AlexDem в сообщении #279391 писал(а):

vek88 в сообщении #279386 писал(а):

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

Зачем так сложно? Я могу написать программу, которая циклится на любых входных данных. А вообще - если множества входных $A$ и выходных $B$ данных ограничены, то все возможные программы представимы функциями из $A$ в $B$, все они очевидно реализуемы в случае ограниченности.

Я несколько раз писал такие программы.

[vek88]

AlexDem в сообщении #279391 писал(а):

vek88 в сообщении #279386 писал(а):

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

Зачем так сложно? Я могу написать программу, которая циклится на любых входных данных. А вообще - если множества входных $A$ и выходных $B$ данных ограничены, то все возможные программы представимы функциями из $A$ в $B$, все они очевидно реализуемы в случае ограниченности.

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

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

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

А беда в том, что любой написанный Вами интерпретатор на каком-то запросе к этой программе сглючит - не даст правильного ответа! Вы доработаете Ваш интерпретатор, но найдется новый глюк. И так до бесконечности. Вас, как программиста, это устраивает?

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

[AlexDem]

vek88 в сообщении #279400 писал(а):

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

Если мне запретят использовать часть из возможных функций, ограничив Прологом, то конечно не смогу. Хотя, даже если там реализуемы все они, то:

vek88 в сообщении #279400 писал(а):

Вы доработаете Ваш интерпретатор, но найдется новый глюк. И так до бесконечности.

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

[Ales]

vek88 в сообщении #279400 писал(а):

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

А есть ли конкретные примеры? И зачем нужен этот Пролог?

[Maslov]

vek88 в сообщении #279400 писал(а):

А беда в том, что любой написанный Вами интерпретатор на каком-то запросе к этой программе сглючит - не даст правильного ответа!

А нельзя немного подробнее? Это какой-то глубокий теоретический результат или просто следствие правила "каждая программа содержит по крайней мере одну ошибку"?

[Xaositect]

Ales писал(а):

Xaositect в сообщении #279392 писал(а):

Ну, в те времена, когда появилась теория вычислений, не было понятно, какие задачи решаются, а какие нет.
А с "очевидной" реализацией функции из конечного $A$ в конечное $B$ тоже есть проблема - это очевидная реализация не влезет в вашу память. Сложность алгоритмов сейчас активная область, и некоторые, если не сказать многие, основные приемы и конструкции взяты из теории вычислений.

Сейчас тоже не все еще ясно.

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

-- Вс янв 10, 2010 23:18:30 --

Я, кстати, тоже вспомнил достаточно интересную неразршимую задачу. Дана контекстно-зависимая грамматика, необходимо проверить принимаемый ей язык на пустоту. Иными словами, есть набор правил вида "если заглавная буква $\Gamma$ стоит в строке между словами $\alpha$ и $\beta$ (из маленьких букв), то его можно заменить на слово $\gamma$ (из маленьких и больших букв)", определить, можно ли из некоторого начального символа $S$ получить хотя бы одно слово, целиком состоящее из маленьких букв.
Интересно, как Вы будете строить эту свою конечную таблицу.

[vek88]

AlexDem в сообщении #279405 писал(а):

vek88 в сообщении #279400 писал(а):

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

Если мне запретят использовать часть из возможных функций, ограничив Прологом, то конечно не смогу. Хотя, даже если там реализуемы все они, то:

vek88 в сообщении #279400 писал(а):

Вы доработаете Ваш интерпретатор, но найдется новый глюк. И так до бесконечности.

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

Мы немного запутались, видимо, слишком торопимся. Уточняю.

1. Правильная и ограниченная задача, четко сформулированная - это программа на языке Пролог (сейчас точно не помню, примерно 50 или 100 строк, т.е. по программистким меркам совсем маленькая). Эта Пролог-программа представляет собой вполне понятное и очевидное логическое описание рассматриваемой задачи. Уверяю Вас, что, посмотрев на эту Пролог-программу, Вы все согласитесь, что она понятно и четко описывает логику задачи. И четко определяет какой ответ надо давать на любой запрос к этой Пролог-программе.

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

3. И представьте себе ужас Вашего положения - вам тычут ... глюк.

4. Вы его устраняете, а Вам ... новый глюк.

За подробностями отсылаю к литературе. Например, см. старую книгу "Представление в ЭВМ неформальных процедур" (дайте поиск в Яндексе).

P.S. Я оказался в положении Д'Артаньяна. Поэтому приношу извинения остальным участникам за то, что не могу сразу ответить всем - буду делать это постепенно.

[Ales]

Xaositect в сообщении #279409 писал(а):

Не ясно, какие задачи решаются, а какие нет?

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

[Xaositect]

Ales в сообщении #279416 писал(а):

Xaositect в сообщении #279409 писал(а):

Не ясно, какие задачи решаются, а какие нет?

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

А, Вы про сложность. В теории сложности, да, есть сложности Но область молодая, так что надежда есть на то, что рано или поздно вопросы разрешатся.

[Ales]

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

[Xaositect]

Ales в сообщении #279422 писал(а):

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

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

-- Пн янв 11, 2010 00:00:40 --

Вообще, у нас тут давно оффтоп пошел по разным направлениям, что в принципе неудивительно, поскольку у всех участники дискуссии, кроме м.б. infoliokrat'а, несчетность $\mathbb{R}$ в классической математике сомнений, видимо, не вызывает.