Здравствуйте, Дарней, Вы писали:
Д>Теоретически, только теоретически. На практике для проверки может потребоваться время, сопоставимое с временем жизни Вселенной.
Ничего страшного на данном уровне достаточно отличать конечное время от бесконечного. К тому же может потребоваться и потребуется — несколько разные вещи.
На практике для достижения достаточно больших времен нужно специально затачивать алгоритмы. Типичные примеры зацикливания легко детектируются за более чем конечные времена.

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

S>На практике для достижения достаточно больших времен нужно специально затачивать алгоритмы. Типичные примеры зацикливания легко детектируются за более чем конечные времена.

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

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

AVC>>Не вполне понял.
AVC>>Вы утверждаете, что некто вычислил 10^100 простых чисел с помощью МТ?

Q>Некто мог бы вычислить, это легко доказать математически.

После Евклида, доказавшего бесконечность множества простых чисел, и после Эратосфена, предложившего первый алгоритм, это, ИМХО, больше не нуждается в доказательстве.
Я просил Вас привести примеры решенных с помощью МТ задач и вычисленных с помощью МТ результатов.
А Вы говорите, что "можно доказать, что некто мог бы вычислить".
Но это разные вещи.

AVC>>Во-вторых, не вполне ясно, почему мы должны считать память ЭВМ ограниченной.
AVC>>Например, можно использовать дополнительную, внешнюю, виртуальную память и т.д., добавляя память по мере необходимости.
AVC>>Если память ЭВМ ограничена принципиально, то пусть кто-нибудь укажет, каков предел.

Q>Например, количество атомов во вселенной.

Т.е. для МТ количество атомов во Вселенной — не предел?

AVC>>У меня сложилось впечатление, что Вы говорите о теоретическом использовании МТ, а Перлис — о "практическом", т.е. именно для вычислений.
AVC>>Т.е. вы говорите о разных вещах.

Q>А кто-нибудь когда-нибудь применял МТ для реальных задач?

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

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

ИМХО, аналогия хромает.
МТ — всего лишь одна из множества примерно равноценных моделей, созданных для исследования понятия алгоритма.
ИМХО, Computer science вполне могла бы существовать и без нее.

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

AVC>>У меня сложилось впечатление, что Вы говорите о теоретическом использовании МТ, а Перлис — о "практическом", т.е. именно для вычислений.

LCR>"Нет ничего практичнее хорошей теории"

LCR>A compendium of NP optimization problems
LCR>Complexity Zoo

LCR>Вот примерно за этим нужна МТ.

Я и не спорю — теория нужна.
Я только предлагаю немного напрячь воображение и представить: а что было бы, если бы у нас была только МТ, а архитектуры фон Цузе — не было.
По моему, именно об этом и говорил Перлис.

Что же касается собственно МТ, то я и не отрицаю, что у меня есть пробел в знаниях на сей счет.
Потребуется изрядно времени (которого, увы, не хватает ), чтобы его заполнить.
Действительно ли МТ так необходима для оценки сложности алгоритма?
И каков на сегодня статус соответствующих разделов теории алгоритмов?
Вот первый попавшийся отрывок из Википедии:
http://ru.wikipedia.org/wiki/Теория_алгоритмов

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

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

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

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

S>Нет, не видел. Но делал eternal loop detector для простого скриптового языка .

и как, надежно он работал? Учитывая вложенные циклы, объектное состояние, вызовы чужих методов, рекурсии и тому подобное?

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

E>>Как ты можешь предположить сочетание "удачные" и "правильные" на практике будет встречаться не так часто, как хотелось бы. Естественно, что у читающих и пишущих в этом форуме такие совпадения будут происходить в 101.9% случаев, как же иначе .

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

Ты хочешь сказать, что уровень сложности написания библиотеки классов -- это уровень, который кого-то останавливает?

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

E>>Сам же жаловался, как хреново с C++ дела обстоят. А ведь C++ умный человек делал, о C++ много книг написано, о нем многое известно. И все равно...

Д>Проблемы С++ имеют совсем другие корни, не надо путать длинное с острым.

У C++ очень большое количество проблем связано с тем, что язык практически всегда оставался совместим со своими предшественниками. Когда некую задачу начнут решать DSL-ями, проблема совместимости версий DSL станет столь же остро, как проблема совместимости в C++. И никаими автоматизированными рефакторингами она не будет преодолеваться (как бы некоторые горячие головы здесь не верили в возможности рефакторинга).

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

E>Да. Во-первых, ты пытаешься определить совершенство логикой. Ты еще красоту линейкой измерь.

Какую это "красоту" ты собрался измерять линейкой?

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

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

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

E>У C++ очень большое количество проблем связано с тем, что язык практически всегда оставался совместим со своими предшественниками.

