Universal Memcomputing Machines як альтернатива Машині Тюрінга

Дану статтю можна вважати вільним перекладом (хоча швидше спробою розібратися) даній статті. І так, написанна вона скоріше для математиків, ніж для широкої аудиторії.

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

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

Взагалі кажучи, є інші моделі — Недетерминированная машина Тюрінга, Квантові машини Тюрінга. Однак вони (поки що) є лише абстрактними моделиями, не реалізуються на практиці.

Півроку тому в Science Advances вийшла цікава стаття з моделлю обчислень, яка істотно відрізняється від МТ і яку цілком можливо реалізувати на практиці (власне стаття була про те, як вони порахували завдання SSP на реальному залозі).

І так. Найцікавіше в цій моделі є те, що, за запевненням авторів, в ній можна вирішувати (деякі) задачі з класу NP-повних задач за поліном часу і пам'яті.

Напевно відразу варто обумовити, що даний результат не означає вирішення проблеми P = NP. Адже постановка цієї проблеми не вирішити задачу q \in NPcompleteза n^{const}часу», а можна симулювати недетерминированную машину Тюрінга на звичайній машині Тюрінга за поліном часу. Так як тут зовсім інша модель обчислень, про класичних класах складності говорити не можна.

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

Невелике введення
Що представляє собою комп'ютер (точніше найбільш популярна реалізація МТ — арх. фон-Неймана) сьогодні? Якийсь інтерфейс вводу-виводу, пам'ять і CPU, який фізично відділений від них. В CPU ж знаходяться як модуль, керуючий ходом обчислень, так і блоки, які ці обчислення виконують.

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

Запропонована модель даних надихалася роботою мозку (фраза досить побита, але сюди підходить). Її суть у тому, що обчислення відбуваються не в окремому пристрої, куди потрібно перенести дані, а прямо в пам'яті. Порядок обчислення контролюються зовнішнім пристроєм (Control Unit).

Ця модель обчислень, отримала назву Universal Memcomputing Machines (перекладати цей термін я не став. Далі я буду вживати скорочення UMM).

У даній статті ми спочатку згадаємо як формально визначається МТ, потім подивимося визначення UMM, подивимося на прикладі як задати алгоритм рішення задачі на UMM, розглянемо декілька властивостей, у тому числі найважливіше — information overhead.

Формальний опис моделі.
Universal Тьюринга Machine (UTM)
Я думаю ви всі пам'ятаєте, що таке машина Тюрінга (інакше сенсу читати цю статтю немає). Стрічка, каретка, всі справи. Давайте згадаємо лише як вона визначається формально.

Машина Тьюрінга — це кортеж

UTM = (Q, \Gamma, b, \Sigma \delta, q_0, F),
де Q— безліч можливих станів,
\Gamma— безліч можливих символів стрічки
b \in \Gamma— порожній символ
\Sigma— безліч вхідних символів
q_0— початковий стан
F \subseteq Q— множина кінцевих станів

\delta : Q \smallsetminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L, N, R\}, де L, N, Rвідповідно зсув вліво, без зміщення, зсув вправо. \delta— наша таблиця переходу.

Мемпроцессор.
Для початку визначимо нашу комірку пам'яті UMM — мемпроцессор.

Мемпроцессор визначається як 4-кортеж (x, y, z, \sigma), де x— стан мемпроцессора y— вектор внутрішніх змінних. z— вектор «зовнішніх» змінних, тобто змінних, що з'єднують різні мемпроцессоры. Іншими словами, якщо z_1z_2— вектора зовнішніх змінних двох мемпроцессоров, то два мемпроцессора соедененны \Leftrightarrowz_1 \cap z_2 \neq \O. Також, якщо мемпроцессор не з'єднаний ні з ким, то z = z(x,y), тобто визначається тільки внутрішнім станом.

І, нарешті, \sigma[x,y,z] = (x', y'), тобто \sigma— оператор нового стану.

Хочу нагадати, що мемпроцессор — не той процесор, який ми зазвичай уявляємо в голові. Це скоріше комірка пам'яті, яка має функцію отримання нового стану (функціональну).

Universal Memcomputing Machine (UMM)
Тепер введемо формальне визначення UMM. UMM — модель обчислювальної машини, сформованої з сполучених мемпроцессоров (які, взагалі кажучи, можуть бути як цифрові, так і аналогові).

