Алгоритмічна непередбачуваність

Ця невелика стаття дає популярне уявлення про принципи адаптації і машинного пошуку на живих прикладах із завдань передбачення погоди шифрування інформації і біржової торгівлі. Будь-яка формується область людського пізнання спочатку насамперед потребує уточнення використовуваних понять і контртеоремных твердженнях, щоб позбавити багато людей від безплідних спроб створення вічного двигуна, філософського каменю або машини часу, так що, якщо ви обираєтесь займатися чим-небудь, пов'язаним з адаптацією, то потрапили точно за адресою.

Так сталося, що природа вкрай не випадкова: її явища виявляють різні закономірності, причому деякі з них люди здатні помічати і використовувати в своїх прогнозах. Наприклад, досить довго спостерігаючи зміну фаз Місяця, ми здатні помітити закономірність їхньої зміни і, знаючи в якій фазі вона була вчора, правильно передбачити, якою вона буде завтра або через тиждень.



Взагалі, під закономірністю в порядку відбуваються зміни (або подій) будемо розуміти наявність певної обчислювальної процедури, виконуючи яку, ви здатні відновити цей порядок. Строго кажучи, знання закономірності само по собі не дає ще можливості робити правильні прогнози. Тривіальним буде приклад, коли розташовуючи правилом зміни фаз, ви не знаєте в якій фазі Місяць сьогодні. Інші, менш тривіальні приклади, наведені трохи пізніше.

Варто особливо відзначити, що будь-яка помічена закономірність у проведених до теперішнього часу спостереженнях анітрохи не зобов'язує подальші спостереження цієї закономірності підкорятися, тому всі такі закономірності повинні мати статус не більше ніж гіпотез і ніяким чином принципово не можуть бути доведені.

Які саме гіпотези варто висувати в конкретних ситуаціях — питання дуже складне, проте точно не варто висувати ті, які суперечать вже зробленими спостереженнями.

Аби трохи пояснити сказане, уявімо собі кілька футуристичну ситуацію. Медики створили засіб жити вічно, і, будучи не в силах поміщатися на рідній Землі, люди відправилися освоювати далекі куточки галактики, в одній з цих експедицій брали участь і ви. Досягнувши поверхні мальовничій планети, ви виявили там пристрій, малюнки на якому недвозначно говорили про його здатності передбачати правильно: буде дощ завтра чи немає на планеті. У вас, звичайно, був з собою парасольку, але, як і всі речі для вічного життя, він обов'язково виявився громіздким і незручним,- а як приємно після обіду прогулятися по заповідних куточках незнайомого світу. Для отримання метеорологічних прогнозів знайдену машину необхідно було ввести номер потрібної планети, але от біда — на вашій планеті номери ніде написано не було. Древня цивілізація, яка побувала тут, звичайно присвоїла цій планеті номер, але який? — абсолютно невідомо. Маючи попереду цілою вічністю і не збираючись все життя без потреби носити парасольку, можна діяти наступним чином: ввести «1» і, до тих пір поки передбачення пристрої дійсно підтверджуються, слідувати їм. Якщо ж у якийсь день, незважаючи на прогноз, вам довелося вимкнути або носити парасольку закритим, введіть номер на одиницю більше попереднього і знову виконайте прогнозам. Оскільки планета має певний номер N, то сюрпризів погоди при такому рецепті дій у вашій вічного життя станеться не більше N. Подібні рецепти назвемо схемами простого перебору гіпотез.

Для наведеного прикладу є доказ, що в кінці кінців ви будете розташовувати правильним пророкує пристроєм, однак, навіть володіючи останнім, у вас все одно не буде ніякого способу довести його правильність. На противагу цьому, розглянемо інший випадок, коли є впевненість у правильності розташовуваної закономірності, але жодного прозорого способу використовувати ці знання для прогнозів немає.

Так вже вийшло, що в далекому майбутньому Австралія вирішила воювати з Океанією. Спеціально для цього перед війною австралійські інженери побудували серію абсолютно однакових машин для отримання правил шифрування быстроустаревающей інформації. Кожна з цих машин, працюючи безперервно після включення, кожні 24 години видає список правил шифрування. Всі, крім одного, вони були включені за добу до початку війни. Забезпечені ними австралійські частини обмінювалися повідомленнями, час значущості яких не перевищувала одного дня. Правда шифри були досить прості, так що сили Океанії розшифровували всі такі повідомлення на наступний же день, але ніякої переваги їм це не давало. Та єдина машина, яка не була запущена, зберігалася у військовому музеї Австралії, звідки, так вийшло, що її вкрали шпигуни Океанії. Якщо викрадена машина, а це сталося через рік після початку війни, принципово не може бути розкрита або як прискорена у своїй роботі, можна використовувати її для отримання поточного шифру Австралійських сил? По всій видимості, немає: адже результати її роботи, навіть якщо після розкрадання вона тут же була включена, відстають на цілий рік.