И никто даже не озаботился тем, чтобы оставить возможность избавляться от хлама в языке. Старые фичи слишком плотно интегрировали непосредственно в язык, и теперь так просто от них не избавишься.

E>Когда некую задачу начнут решать DSL-ями, проблема совместимости версий DSL станет столь же остро, как проблема совместимости в C++. И никаими автоматизированными рефакторингами она не будет преодолеваться (как бы некоторые горячие головы здесь не верили в возможности рефакторинга).

Рефакторинг здесь и не нужен. Нужен всего лишь конвертор из старого формата в новый. Который реализуется без особых проблем, ибо DSL — это далеко не полноценный ЯП по сложности своего синтаксиса; и тем более не С++, язык, который стал притчей во языцех из-за своего безумно переусложненного синтаксиса.

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

AVC>Я и не спорю — теория нужна.
AVC>Я только предлагаю немного напрячь воображение и представить: а что было бы, если бы у нас была только МТ, а архитектуры фон Цузе — не было.
AVC>По моему, именно об этом и говорил Перлис.

Глупость какая. Никто не оборачивался на МТ, когда делал компьютер. Компьютер — это инженерная, в основном, задача, зачем его сравнивать с МТ я не знаю.

AVC>Действительно ли МТ так необходима для оценки сложности алгоритма?
AVC>И каков на сегодня статус соответствующих разделов теории алгоритмов?
AVC>Вот первый попавшийся отрывок из Википедии:
AVC>http://ru.wikipedia.org/wiki/Теория_алгоритмов
AVC>

AVC>Поскольку класс P содержится в классе NP, принадлежность той или иной задачи к классу NP зачастую отражает наше текущее представление о способах решения данной задачи и носит неокончательный характер. В общем случае нет оснований полагать, что для той или иной NP-задачи не может быть найдено P-решение. Вопрос о возможной эквивалентности классов P и NP (то есть о возможности нахождения P-решения для любой NP-задачи) считается многими одним из основных вопросов современной теории сложности алгоритмов. Ответ на этот вопрос не найден до сих пор.

Что значит необходима? Можно формулировать тоже самое и в других терминах, но зачем? Для МТ формулировка выглядит вполне естественно — как зависит время выполнения алгоритма от размера задачи на входе.
Если докажешь, что NP=P, тебе памятник при жизни поставят.

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

Д>и как, надежно он работал? Учитывая вложенные циклы, объектное состояние, вызовы чужих методов, рекурсии и тому подобное?
100%. Но язык был значительно проще, чем ты описываешь. Там не было объектного состояния и вызова чужих методов. Рекурсии тоже не было. Вся фишка была в том, что очень легко строился вектор состояния для обработчика события; далее, путем запуска двух копий скрипта с разной скоростью проверялось совпадение векторов.
Прикол в том, что фактический объем модифицируемого состояния в большинстве циклов крайне невелик. Для настоящего языка с косвенной адресацией все значительно сложнее, хоть и небезнадежно

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

S>100%. Но язык был значительно проще, чем ты описываешь. Там не было объектного состояния и вызова чужих методов. Рекурсии тоже не было. Вся фишка была в том, что очень легко строился вектор состояния для обработчика события; далее, путем запуска двух копий скрипта с разной скоростью проверялось совпадение векторов.

Не совсем понял.. а как отыгрывались разные комбинации входных данных?

S>Прикол в том, что фактический объем модифицируемого состояния в большинстве циклов крайне невелик. Для настоящего языка с косвенной адресацией все значительно сложнее, хоть и небезнадежно

надеюсь... статические проверки рулят однозначно

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

L>Какую это "красоту" ты собрался измерять линейкой?

тогда уж не линейкой, а рулеткой! А то какой-то нестандартной ориентацией попахивает

Здравствуйте, Дарней, Вы писали:
Д>Не совсем понял.. а как отыгрывались разные комбинации входных данных?
Каких входных данных? У нас не стояла задача узнать, существуют ли в принципе входные данные, способные зациклить скрипт. Стояла значительно более реалистичная задача: отловить зациклившийся скрипт и пристрелить его. Именно это и делалось.

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

S>Каких входных данных? У нас не стояла задача узнать, существуют ли в принципе входные данные, способные зациклить скрипт. Стояла значительно более реалистичная задача: отловить зациклившийся скрипт и пристрелить его. Именно это и делалось.

In computability theory the halting problem is a decision problem which can be informally stated as follows:
Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible inputs cannot exist. We say that the halting problem is undecidable over Turing machines. ([1] with respect to attribution of "halting problem" to Turing.)

То, о чем ты говоришь — это совсем не та задача.
И снова получился анекдот про Иванова, который "Волгу" выиграл....

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

Д>In computability theory the halting problem is a decision problem which can be informally stated as follows:
Д>Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.
А?
Д>Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible inputs cannot exist. We say that the halting problem is undecidable over Turing machines. ([1] with respect to attribution of "halting problem" to Turing.)

