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

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

06.01.2016 10:20

myxo 9 9400 Источник

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

Небольшой спойлер: в начале это казалось мне какой-то магией, но потом я понял подвох…

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

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

Полгода назад в 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 Turing 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_1$ и $z_2$ — вектора внешних переменных двух мемпроцессоров, то два мемпроцессора соединены $\Leftrightarrow$ $z_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 Q$ , $j$ как символ ленты ( $\Gamma$ ).

$\Delta$ у нас будет состоять из единственной функции $\delta [ x(p) ] = (x'(p), p')$ (опускаем $\beta$ , так как функция только одна). Новое состояние $x'$ определяется таблицей переходов МТ, $x'(j_s)$ — будет новое состояние, $x'(j)$ — новый символ ленты. Новый указатель $p' = \{j_s, j'\}$ , $j' = j$ если перехода каретки нет, $j' = j + 1$ если каретку перемещаем вправо, $j' = j - 1$ если влево. В итоге, при записи в $x$ начальное состояние $q_0$ и начальный символ из $\Sigma$ , с $\Delta = \delta$ UTM симулирует универсальную машину Тьюринга.

Теорема доказана.

Алгоритмы

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

Пусть есть множество $G \in \mathds{Z}$ и задано число $s$ . Существует ли подмножество $K \subseteq G$ , сумма элементов которых равна $s$ .

Экпоненциальный алгоритм

Пусть в нашей UMM мемпроцессоры расположены в матричном виде (см. рисунок). Определим три операции.

$\chi$ — это непосредственно вычисление. Используя активационные линии, мы можем выбрать строки и ограничивающие столбцы, в которых производятся вычисления. Суть вычисления в прибавлении значения крайней левой ячейки ко всей строке.
$\mu$ — это операция перемещения данных. Узел контроля выбирает две колонки и значения из первой копируются во вторую. Узел контроля не обязательно сам выполняет операцию копирования, он просто активирует колонки нужными линиями.
$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 = h$ и $x \ast 0 = 0$ . Причем, если для $h, k, h', k'$ выполняется $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' \star k'},$

где $\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} < 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. Вполне возможно, что мы узнаем о нейронных сетях немного больше, если посмотрим на них с другой стороны, используя немного другой мат. аппарат.

Комментарии (9)

supernapalm
06.01.2016 18:37
#8727487
Наверное сразу стоит оговорить, что данный результат не означает решения проблемы . Ведь постановка этой проблемы не «решить задачу за времени», а можно ли симулировать недетерминированную машину Тьюринга на обычной машине Тьюринга за полином времени.

На самом деле, если вы решаете одну NP-полную задачу за полином то сразу же решаете и ВСЕ NP задачи за полином. Причем в этой же модели вычислений, как я понимаю, раз она симулирует МТ. А если даже нет — на практике как раз свести (за полином) одну NP задачу к некоторой NP-полной совсем не проблема.

Поправьте если я не прав.
1. myxo
  06.01.2016 20:40
  #8727617
  Все правильно за одним исключением: данная модель, при решении задач, не симулирует МТ (приведенная теорема была для иллюстрации того, что она в принципе может это делать). Она решает задачи, скажем так, по-своему.
  
  В том и проблема равенства классов NP и P, что есть модели вычислений, которые решают NP полные задачи за полином (та же недетерминированная машина Тьюринга), но реализовать на практике мы ~~(пока что)~~ можем только обычную машину Тьюринга. Поэтому есть, вообще говоря два выхода из положения. Понять как решать быстро задачи на МТ, либо предложить хорошую модель, которую мы сможем построить в нашей реальности.

deniskreshikhin
06.01.2016 19:17
#8727525
+4
Я не очень понял теоретическую часть, но что касается сигнальной части — выскажу свое мнение по двум пунктам.

1. Т.к. рабочая частота у электронных устройств ограничена, то при увеличении количества элементов N будет сужаться полоса для фильтров. Но что бы узкополосный фильтр выдал свой отклик, требуется подождать некоторое время ~ 1/df, где df ширина полосы этого фильтра.
В итоге с ростом N физическая скорость вычисления на 1 мемустройство будет оставаться той же самой.

Фактически это решение имеет квадратичную сложность, а не линейную. Т.к. с ростом N нужно увеличивать как количество фильтров, так и вермя ожидания.

2. Вообще создание константного алгоритма для некоторого фиксированного N не является проблемой, всегда можно составить таблицу которая будет хранить заранее подготовленные значения. Проблема только в памяти, которой не бывает слишком много.
Такая же беда и здесь, как нельзя построить ПЗУ бесконечной памятью, так нельзя построить и электронное устройство с бесконечной рабочей частотой.

Пример подхода, когда константный алгоритм зашит в аппаратную часть всем известен это умножение в ЦПУ. Ведь умножение даже двоичных чисел произвольной длины требует минимум N*log(N) операций. Т.к. с точки зрения математики умножение и свертка это операции имеющие одну и ту же природу.

irriss
07.01.2016 08:30
#8728083
Похоже на продолжение идеи клеточных автоматов.

irriss
07.01.2016 08:30
#8728085
Похоже на продолжение идеи клеточных автоматов.

sophist
07.01.2016 13:21
#8728275
Интересно, а с мемристорами как элементной базой идея мемпроцессоров как-нибудь состыковывается?
1. myxo
  07.01.2016 14:41
  #8728321
  очень даже стыкуется. Мемристоры — естественные элементы для конструирования мемпроцессоров. Я об этом как-то не стал писать (хотел сконцентрироваться на другом), но в оригинальной статье приводятся, например, уравнения перехода, если делать мемпроцессор из мемэлементов.

lockywolf
08.01.2016 01:31
#8728735
Выглядит любопытно, но я несколько не понял:

«задачи из класса NP полных задач за полином времени и памяти.»

Полином по памяти — это очень плохо. NP \in PSPACE

Ну, и вторая проблема в том, что даже обычную машину тьюринга мы не можем сделать, потому что у неё по условию бесконечная лента, и это условие нельзя ослабить.

Правильно я понимаю, что у мемристорной машины для имитации бесконечной ленты требуется бесконечное число мемпроцессоров?
1. myxo
  08.01.2016 02:09
  #8728761
  я вас тоже не понял
  
  Полином по памяти — это очень плохо. NP \in PSPACE
  
  Чего плохого-то?
  
  По поводу бесконечной ленты да, нужно бесконечное кол-во мемпроцессоров.