Щоб розібратися у всьому цьому краще і мати можливість робити точні твердження, розглянемо кілька типів машин.

1) Автоматична друкарська машина. Ці машини, працюючи, видають послідовність слів «так» або «ні», друкуючи їх на (нескінченно) довгій паперовій стрічці, спочатку якимось чином в них заправленої.(рис1) Машини, що дають однакові послідовності, будемо називати эквивалентыми.
image

2) Машини пошуку закономірності
здатні переглядати слово за словом послідовності, надруковані автоматичними друкованими машинами, і в якості гіпотез іноді друкувати креслення того, як на їх думку влаштовані ці машины.Выдав черговий креслення, машина пошуку продовжує свою роботу далі, перевіряючи збігаються надалі переглядається нею послідовність і послідовність дається друкарською машиною, що працює згідно з останнім кресленням.(рис2)
image

3) Повільні машини передбачення, подібно машин пошуку переглядають стрічки, видані друкованими машинами, і друкують припущення: яким буде наступне прочитане слово. Таким чином, повільна машина не переходить до перегляду десятого по порядку слова, якщо вона не надрукувала до цього моменту гіпотезу про десятому слові.(рис3)
image

4) Машини швидкого передбачення (швидкі машини) на відміну від повільних працюють не на вже надрукованої «повністю» послідовністю слів, а безпосередньо слідом за друкарською машиною. Їх завдання — друкувати гіпотезу про наступному слові швидше, ніж це слово з'явиться друкарської машини.(рис4)
image

У певному сенсі, питання, пов'язані з першими трьома типами машин, можуть бути переформульовані як питання про алгоритми. Питання про останньому типі має багато в чому технологічну специфіку, того, яким чином ці алгоритми реалізовані.

*Теореми математичної логіки стверджують, що немає загального способу в конструкції або кресленням алгоритмічно зрозуміти, чи видасть друкарська машина нескінченну ланцюжок слів або після деякого, а може бути і зовсім нічого не надрукувавши в ході своєї роботи, не видасть більше жодного слова. Однак, тут буде передбачатися, що завжди, коли це можливо, машини друкують нескінченні послідовності.*

Якщо машини передбачення змусити переглядати свої ж стрічки? Нехай на деякому кроці такої роботи машина H (hipotesis constructor ) робить припущення, що наступним буде переглянуто деяке слово, наприклад, «так», тоді надрукувавши це слово як гіпотезу, вона його в слід за цим і прогляне: припущення завжди виявляються правильними, а машина передбачення перетворюється в друкарську машину. (рис5)
image

Такий режим роботи пророкують машин назвемо позитивної депривацією. Однак цікавіше виявляється режим негативної депривації. Для цього візьмемо звертає модуль N (рис 6), вся робота якого зводиться до того, щоб прочитати слово і з деякою затримкою по часу надрукувати йому зворотне своїй стрічці. Якщо стрічку N в цій конструкції сприймати як зовнішню, а стрічку H як внутрішнє пристосування, то виходить деяка друкарська машина HнеD.
image
Машину H швидкому випадку тут можна розглядати як самостійну машину передбачення, що працює слідом за машиною HнеD ( частина досліджує ціле). Зрозуміло, всі передбачення H про слова, друку HнеD виявляються невірними. Для більшої очевидності візьмемо ще один примірник H і приєднаємо його до стрічки HнеD(рис7). Якщо зовнішні і внутрішні екземпляри машини H включають одночасно, то, як не складно зрозуміти, хід їх роботи збігається. Ці ж міркування з невеликими змінами застосовні і до повільних машин.
image
Тепер є можливість відповісти на питання, центральний для даної статті: чи існують абсолютні адаптивні машини, а саме:
1) Існує абсолютна машина пошуку, яка, досить довго переглядаючи будь-алгоритмічну послідовність, може бути після декількох невдалих припущень, врешті-решт видає креслення якої-небудь машини, здатної надрукувати цю послідовність?

2) Існує абсолютна повільна машина передбачення, працюючи на будь-алгоритмічної послідовності, здатна робити за винятком кінцевого числа, всі передбачення правильно?

3) При яких припущеннях про конструкторських (технологічних) можливості може існувати аналогічна повільної абсолютна швидка машина передбачення?

