Машина, що мутує власну програму

У січні 1958 року Річард Фрідберг з IBM описав спробу вчити комп'ютер, змінюючи його власні команди: «Учень» випадково замінює інструкції в програмі малої машини «Герман» і залишає ті, з якими частіше приходить успіх. Машину з 64 однобітних комірок даних і 64 чотирнадцятибітних інструкцій симулювали на IBM 704; результат автор сам називає «limited success».

Устрій. Програма «Германа» діє на 64 комірки даних, у кожній один біт (D0-D63), і 64 комірки інструкцій по 14 бітів; «Вчитель» перед кожним випробуванням записує випадкові біти у вхідні комірки, після виконання перевіряє співвідношення вхідних і вихідних бітів і повідомляє «Учню» про успіх чи невдачу; «Учень» змінює програму лише після невдачі, заміняє інструкції випадковими й лишає ті, що частіше пов'язані з успіхом. Усе симулюють на IBM 704: від 5 000 до 10 000 випробувань за хвилину. Задача 1: вхід D0, вихід D63, успіх — коли вихідний біт дорівнює вхідному; випадкова програма, що встигає завершитися, розв'язує її приблизно в 50 % випробувань. Дослід 1: за перші 60 000 випробувань (етап 1) частота успіху росте майже від нуля до трохи менш як половини, бо зникають невдачі за часом; наступні 90 000 (етап 2) вона коливається біля 45 %; в останніх 50 000 (етап 3) Герман «hit the jackpot»: програма, надрукована в статті (Chart 1), успішна на задачі 1 за будь-якої послідовності вхідних бітів. Автор не вирішує, чи етап 2 був лише випадковим блуканням, чи поступово підвищував шанс знайти досконалу програму. Дослід 2: варіант «Шерман» не має двох особливостей Германа (адреса інструкції як третя адреса й непряма адреса), які мали допомагати зберігати запис успішності однієї інструкції незалежно від решти; за 800 000 випробувань він жодного разу не досяг успіху більше ніж у половині будь-яких 20 000 підряд, тоді як Герман знайшов досконалу програму за 150 000. Дослід 3: дослід 1 повторено дев'ять разів з іншими початковими випадковими числами; у восьми повторах досконала програма знайдена за 30 000-210 000 випробувань, у середньому близько 100 000, у дев'ятому час вичерпався після 220 000. Далі задачі складніші. Дослід 4: чергування задач 1 і 2 (вихід — доповнення входу) із повторним дорозв'язанням. Дослід 6: молодший біт суми двох вхідних бітів (задача 4) — досконала програма після 940 000 випробувань. Дослід 8: задача 6, вихід 1 у непарних і 0 в парних випробуваннях, — менш ніж за 20 000; а чергування задач 1 і 2 у послідовних випробуваннях — жодної досконалої програми за 2 130 000 випробувань (863 447 успіхів). Дослід 5: задача 3, двобітна сума двох вхідних бітів, — жодної досконалої програми за 2 420 000 випробувань, 612 063 успіхи, що, за автором, відповідає очікуваному для випадкової програми (без невдач за часом) середньому в чверть; дослід 7: старший біт суми (задача 5) — жодної за 2 740 000, 1 367 321 успіх, тобто в межах половини. Дослід 9: якщо кожне десяте випробування оголошено невдачею, тож навіть досконала програма мала б 90 %, Герман за 1 380 000 випробувань не втримував частоту вище 45 % довше ніж близько 50 000 випробувань; автор називає це серйозною вадою збереження статистично вигідних, але не безпомилкових інструкцій. Висновок статті: результати, хоч і уривчасті, показують, що за практичну кількість випробувань така машина досягає успіху, достатнього для змістовних дослідів. Чого запис не стверджує: результатів другої частини (Friedberg, Dunham, North, 1959), яку не читано; що метод перевершує випадковий пошук (на двобітній задачі автор бачить успіх на рівні випадкового); що це перша програма, яка змінює власні команди; зв'язку з Голландом 1975 року; таблиці й Chart 2 покомірково не перевірялися. Одне джерело, власна стаття автора: впевненість середня.