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

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

B>>Разве это не связанные вещи?
B>>Самоприменимость и возможность написать программу, которая устанавливала бы возможность остановки другой программы.
B>>Собственно достаточно иметь доказанной теорему о самоприменимости, чтобы сделать вывод
B>>о невозможности такой программы.
B>>Или я не прав?

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

DG>зы
DG>теорема только говорит, что нельзя написать программу, которая по любой программе сообщает заканчивается та или нет.
DG>но она не говорит, что нельзя написать программу, которая будет определять конечность для 5%, 50%, 75% или 99% задач

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

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

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

А зачем тебе общее решение? Тебе разве недостаточно программы, которая для любой твоей реальной задачи в 99% случаев смогла бы определить конечная программа или нет?

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

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

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

DG>А зачем тебе общее решение? Тебе разве недостаточно программы, которая для любой твоей реальной задачи в 99% случаев смогла бы определить конечная программа или нет?

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

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

B>Но пока что названное тобой число 99% — это ведь тоже из разряда мечты.
B>Ты можешь назвать класс программ, про которые можно было бы утверждать нечто похожее?

1. Программы без циклов
2. Программы с детерминированными циклами (for i = 0; i < 10; ++i) или (while (Read()) do)

для выделения более сложных классов надо много думать.

B>И можно ли ограничится этим классом на практике?

надо много думать.

зы
На самом деле проблема в этой области одна — это никому не надо.

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

DG>зы
DG>На самом деле проблема в этой области одна — это никому не надо.

Отнюдь. Просто проблема очень и очень тяжела и с наскоку не решается.

PS
Программисты — это самые оптимистичные люди, с которыми мне приходится сталкиваться

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

DG>А зачем тебе общее решение? Тебе разве недостаточно программы, которая для любой твоей реальной задачи в 99% случаев смогла бы определить конечная программа или нет?

Все даже проще. Отбираем проги, которые:
1) Имеют ограниченный набор входных данных.
2) останавливаются за N шагов на любых входных данных (нафиг нам слишком долгие проги?).

А вот эта задача алгоритмически разрешима.

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

B>Программисты — это самые оптимистичные люди, с которыми мне приходится сталкиваться

Вспоминается: "Я знаю, что задача неразрешима, но вы мне скажите как ее решать".

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

DG>Вспоминается: "Я знаю, что задача неразрешима, но вы мне скажите как ее решать".

Это Стругацкие.

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

KO>Приведи, очень интересно.

Немного переформулированное доказательство:

Пусть существует программа А, которая умеет определять, заависнет та или иная программа, поданная на ее вход.
В случае, если программа зависает, печатается 0, а в случае, если нет — 1
Нетрудно имея такую программу, создать программу B, которая вместо того, чтобы печатать 1, виснет.
Т.е, программа B виснет, если на ее входе — нормальная программа и не виснет, если программа "неверная"
Применим программу B саму к себе.
1. Пусть программа B — правильная, значит виснуть она не должна. В резульате получим N, что говорит о том, что B виснет
2. Пусть программа B — неверная, значит на выходе мы должны поулучить N, т.е., программа B не виснет, значит она верна
Противоречие доказывает теорему.

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

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

C>Здравствуйте, King Oleg, Вы писали:

KO>>Приведи, очень интересно.

C>Немного переформулированное доказательство:

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

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

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

C>>Здравствуйте, King Oleg, Вы писали:

KO>>>Приведи, очень интересно.

C>>Немного переформулированное доказательство:

C>А вообще, пробема самоприменимости формулировалась как создание программы, которая определяла бы, виснет или нет программа, если ей на вход подать ее саму. Абстрактного понятия "виснет" в теореме не было

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

> Пусть существует программа А, которая умеет определять,
> заависнет та или иная программа, поданная на ее вход.
> В случае, если программа зависает, печатается 0,
> а в случае, если нет — 1
> Нетрудно имея такую программу, создать программу B,
> которая вместо того, чтобы печатать 1, виснет.
> Т.е, программа B виснет, если на ее входе — нормальная
> программа и не виснет, если программа "неверная"
> Применим программу B саму к себе.
> 1. Пусть программа B — правильная, значит виснуть она не должна.
> В резульате получим N, что говорит о том, что B виснет
> 2. Пусть программа B — неверная, значит на выходе мы должны
> поулучить N, т.е., программа B не виснет, значит она верна
> Противоречие доказывает теорему.

