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

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

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

TR>>Ну как идея?
B>Смешно

Да, еще твою идею можно применить к любому виду деятельности
Книжки так же писать можно, машины новые создавать.
Новые сорта пива тоже (дегустатором будешь ?)

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

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

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

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

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

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

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

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

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

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

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

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

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

TR>Ну как идея?

Моя очень сильно смеяться! Моя даже тюбетейку потеряль!
Идея отличная! Только есть замечания, многие из которых ранее уже были высказаны другими.
Конечно же надо оперировать машинными командами. Это во первых. Во вторых: несложно написать генератор. Сложно сделать автомат, опеределяющий полезность кода и его функциональность. И нужны большие вычислительные мощности.
Такая идея очень подходит для вируса, обладающего возможностью мутировать и самовольно изменяющего и наращивающего свою функциональность. Однако тут тоже надо иметь органы контроля. Новый код должен отлаживаться и в случае его достаточной работоспособности (фиг его знает, как это определять) включаться в тело вируса. Не обязательно, чтобы он тут же работал. Несколько итераций и новые куски должны соединяться и определяться их работоспособность. Если все плохо, то переконфигурация.
Значит надо модуль ИИ делать. Его отладить. Либо писать нейронные сети. Говорят нейронные сети обладают сильным потенциалом в области адаптации к задачам. А еще туда встроить генетические алгоритмы. Тут нужен коллектив со специалистами в математике, кибернетике, компиляторов, низкоуровневого системного программирования. И т.п. ...

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

{skip}

где дают такую траву?

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

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

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

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

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

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

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

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

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

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

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

M>>>Цитирую:
M>>>

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

B>>Осталось пояснить, что такое сразу после запуска.
B>>Мы программисты или кто?

M>Программисты как такую задачу решают. Спрашивают у заказчика и корректируют цифру в нужную сторону, сообразуясь со своими интересами.

M>Думаю, любому заказчику достаточно будет работы в течении пары часов. Если что, спина не переломится по второму разу запустить.

Искренне желаю тебе поработать на компе, на котором каждая прога, включая ОС,
падала бы с частотой раз в часа

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

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

Даже если отбросить в сторону генерацию программ, проверять правильность и нужность программ кто будет?

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

TR>Ну как идея?

оцени время перебора всех прог размером 1К. и сразу поймешь как тебе идея...

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

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

Так ведь она далеко не новая

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

TR>Ну как идея?

Почитай Гулливера. А именно, раздел про академию Лапутян

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

TR>Ну как идея?
Смешно

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

[...]
TR>Ну как идея?

Добавим ещё пару фильтров — ну там что-то по поводу выручки от программ, которые сразу не падают.

Ты форумом не ошибся, часом? Может, в "коллеги, улыбнитесь" сразу?

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

ГВ>Ты форумом не ошибся, часом? Может, в "коллеги, улыбнитесь" сразу?

Изначально это вообще в "Философии" было

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

ГВ>Ты форумом не ошибся, часом? Может, в "коллеги, улыбнитесь" сразу?

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

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

TR>Привет все.
TR>...

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

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

TR>Ну как идея?

Полный бред

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

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

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

TR>>Ну как идея?

C>Полный бред

C>Было доказано (кажется, Тьюрингом), что невозможно построить программу, которая получит на вход другую программу и за конечное число шагов определит, зависнет та или нет (или верна она или нет). Доказательство построено на коцепции машины Тьюринга к модели функционирования которой сводится вычислительный процесс на современных ПК.
C>Если интересно — доказательство могу привести
Приведи, очень интересно.

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


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

Точно его не помню, книга дома. Вечером напишу.

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

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

TR>>Ну как идея?

C>Полный бред

C>Было доказано (кажется, Тьюрингом), что невозможно построить программу, которая получит на вход другую программу и за конечное число шагов определит, зависнет та или нет (или верна она или нет). Доказательство построено на коцепции машины Тьюринга к модели функционирования которой сводится вычислительный процесс на современных ПК.
C>Если интересно — доказательство могу привести

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

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

Никак не могу понять — какое отношение теорема о самоприменимости имеет к данной идеи?

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

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

DG>Никак не могу понять — какое отношение теорема о самоприменимости имеет к данной идеи?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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

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

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

Цитирую:

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

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

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

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

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

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

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

А>Лет 5 тому назад один мужик (идея похоже ему тоже не принадлежит) рассказал про такой способ формировния картинок... прикинь, что можно увидеть все картинки мира, вплодь до убийцы Листьева

Вот уж проблема так проблема, убийца Листьева.

Парадокс-то из области четвёртого класса. Ну, к примеру, такая ещё задача: можно ли увидеть абсолютно неизлучающее тело?

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

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

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

M>Цитирую:
M>

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

Осталось пояснить, что такое сразу после запуска.
Мы программисты или кто?
Чувствую беседа пойдет в русло, что такое куча и есть ли вообще куча на свете

M>>Цитирую:
M>>

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

B>Осталось пояснить, что такое сразу после запуска.
B>Мы программисты или кто?

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

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

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

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

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

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

Ну дак в чем проблема?
Зафиксируй для начала N

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

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

TR>Привет все.
TR>Такой вопрос — что все мы, программисты, делаем в конечном итоге?

Так мы до Скайнета договоримся