UMM = (M, \Delta, \mathcal{P}, S, \Sigma, p_0, s_0, F),
де M— безліч можливих станів мемпроцессора
\mathcal{P}— безліч покажчиків на мемпроцессоры (використовуються в \delta, щоб вибрати потрібні мемпроцессоры)
S— безліч індексів \alpha(номер використовуваної функції \delta)
\Sigma— початковий стан мемпроцессоров
p_0— початкова безліч покажчиків
s_0— початковий індекс оператора ($\alpha$)
F \subseteq M— множина кінцевих станів

\Delta = \{ \delta_{\alpha} \ | \ \delta_{\alpha}: M^{m_{\alpha}} \smallsetminus F \times \mathcal{P} 
\rightarrow M^{{m'}_{\alpha}} \times \mathcal{P}^2 \times S \},
де m_{\alpha} < \infty— кількість мемпроцессоров використовуються як вхід функцією \delta_{\alpha}{m'}_{\alpha} < \infty— кількість мемпроцессоров, використовуваних як вихід функцією \delta_{\alpha}.

За аналогією з машиною Тюрінга, як ви могли вже здогадатися, \delta_{\alpha}— функції переходу, аналог таблиці станів. Якщо подивитися на прикладі, то нехай p_{\alpha}, {p'}_{\alpha}, p_{\beta} \in \mathcal{P}— покажчики на мемпроцессоры p_{\alpha} = \{ i_1, \dots, i_{m_{\alpha}} \}x(p)— вектор станів даних мемпроцессоров, а \beta \in S— індекс наступної команди,

\delta_{\alpha} [x(p_{\alpha})] = (x'({p'}_{\alpha}), \beta, p_{\beta})
Взагалі кажучи, відкидаючи формалізм, головна відмінність UMM від МТ в тому, що в UMM впливаючи на одну комірку пам'яті (тобто на мемпроцессор), ви автоматично впливаєте і на її оточення, без додаткових викликів з Control Unit.

Зазначимо 2 властивості UMM, безпосередньо випливають з його визначення.
  • Властивість 1. Intrinsic parallelism (я так і не визначився, як правильно перекласти цей термін, тому залишив як є). Будь-яка функція \delta_{\alpha}може запускатися на будь-якій множині процесорів одночасно. У машині Тюрінга для цього потрібно вводити додаткові стрічки і головки.
  • Властивість 2. Функціональний поліморфізм. Воно полягає в тому, що, на відміну від машини Тюрінга, UMM може мати багато різних операторів \delta_{\alpha}.

Взагалі кажучи, не так вже й складно модифікувати машину Тюрінга так, щоб вона теж мала даними властивостями, але автори наполягають.

І ще кілька зауважень за визначенням. UMM, на відміну від машини Тюрінга, може мати нескінченне простір станів при кінцевому кількості мемпроцессоров (з-за того, що вони можуть бути аналоговими).

До речі кажучи, UMM можна розглядати як узагальнення нейронних мереж.

Доведемо одну теорему.
UMM — універсальна машина (тобто машина, яка може симулювати роботу будь МТ).
Доведення.

Іншими словами, нам потрібно показати, що машина Тьюрінга — приватний випадок UMM. (вірно зворотне — не доведено, і, якщо автори статті праві, але це буде еквівалентно доказу P = NP)

Нехай у визначенні UMM, M = Q \cup \Gamma. Один з мемпроцессоров ми позначимо як j_s, решта (можливо нескінченна кількість) j. Далі ми визначимо покажчик p = \{j_s, j\}. j_sми будемо використовувати позначення стану q \in Qjяк символ стрічки (\Gamma).

\Deltaу нас буде складатися з єдиною функції \delta [ x(p) ] = (x&#39;(p), p&#39;)(опускаємо \beta, так як функція лише одна). Новий стан <img src=«tex.s2cms.ru/svg/x' alt=»x'"/> визначається за таблицею переходів МТ x&#39;(j_s)— буде новий стан, x&#39;(j)— новий символ стрічки. Новий покажчик p&#39; = \{j_s, j&#39;\}j&#39; = jякщо переходу каретки немає, j&#39; = j + 1якщо переміщаємо курсор вправо, j&#39; = j - 1якщо вліво. У підсумку, при записі в xпочатковий стан q_0і початковий символ \Sigma, \Delta = \deltaUTM симулює універсальну машину Тюрінга.

Теорема доведена.

Алгоритми
Подивимося на прикладі, як можна вирішувати завдання на UMM (поки просто щоб познайомитися з моделлю). Візьмемо задачу про сумі підмножини (Subset Sum Problem, SSP).

Нехай є множина G \in \mathds{Z}і задано число s. Існує підмножина K \subseteq G, сума елементів яких дорівнює s.

Экпоненциальный алгоритм
Нехай у нашій UMM мемпроцессоры розташовані в матричному вигляді (див. малюнок). Визначимо три операції.

  1. \chi— це безпосередньо обчислення. Використовуючи активаційні лінії, ми можемо вибрати рядки і обмежують стовпці, в яких проводяться обчислення. Суть обчислення в зростанні значення крайньої лівої клітинки до всієї рядку.
  2. \mu— це операція переміщення даних. Вузол контролю вибирає дві колонки і значення з першої копіюються у другу. Вузол контролю не обов'язково сам виконує операцію копіювання, він просто активує колонки потрібними лініями.
  3. p— операція, схожа на \mu, тільки вона бере 1 значення і записує його в колонку.
Комбінуючи ці три операції, ми можемо отримати функцію переходу \delta = \mu \circ \chi \circ p.

На першому кроці алгоритму ми отримуємо суму всіх підмножин завдовжки n-1, на другому кроці підмножин n-2і так далі. Як тільки ми знайшли потрібне число (воно буде в лівому стовпці), ми знайшли відповідь. Кожен крок виконується за один виклик функції \delta, отже алгоритм працює n-1кроків.

Тепер порахуємо скільки мемпроцессоров нам потрібно для виконання цих операцій. На ітерації k нам потрібно \binom{n-1}{k-1} (n+2-k)мемпроцессоров. Оцінка для даного виразу за формулою Стирлинца — (n/2 \pi)^{1/2} 2^{n-1}. Кількість сайтів росте експоненціально.

Думаю зараз стало більш-менш зрозуміло що це за такий об'єкт. Тепер перейдемо до самого смачного, що нам пропонує UMM, а саме до третього властивості information overhead.

Exponential Information Overhead
Нехай у нас є n мемпроцессоров, позначимо стан обраних мемпроцессоров x(p) = (x(j_1), \dots, x(j_n)). Стан окремого мемпроцессора x(j) = u_jміститься у внутрішніх змінних u_j \in M_a. u_j— вектор. Також для кожного мемпроцессора розділимо зовнішні змінні на 2 групи — «in» і «out» (out одного мемпроцессора підключається до in іншого). На картинці незаповнений коло — компонента (u_j)_h = 0. Припустимо також, що у нас є пристрій, яке, будучи підключеним до потрібного мемпроцессору, може разом вважати u_j.

Це пристрій, підключений до декількох мемпроцессорам може вважати стан обох, а значить їх глобальний стан, обумовлений як u_{j_1, j_2} = u_{j_1} \diamond u_{j_2}, де \diamond : R^d \times R^d \rightarrow R^d— коммутативная, асоціативна операція d = \dim(u_j). Визначається ця операція

(u_{j_1} \diamond u_{j_2})_{h \star k} = (u_{j_1})_h \ast (u_{j_2})_k,
де \star: \mathds{Z} \times \mathds{Z} \rightarrow \mathds{Z}\ast: R \times R \rightarrow R— коммутативные і асоціативні операції з h \star 0 = hx \ast 0 = 0. Причому, якщо для <img src=«tex.s2cms.ru/svg/h%2C%20k%2C%20h'%2C%20' alt=»h, k, h', k'"/> виконується <img src=«tex.s2cms.ru/svg/h%20%5Cstar%20k%20%3D%20h'%20%5Cstar%20k' alt=»h \star k = h' \star k'"/>

(u_{j_1} \diamond u_{j_2})_{h \star k} = (u_{j_1} \diamond u_{j_2})_{h \star k} \oplus (u_{j_1} \diamond u_{j_2})_{h&#39; \star k&#39;},
де \oplus: R \times R \rightarrow R— коммутативная, асоціативна операція, для якої x \oplus 0 = x.

Тепер, маючи безліч G = \{a_1, \dots, a_n\}цілих чисел, визначимо повідомлення m = (a_{\sigma_1} \star \dots \star a_{\sigma_k}) \cup (a_{\sigma_1} , \dots , a_{\sigma_k}), де (\sigma_1, \dots, \sigma_k)— індекси взяті з різних підмножин \{1, \dots, n\}. Таким чином безліч повідомлень Mскладається з \sum_{j=0}^m \binom{n}{j} = 2^nрівноймовірно повідомлень m, кількість інформації по Шеннону одно I(m) = -\log_2(2^{n}) = n

Тепер, беручи n мемпроцессоров, ми виставляємо ненульові компоненти u_{j_0}, u_{j_h}, де h \in \{1, \dots, n\}. Таким чином ми закодували всі елементи Gна мемпроцессорах. З іншого боку, підключаючись до потрібних мемпроцессорам зчитуючи їх глобальний стан (за формулами там як раз виходить сума елементів), ми можемо вважати будь-яке можливе стан m. Іншими словами, n мемпроцессоров може закодувати (стиснути інформацію, якщо хочете) 2^nповідомленнях одночасно.

Алгоритм рішення SSP, що використовує Exponential Information Overhead
Тут я змушений сказати, що я так і не зміг розібратися в деталях цього алгоритму (склалося те, що я не так вже сильний в електротехніці та обробки сигналів, а автори, мабуть, вирішили не розписувати все для таких неуків), але загальна ідея така.

Для початку вони пропонують подивитися на функцію

g(x) = -1 + \prod_{j=1}^n (1 + e^{i 2 \pi a_j x})
Якщо ми розкриємо дужки, то у нас будуть твори по всіляких наборів індексів j(позначимо такий набір P), а вони дорівнюють

\prod_{j \in P} e^{i 2 \pi a_j x} = \exp \left(i 2 \pi x \sum_{j \in P} a_j \right)
Іншими словами, наша функція gмістить інформацію про суми всіх підмножин G. Тепер, якщо розглянути функцію g як джерело сигналу, то кожна експонента дає свій внесок у результуючий сигнал, причому внесок з частотою \sum_{j \in P} a_j.

Тепер, все, що нам потрібно — це застосувати до цього сигналу перетворення Фур'є і подивитися які частоти є у нас в сигналі. Якщо у нас є компонента з частотою s, то підмножина G, з сумою s.

Якщо ми вирішуємо цю задачу на звичайному комп'ютері, то зараз ми могли б застосувати швидке перетворення Фур'є. Оцінимо асимптотику.

Для цього оцінимо кількість точок, що потрібно взяти з сигналу. За теоремою Котельникова цих точок потрібно N = 2 f_{max} + 1, де f_{max} &amp;lt; n \max\{|a_j|\}— оцінка на максимальну можливу величину частоти. У статті автори ввели додаткову змінну p, яка пропорційна Nі вважали асимптотику через неї.

Таким чином, використовуючи FFT ми можемо вирішити завдання за O(p \log(p)). Тут потрібно зауважити, що, як і в задачі про рюкзак (а SSP — окремий випадок задачі про рюкзак), $p$ зростає експоненціально. Для нашої задачі також можна використовувати алгоритм Герцеля, що дасть нам O(n p). Запропонований авторами метод дозволяє позбавиться від pв асимптотиці, що дасть нам лінійний час.

Тепер, своїми словами (для більш детального розгляду, зверніться до оригінальним статтям) як вони цього досягли.

Беремо nаналогових мемпроцессоров, внутрішнім значенням яких буде значення якогось числа з G. В якості операторів \star\astвзяті, відповідно, додавання і множення.

Але це в нашій моделі. В залозі виходить, що кожен мемпроцессор — генератор сигналу зі своєю частотою (відповідний числу з G), загальний стан мемпроцессоров — просто додавання сигналу. Виходить, що ці мемпроцессоры симулюють функцію g.

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

Разом асимптотика за часом взагалі склала O(1), асимптотика за мемпроцессорам склала O(n). Пускаємо салют? Не поспішайте.

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

Справа все в кодуванні сигналу (виразні пояснення я знайшов тут). З-за того, що ми кодуємо аналогові сигнали, і використовуємо дискретні генератори сигналів, нам тепер потрібна експонентна точність по визначенню рівня сигналу (в тій залізці, яка виділяє потрібну частоту), що, можливо, зажадає експоненти часу.

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

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

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

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

0 коментарів

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