Теория сложности.

[Профессор Снэйп]

вздымщик Цыпа писал(а):

void main() { char *c="void main() { char *c=%c%s%c; printf(c,34,c,34); }"; printf(c,34,c,34); }

Echo-Off писал(а):

VAR S:STRING;BEGIN S:='VAR S:STRING;BEGIN S:=;Write(Copy(S,1,22),#39,s,#39,Copy(S,23,49))END.';Write(Copy(S,1,22),#39,s,#39,Copy(S,23,49))END.

Ну да, ну да...

Х. Роджерс писал(а):

Примеры этого явления могут быть приведены в обычном русском языке. Выражение "результат подстановки "25" в "$x$ просто"" означает, конечно, "25 есть простое число". Выражение "результат подстановки "результат подстановки "$x$" в "$x$"" в "результат подстановки "$x$" в "$x$""" означает, как можно убедится, самоё себя.

Вообще, если проанализировать доказательство (первой) теоремы Гёделя о неполноте, то оттуда можно вытащить этот трюк. Я не знаю, следует ли приписывать его изобретение Курту Гёделю, или тот сам его откуда-то позаимствовал.

[Captious]

Профессор Снэйп в сообщении #144427 писал(а):

Вообще, если проанализировать доказательство (первой) теоремы Гёделя о неполноте, то оттуда можно вытащить этот трюк. Я не знаю, следует ли приписывать его изобретение Курту Гёделю, или он сам его откуда-то позаимствовал.

Курт просто напросто "формализовал" известный с давних времён "Парадокс Лжеца"...

[Профессор Снэйп]

Captious писал(а):

Курт просто напросто "формализовал" известный с давних времён "Парадокс Лжеца"...

Ключевое слово здесь --- "просто"

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

[Посторонний]

Sonic86 писал(а):

В курсе теории алгоритмов, предложенной Профессором Снейпом, на стр. 100 в примечании я нашел следующее:
"Есть классическая задача для программистов, которая заключается в том, чтобы написать программу, выводящую на экране свой собственный текст. ... теорема о неподвижной точке утверждает, что можно написать такую команду, которая не использует команд обращения к файлам, а лишь команду вывода на экран..."
Очень было бы интересно посмотреть на такую программу (желательно на С++ или на Pascal).
У нас на работе товарищи программисты очень удивились, что такая программа есть, хотя сомневались. Между тем, не могу представить себе код программы. Только вижу, что там должен быть цикл. И вопрос: в команде вывода параметры цикла можно использовать или нельзя (то есть происходит вывод только строк-констант?)?

а на жабаскриптах не пойдет?

http://bbi-math.narod.ru/intro/introjs.html

только надо отключить блокировку всплывающих окон... ну и жаба скрипты должны выполняться

на первой страничке код очень хорошо виден (просмотр ХТМЛ кода)
на копиях не очень понятно переводы строк съедаются

прикол в том, что код можно расширять за счет случайных символов; данная программа ставит случайный номер в тегах <title></title>, но можно придумать, чтобы вставляла случайные символы и в любое другое место... если сделать вставку случайных симвлоов в подходящее место и дать ей достаточно долго поразмножаться, то может появиться что-то неожиданное, способное к повторению в потомках... возможно саморазвитие... много забавных моментов есть:))

[Профессор Снэйп]

Посторонний писал(а):

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

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

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

[Anton Nonko]

Профессор Снэйп в сообщении #144802 писал(а):

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

Это очень интересно. Расскажите, а?

[MaximKat]

Не эта, случаянно?