Это противоречие не доказывает утверждение вверху

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

Предположим существование программы A, на входе
которой другая программа, на выходе 1 если
программа на входе завершиться за конечное
число шагов, 0 в противном случае.

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


дело не в том что
> Нетрудно имея такую программу, создать программу B,
> которая вместо того, чтобы печатать 1, виснет.
(изменить так чтобы висла)
а вот что
невозможно убедиться для жидкости "элексир бессмертия",
что это действительно "элексир бессмертия" за конечное
время


--
"человек правильно говорящий, и правильно мыслит" (с) Я

остается маленький вопрос, как для нагенеренных
программ определить, что они делают, какой вопрос решают ?

используя пример о генерерации картинок и убийце Листьева,
как мы узнаем что, именно эта картинка и есть картинка
убийцы Листьева ? (кроме прочего там ведь и твое лицо будет

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

только лажа это, почему-то такой подход у меня ассоциируется
с америкосами, психологами и шаманами.

обобщить можно словами "когда законы управляющие явлениями
не известены, тычемся во все места, а вдруг повезет"
я считаю, заниматься подобными вещами — вычеркнуть свое время

--
[comrade]Serjio

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

S>обобщить можно словами "когда законы управляющие явлениями
S>не известены, тычемся во все места, а вдруг повезет"
S>я считаю, заниматься подобными вещами — вычеркнуть свое время

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

Но к исходному сообщению это конечно же не имеет никакого отношения.

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

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

я стараюсь обратить внимание собеседника,
чем он занимается

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

S>"человек правильно говорящий, и правильно мыслит" (с) Я

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

Если принять во внимание эти уточнения, доказательство устраивает?

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

Автор: ch00k
Дата: 04.09.03

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

TR>Привет все.
TR>Такой вопрос — что все мы, программисты, делаем в конечном итоге?
TR>Первый вариант ответа — создаем файлы (исполняемые). Но ведь любой файл — это набор символов. Вот и первая идея — написать маленькую прогу, которая будет плодить перебором файлы фиксироывнной длины со всевозможным перебором символов. Поставим фильтр на выходе этой проги на форматы исполняемых файлов. После этого еще один фильтр — на непадение сразу после запуска. Получаются ВСЕ программы искомого размера. То есть если на входе этого генератора программ поставим 2 байта — то будет 255*255 переборов. Согласен, для нормальной проги переборов будет много, но ведь на то она и машина, чтобы однотипные действия выполнять.
TR>Второй вариант ответа — создаем определенную последовательность действий процессора. По сути идея та же. Но будем перебирать не все символы подряд, а опкоды процессора, ну и со всякими там заголовками и прочими особенностями разных форматов.
TR>Ну как идея?

А зачем все усложнять?
Берем любую случайную последовательность байт, и перебором подбираем к ней заказчика, авось повезет.

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

DG>зы
DG>теорема только говорит, что нельзя написать программу, которая по любой программе сообщает заканчивается та или нет.
DG>но она не говорит, что нельзя написать программу, которая будет определять конечность для 5%, 50%, 75% или 99% задач

Вот ведь спорщики.

Цитирую:

После этого еще один фильтр — на непадение сразу после запуска.

Так что непримесамонимость тут не причёмм.

WF>2) останавливаются за N шагов на любых входных данных (нафиг нам слишком долгие проги?).

А ведь как верно! Вот наш ответ товарищу Генри Николаевичу Чумберлену.

Давайте построим ИИ, который будет вести себя адекватно хотя бы пятьсот лет. Мне лично хватит с головой. А последующие поколения пускай поломают и нового соорудят, ещё на пятьсот лет.

DG>Вспоминается: "Я знаю, что задача неразрешима, но вы мне скажите как ее решать".

Кажется, "Понедельник начинается в субботу"?