Простіше всього отримати відповідь на другій з цих питань:
Оскільки ніяка повільна машина не здатна зробити жодного правильного передбачення про надрукованій нею ж в режимі негативної депривації алгоритмічної послідовності, то ні одна повільна машина абсолютної бути не може.
Питання про існування абсолютної машини пошуку зводиться до попереднього. Припустимо така машина існує, тоді всякий раз, коли, працюючи над певною алгоритмічної послідовністю, вона друкує «креслення», виконаємо згідно з цим кресленням друкарську машину і, після, можливо, деякого попереднього часу роботи цієї друкарської машини, використовуємо її для передбачення. Бо, зрештою, буде надруковано правильний креслення, буде і для кожної алгоритмічної послідовності побудована за нього правильна друкарська машина, і з цього моменту всі прогнози стануть правильними. З сказаного слід, що наведена схема є алгоритм роботи деякої абсолютної повільної машини передбачення, якої, як було показано раніше, не може існувати.

Проблема існування або не існування абсолютної швидкої машини трохи тонше. Можна сказати так, якщо технології дозволяють реалізувати схему негативної депривації, то абсолютну машину швидкого передбачення побудувати не можна.

Наостанок варто навести приклад, пов'язаний з біржовими торгами, коли абсолютна для деякого класу повільна машина може бути побудована, а абсолютна швидка існувати не може.

По ходу всього викладу ніякого обмеження, крім кінцівки, на тривалість роботи машин між висновками на друк чергових слів не накладалося. Однак у деяких ситуаціях ми не можемо дозволити машин таку «розкіш»: пристрій управлінням зенітним вогнем не військовому кораблі або автопілот сучасного авіалайнера, по всій видимості, повинні приймати свої рішення у режимі реального часу.

Полуформально будемо говорити про друкарській машині «реального часу», якщо, будучи включеною, вона друкує рівно одне слово в точності в кінці кожної хвилини по гринвическому часу. Таке ж обмеження накладемо на технологію швидких машин передбачення «реального часу» і, щоб позбутися від колізій, машини передбачення будемо включати за хвилину до початку роботи друкованих машин, аналізованих ними.

Тисяча людей по всьому світу шукають спосіб передбачати біржові курси, вважаючи, що в їх змінах є певні закономірності. Уявімо фантастичну ситуацію, коли курс долара не визначається якимось чином ринком, а видається друкарською машиною «реального часу». Цю машину B назвемо біржовий. Існує спосіб, досить довго спостерігаючи за біржової машиною, яка б вона не була, навчитися передбачати її хоча б на одну хвилину вперед? Машину «реального часу», здатну це робити, назвемо абсолютним біржовим аналізатором A(рис8).
image
Докази про неможливість існування абсолютного біржового аналізатора знову скористаємося його роботою в режимі негативної депривації, при цьому вважаючи величину затримки в звертає модулі N дорівнює одній хвилині. На малюнках 9 і 10 наведена робота однієї з можливих таких схем в протягом декількох хвилин.
imageimage

*При великих затримки N доводиться йти на хитрості. Скажімо, при затримці вже дві хвилини схема депривації не працює — вона дозволяла б довести неіснування аналізаторів, дають прогноз на дві хвилини вперед. Здогадається читач, як розташовуючи декількома екземплярами звичайного абсолютного аналізатора, сконструювати абсолютний аналізатор, що дає прогноз на дві хвилини вперед?*

При неможливості побудувати абсолютний аналізатор чарами здається можливість, досить довго спостерігаючи за будь біржової машиною, може бути після кількох помилок в кінці кінців правильно знайти креслення (еквівалентної) цієї машини на початок її роботи. Абсолютна машина такого пошуку реалізує схему простого перебору гіпотез. Якщо сконструювати довільну машину M(рис11),
image
взагалі кажучи, вона може не бути машиною реального часу, і, може так вийти, довго працюючи, взагалі нічого не надрукувати. Візьмемо тому модуль прийняття рішення D, переглядаючи стрічку M, цей модуль всякий раз, коли на попередній хвилині M надрукувала якесь слово друкує це ж слово, в іншому випадку друкує «так»(рис12).
image
Якщо ж M — машина реального часу, то така надбудова істотних змін у роботу M не вносить. Згадана абсолютна машина пошуку повинна в якості гіпотез перераховувати креслення всіх можливих друкарських машин, доповнюючи їх кресленнями модуля D — рано чи пізно відповідний креслення зустрінеться.

Коваленко Сергій,
осінь, 2014 рік, р. Дубна.
www.webisgroup.ru
Будь-які зауваження ви можете надіслати на пошту magnolia@bk.ru

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.