Д>То, о чем ты говоришь — это совсем не та задача.
Точно? Мне просто казалось, что Тьюринг говорил именно про неразрешимость для произвольного ввода. Т.е. он имел в виду, что решение для некоторых наборов входных данных может и существовать, но нельзя гарантировать отсутствия входного набора, для которого проблема останова неразрешима.
Д>И снова получился анекдот про Иванова, который "Волгу" выиграл....
Может быть.

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

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

MFC?
Некоторые контейнерные классы из JDK 1.0?
AWT из JDK?
std::basic_string?

E>>У C++ очень большое количество проблем связано с тем, что язык практически всегда оставался совместим со своими предшественниками.

Д>И никто даже не озаботился тем, чтобы оставить возможность избавляться от хлама в языке. Старые фичи слишком плотно интегрировали непосредственно в язык, и теперь так просто от них не избавишься.

А какой язык приспособлен к тому, что бы из него изымали старые фичи и при этом сохраняли совместимость с написанным ранее кодом? Какой из распространенных ныне языков пережил существенное изменение с потерей совместимости (будучи уже раскрученным и имеющим солидную кодовую базу) и при этом выжил?

E>>Когда некую задачу начнут решать DSL-ями, проблема совместимости версий DSL станет столь же остро, как проблема совместимости в C++. И никаими автоматизированными рефакторингами она не будет преодолеваться (как бы некоторые горячие головы здесь не верили в возможности рефакторинга).

Д>Рефакторинг здесь и не нужен. Нужен всего лишь конвертор из старого формата в новый. Который реализуется без особых проблем, ибо DSL — это далеко не полноценный ЯП по сложности своего синтаксиса; и тем более не С++, язык, который стал притчей во языцех из-за своего безумно переусложненного синтаксиса.

Почему у тебя неявно сковозит, что DSL -- это просто? DSL может быть сложен как по синтаксису, так и по семантике.

В качестве примера. Представь себе, что в программе на Nemerle использовалась библиотека Oyster-а для работы с физическими величинами. Программа разрослась до нескольких миллионов строк кода, в активной разработке находятся сразу несколько версий для разных заказчиков. И тут оказалось, что требуется перейти на другую подобную библиотеку от более именитого производителя. Насколько просто будет произвести автоматическое преобразование существующего кода?

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

S>Точно? Мне просто казалось, что Тьюринг говорил именно про неразрешимость для произвольного ввода. Т.е. он имел в виду, что решение для некоторых наборов входных данных может и существовать, но нельзя гарантировать отсутствия входного набора, для которого проблема останова неразрешима.

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

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

E>MFC?
E>Некоторые контейнерные классы из JDK 1.0?
E>AWT из JDK?
E>std::basic_string?

И что, кто-то заставлял использовать эти средства насильно? Ходил по офисам и палкой бил по головам ослушников? Плохой выбор — это проблема выбирающего. Если выбора нет и библиотека откровенно плоха — напиши свою и обогатись. Если нет времени на это — пиши прогу с учетом замены в будущем. Пишите с использованием языка, а не думайте на нем. И так далее.

E>А какой язык приспособлен к тому, что бы из него изымали старые фичи и при этом сохраняли совместимость с написанным ранее кодом?

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

E>Какой из распространенных ныне языков пережил существенное изменение с потерей совместимости (будучи уже раскрученным и имеющим солидную кодовую базу) и при этом выжил?

бейсик? Не буду приводить его в качестве примера хорошего языка, конечно. Но его живучесть просто потрясает, он прошел очень большой путь от того чуда с номерами строк 10,20,30 до VB.NET, который стал практически нормальным языком
Что еще важнее, язык развивается и занимает новые ниши. В отличие от С++, который ожидает прямо противоположная участь.

E>Почему у тебя неявно сковозит, что DSL -- это просто? DSL может быть сложен как по синтаксису, так и по семантике.

Потому что это будет уже не DSL

E>В качестве примера. Представь себе, что в программе на Nemerle использовалась библиотека Oyster-а для работы с физическими величинами. Программа разрослась до нескольких миллионов строк кода, в активной разработке находятся сразу несколько версий для разных заказчиков. И тут оказалось, что требуется перейти на другую подобную библиотеку от более именитого производителя. Насколько просто будет произвести автоматическое преобразование существующего кода?

Я не знаю, каков синтаксис ни у той, ни у другой И, кстати говоря, не верю что все миллионы строк кода состоят именно из DSL, который написал Oyster
Давай ты приведешь конкретный пример проблемы, которую нельзя решить относительно несложным автоматическим конвертором, а я попробую ее решить?

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

AVK>Не наезда ради, но кардинально.

Координально, координально. Из жалких тырканий дело перешло в научный подход.