Возможно ли создать программу путем перебора символов в файле?
Пришла в голову мысль и прошу знающий людей сказать, почему скорее всего(я так подозреваю), нельзя сделать сабж вопроса? Допустим мы написали алгоритм который просто вставляет в файл допустим столько символов, чтобы заполнить 1кк строк. Допустим наш компилятор очень умная вещь, которой не важно как мы соблюдаем грамматику языка. Не ставим скобки, не ставим пробелы, вобщем просто рандомно вставляем любые символы. Так же условимся, что чтобы создать нужную нам программу нужно именно миллион строк. Ну написал какой то программист программу, в ней миллион строк, она компилируется и работает. Мы путем полного перебора хотим полностью повторить эту программу. Так же у нас в распоряжении все компьютеры мира, чтобы каждый из них параллельно генерировал и компилировал эту программу. Возможно ли за конечное время, что программа будет создана?
DollyPapper, ну логично, что чем меньше символов, то больше вероятность.
к примеру php <?php echo 'Hello World'; ?>
Такую запись сможет перебрать даже обычный один компьютер и не за многое время. А учитывая что нам достаточно воспроизвести <?php echo 'тут что угодно'; ?>
то точно шанс будет выше.
Определенно возможно, а точнее вероятность отлична от нуля, хоть и мала. Но ничто не помешает "слепому случаю" устроить всё так, что такой набор символов будет сгенерирован в первую же итерацию.
Можно даже посчитать какова вероятность.
У нас 1 млн строк, в каждой строке пусть по 80 символов итого 80 млн символов на файл.
Допустим мы используем 60 символов из тех что есть на клавиатуре. Т.е. в каждом месте файла может быть один из 60 символов с клавиатуры.
Получим количество возможных вариантов файлов 60 в степени 80 млн.
Т.е. вероятность написать таким способом нужную программу равна 1 / 60 в степени 80 млн.
Таким образом теорема остается лишь теорией. На практике это невозможно в силу того, что мы не можем создать устройство, которое будет способно работать в течение неограниченного времени.
По вашему вопросу - программу, которая запускается и завершается - скорее всего можно случайным образом написать за минуту. Программу, которая выполняет некий алгоритм действий - зависит от размера программы - чем больше размер, тем геометрически больше времени понадобится.
Виктор Пелевин в своем романе "IPhuck 10" раскрыл тему.
Он назвал это рандомным кодом (RCP – "random code programming").
Вот цитата из книги: "RCP – это близкое по идеологии, но совершенно иное по целям и результатам направление в программировании. Здесь мы генерируем не случайные комбинации входных данных, а случайные последовательности самого программного кода. А потом прикладываем к этому коду принципы "exhaustive testing".
Это как с обезьяной, способной за миллион лет настучать на машинке "Войну и мир" – только в случае с RCP мы отводим миллиард лет, делаем обезьяне серьезный оверклок воткнутым в задницу высоковольтным проводом – и ожидаем, что она напишет нам не "Войну и мир", а программу, способную написать "Войну и мир".
Качество задачи меняется – поэтому нужна очень высокая производительность и большие объемы памяти. Сегодня с этим проблем нет: мощности избыточны. Достаточно задать требования к выходным секвенциям, и мы рано или поздно получим программу, которая будет делать то, что нам угодно..."
