この記事は、この記事の無料翻訳（とはいえ、それを理解しようとする試み）と考えることができます。 そして、はい、それは幅広い聴衆よりも数学者向けに書かれました。

小さなネタバレ：最初は、ある種の魔法のように思えましたが、キャッチに気づきました...

今日、チューリングマシン（以下MT）は、アルゴリズムの概念の普遍的な定義であり、したがって「問題ソルバー」の普遍的な定義です。アルゴリズムには他にも多くのモデルがあります-ラムダ計算、マルコフアルゴリズムなどがありますが、それらはすべて数学的にMTと同等であるため、興味深いものの、理論世界では何も変わりません。

一般的に言えば、他のモデルがあります-非決定的チューリングマシン、量子チューリングマシン。ただし、それらは（これまで）実際には実装されていない抽象的なモデルにすぎません。

6か月前、Science Advancesは、MTとは大幅に異なる計算モデルを使用した興味深い記事を公開しました。この記事は、実際のハードウェアでSSPタスクを計算する方法についての記事でした。

はい。このモデルで最も興味深いのは、著者によると、NP時間クラスの完全な問題の多項式時間とメモリで（一部の）問題を解決できることです。

おそらく、この結果は問題を解決することを意味するものではないことをすぐに言及する価値があります $P = NP$ 。結局のところ、この問題の声明は「問題を解決しない」 $NPcompleteの\$ のために $n ^ {定数}$ そして、時間の多項式に対して通常のチューリングマシン上で非決定性チューリングマシンをシミュレートすることが可能です。これはまったく異なる計算モデルであるため、古典的な複雑度クラスについては言えません。

私自身は、このマシンを鉄で構築する可能性については現在懐疑的ですが（以下で説明します）、モデル自体は解析するのに十分興味深いものであり、おそらく他の科学分野にも応用できるでしょう。

小さな紹介

今日のコンピューター（より正確には、MTの最も一般的な実装であるVon Neumann）とは何ですか？何らかの種類の入出力インターフェイス、メモリ、およびCPU。これらは物理的に分離されています。 CPUには、計算の過程を制御するモジュールと、これらの計算を実行するブロックの両方があります。

CPUの物理的な分離は、データの転送に多くの時間を費やす必要があることを意味します。実際、このために、さまざまなレベルのキャッシュメモリが発明されました。ただし、キャッシュメモリはもちろん、生活を楽にしますが、データ転送のすべての問題を解決するわけではありません。

提案されたデータモデルは、脳の働きに触発されました（このフレーズはかなりボロボロですが、ここに収まります）。その本質は、データを転送する必要がある別のデバイスではなく、直接メモリで計算が行われることです。計算順序は、外部デバイス（コントロールユニット）によって制御されます。

Universal Memcomputing Machinesと呼ばれるこのコンピューティングモデル（この用語は翻訳していません。さらに、略語UMMを使用します）。

この記事では、まずMTが正式に定義されている方法を思い出してから、UMMの定義を見て、UMMの問題を解決するためのアルゴリズムを設定する方法の例を見て、最も重要な情報オーバーヘッドを含むいくつかのプロパティを検討します。

モデルの正式な説明。

ユニバーサルチューリングマシン（UTM）

チューリングマシンとは何かを覚えていると思います（そうでない場合、この記事を読むのは意味がありません）。テープ、キャリッジ、すべてのもの。正式にどのように定義されているかを覚えておきましょう。

チューリングマシンはタプルです

$UTM =（Q、\ガンマ、b、\シグマ、\デルタ、q_0、F）、$

どこで $Q$ -多くの可能な条件、

$\ガンマ$ -多くの可能なリボン文字

$b \ in \ガンマ$ -空の文字

$\シグマ$ -多くの着信キャラクター

$q_0$ -初期状態

$F \サブセットeq Q$ -多くの最終状態

$\デルタ：Q \ smallsetminus F \回\ガンマ\右矢印Q \回\ガンマ\回\ {L、N、R \}$ どこで $L、N、R$ したがって、シフトなしで左にシフトし、右にシフトします。それは $\デルタ$ -変換テーブル。

Memprocessor。

まず、メモリセルUMM-memprocessorを定義しましょう。

memprocessorは4タプルとして定義されます $（x、y、z、\ sigma）$ どこで $x$ -memprocessorの状態、 $y$ 内部変数のベクトルです。 $z$ -「外部」変数のベクトル、つまり、異なるmemprocessorを接続する変数。言い換えれば、 $z_1$ そして $z_2$ 2つのmemprocessorsの外部変数のベクトルであり、2つのmemprocessorsが接続されている $\左向き矢印$ $z_1 \ cap z_2 \ neq \ O$ 。また、memprocessorが誰にも接続されていない場合、 $z = z（x、y）$ 、つまり、内部状態によってのみ決定されます。

そして最後に $\シグマ[x、y、z] =（x '、y'）$ それは $\シグマ$ -新しい状態の演算子。

memprocessorは、私たちが頭の中で想像するようなプロセッサではないことを思い出してほしい。むしろ、新しい状態（プログラム可能）を取得する機能を持つメモリセルです。

Universal Memcomputing Machine（UMM）

ここで、UMMの正式な定義を紹介します。 UMMは、接続されたmemprocessor（一般的に言えば、デジタルまたはアナログのいずれか）から形成されたコンピューティングマシンのモデルです。

$UMM =（M、\ Delta、\ mathcal {P}、S、\ Sigma、p_0、s_0、F）、$

どこで $M$ -memprocessorの多くの可能な状態

$\ mathcal {P}$ -memprocessorsへの多くのポインタ（で使用 $\デルタ$ 目的のプロセッサを選択するには）

$S$ -多くのインデックス $\アルファ$ （使用した機能の数 $\デルタ$ ）

$\シグマ$ -memprocessorsの初期状態

$p_0$ -ポインターの初期セット

$s_0$ -演算子の初期インデックス（$ \ alpha $）

$F \サブセットeq M$ -多くの最終状態

$\ Delta = \ {\ delta _ {\ alpha} \ | \ \ delta _ {\ alpha}：M ^ {m _ {\ alpha}} \ smallsetminus F \ times \ mathcal {P} \右矢印M ^ {{m '} _ {\ alpha}} \ times \ mathcal {P} ^ 2 \回S \}、$

どこで $m _ {\ alpha}＆lt; \ infty$ -関数によって入力として使用されるmemprocessorsの数 $\デルタ_ {\ alpha}$ 、 ${m '} _ {\ alpha}＆lt; \ infty$ -出力関数として使用されるmemprocessorsの数 $\デルタ_ {\ alpha}$ 。

ご想像のとおり、チューリングマシンとの類推により、 $\デルタ_ {\ alpha}$ -遷移関数、状態テーブルの類似物。例を見たら、みましょう $p _ {\ alpha}、{p '} _ {\ alpha}、p _ {\ beta} \ in \ mathcal {P}$ -memprocessorsへのポインター、 $p _ {\ alpha} = \ {i_1、\ドット、i_ {m _ {\ alpha}} \}$ 、 $x（p）$ memprocessorsのデータの状態ベクトルであり、 $Sの\ベータ\$ 次のコマンドのインデックスです

$\ delta _ {\ alpha} [x（p _ {\ alpha}）] =（x '（{p'} _ {\ alpha}）、\ beta、p _ {\ beta}）$

一般的に言えば、UMMとMTの主な違いは、フォーマリズムを破棄することです。UMMでは、1つのメモリセル（つまり、memprocessor）に影響を与え、コントロールユニットからの追加呼び出しなしで自動的に環境に影響を与えます。

UMMの定義から直接わかる2つのプロパティに注意してください。

プロパティ1.本質的な並列処理 （この用語を正しく翻訳する方法をまだ決めていませんので、そのままにしておきます）。任意の機能 $\デルタ_ {\ alpha}$ 任意のプロセッサのセットで同時に実行できます。このためのチューリングマシンでは、追加のテープとヘッドを入力する必要があります。
プロパティ2.機能的多型 。チューリングマシンとは異なり、UMMは多くの異なる演算子を持つことができるという事実にあります $\デルタ_ {\ alpha}$ 。

一般的に言って、チューリングマシンを修正してこれらの特性も持たせることはそれほど難しくありませんが、著者は主張しています。

そして、定義によりさらにいくつかのコメント。 UMMは、チューリングマシンとは異なり、有限数のmemprocessorを持つ無限状態空間を持つことができます（それらはアナログである可能性があるため）。

ところで、UMMはニューラルネットワークの一般化と考えることができます。

1つの定理を証明しましょう。

UMMはユニバーサルマシン（つまり、MTの動作をシミュレートできるマシン）です。

証明。

つまり、チューリングマシンがUMMの特殊なケースであることを示す必要があります。（反対が真実かどうか-証明されていない、そして記事の著者が正しい場合、これは証明と同等になります $P = NP$ ）

UMMの定義で、 $M = Q \カップ\ガンマ$ 。私たちが示すmemprocessorsの1つ $j_s$ 、残り（おそらく無限数）として $j$ 。次に、ポインターを定義します $p = \ {j_s、j \}$ 。 $j_s$ 状態のシンボルとして使用します $q \にQ$ 、 $j$ リボン記号（ $\ガンマ$ ）

$\デルタ$ 単一の関数で構成されます $\ delta [x（p）] =（x '（p）、p'）$ （省略） $\ベータ$ 、1つの関数しかないため）。新しい状態 $x '$ 遷移表MTによって決定されます。 $x '（j_s）$ -新しい状態があります。 $x '（j）$ -新しいリボンシンボル。新しいポインター $p '= \ {j_s、j' \}$ 、 $j '= j$ キャリッジの移行がない場合、 $j '= j + 1$ キャリッジが右に移動した場合、 $j '= j-1$ 残っている場合。その結果、録音するとき $x$ 初期状態 $q_0$ および開始文字 $\シグマ$ と $\デルタ= \デルタ$ UTMはユニバーサルチューリングマシンをシミュレートします。

定理は証明されています。

アルゴリズム

UMMの問題を解決する方法の例を見てみましょう（現時点では、モデルに慣れるためだけです）。サブセット合計問題（SSP ）を取ります。

たくさんあります $G \ in \ mathds {Z}$ そして番号が与えられます $s$ 。サブセットはありますか $K \サブセットeq G$ 要素の合計が等しい $s$ 。

指数アルゴリズム

UMMでは、memprocessorsがマトリックス形式で配置されていると仮定します（図を参照）。 3つの操作を定義します。

$\チー$ -これは直接計算です。アクティベーションラインを使用して、計算が実行される行と境界列を選択できます。計算の本質は、左端のセルの値を行全体に追加することです。
$\ mu$ データを移動する操作です。制御ノードは2つの列を選択し、最初の列の値が2番目の列にコピーされます。制御ノードは必ずしもコピー操作自体を実行するわけではなく、単に必要な行で列をアクティブにします。
$p$ -同様の操作 $\ mu$ 、彼女だけが1つの値を取り、それを列に書き込みます。

これら3つの操作を組み合わせて、遷移関数を取得できます $\ delta = \ mu \ circ \ chi \ circ p$ 。

アルゴリズムの最初のステップで、長さのすべてのサブセットの合計を取得します $n-1$ サブセットの2番目のステップ $n-2$ などなど。正しい番号が見つかったら（左の列に表示されます）、答えが見つかりました。各ステップは1回の関数呼び出しで実行されます。 $\デルタ$ したがって、アルゴリズムは機能します $n-1$ ステップ。

次に、これらの操作を実行するために必要なmemprocessorの数を計算します。繰り返しkでは、 $\ binom {n-1} {k-1}（n + 2-k）$ memprocessors。スターリング公式によるこの式の推定は $（n / 2 \ pi）^ {1/2} 2 ^ {n-1}$ 。ノードの数は指数関数的に増加しています。

今では、これがどんな種類のオブジェクトであるかが多かれ少なかれ明らかになったと思います。次に、UMMが提供する最もおいしいもの、つまり3番目のプロパティである情報オーバーヘッドに進みましょう。

指数情報のオーバーヘッド

n個のmemprocessorがあるとします。選択したmemprocessorの状態を次のように示します。 $x（p）=（x（j_1）、\ドット、x（j_n））$ 。個々のmemprocessorの状態 $x（j）= u_j$ 内部変数に含まれる $M_aのu_j \$ 。 $u_j$ -ベクトル。また、各memprocessorについて、外部変数を「in」と「out」の2つのグループに分けます（1つのmemprocessorのoutは別のmemprocessorに接続されています）。写真は空の円-コンポーネントを示しています $（u_j）_h = 0$ 。また、目的のmemprocessorに接続され、すぐに読み取れるデバイスがあるとします $u_j$ 。

複数のmemprocessorに接続されたこのデバイスは、両方のステータスを読み取ることができます。つまり、グローバルステータスは、 $u_ {j_1、j_2} = u_ {j_1} \ダイヤモンドu_ {j_2}$ どこで $\ダイアモンド：R ^ d \回R ^ d \右矢印R ^ d$ -可換、連想操作、 $d = \ dim（u_j）$ 。この操作は次のように定義されます

$（u_ {j_1} \ダイヤモンドu_ {j_2}）_ {h \ star k} =（u_ {j_1}）_ h \ ast（u_ {j_2}）_ k、$

どこで $\スター：\ mathds {Z} \ times \ mathds {Z} \ rightarrow \ mathds {Z}$ そして $\ ast：R \回R \右矢印R$ -との可換および連想演算 $h \ star 0 = h$ そして $x \ ast 0 = 0$ 。また、 $h、k、h '、k'$ 行った $h \ star k = h '\ star k'$ それから

$（u_ {j_1} \ダイヤモンド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 \回R \右矢印R$ -交換可能な連想操作 $x \ oplus 0 = x$ 。

今たくさん持っている $G = \ {a_1、\ドット、a_n \}$ 整数、メッセージを定義 $m =（a _ {\ sigma_1} \ star \ dots \ star a _ {\ sigma_k}）\ cup（a _ {\ sigma_1}、\ dots、a _ {\ sigma_k}）$ どこで $（\ sigma_1、\ドット、\ sigma_k）$ -あらゆる種類のサブセットから取得したインデックス $\ {1、\ドット、n \}$ 。たくさんの投稿 $M$ から成る $\ sum_ {j = 0} ^ m \ binom {n} {j} = 2 ^ n$ 同様に可能性のあるメッセージ $m$ 、シャノンに関する情報量は $I（m）=-\ log_2（2 ^ {-n}）= n$

ここで、n個のmemprocessorを使用して、ゼロ以外のコンポーネントを公開します $u_ {j_0}、u_ {j_h}$ どこで $h \ in \ {1、\ドット、n \}$ 。すべての要素をエンコードしました $G$ memprocessorsで。一方、必要なmemprocessorに接続し、それらのグローバル状態を読み取ることで（式に従って、要素の合計が取得されます）、可能な状態mを考慮することができます。言い換えると、n個のmemprocessorsが（必要に応じて情報を圧縮して）エンコードできます。 $2 ^ n$ メッセージを同時に。

指数情報オーバーヘッドを使用したSSPソリューションアルゴリズム

ここで、私はこのアルゴリズムの詳細を理解できなかったと言わざるを得ません（私は電気工学と信号処理がそれほど得意ではなかったことがわかり、著者はそのような無知のためにすべてを塗りつぶさないことにしたようです）が、一般的な考えは。

開始するために、彼らは関数を見ることを提案します

$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}＆lt; n \ max \ {| a_j | \}$ -可能な最大頻度の評価。記事では、著者は追加の変数を導入しました $p$ 比例している $N$ そしてそれを通して漸近性を考慮しました。

したがって、 FFTを使用して、次の問題を解決できます。 $O（p \ log（p））$ 。ここで、バックパック問題（およびSSPはバックパック問題の特殊なケース）と同様に、$ p $は指数関数的に増加することに注意する必要があります。 Goertzelのアルゴリズムもタスクに使用できます。これにより、 $O（n p）$ 。著者によって提案された方法では、あなたが取り除くことができます $p$ 漸近では、線形時間を提供します。

さて、あなた自身の言葉で（より詳細な議論については、元の記事を参照してください）、彼らはこれをどのように達成しましたか。

取る $n$ アナログmemprocessors、その内部値はからのいくつかの値になります $G$ 。オペレーターとして $\スター$ そして $\ ast$ それぞれ、加算と乗算が行われます。

しかし、これは私たちのモデルです。鉄では、各memprocessorは独自の周波数（の数に対応する信号発生器）であることがわかります $G$ ）、memprocessorsの一般的な状態は、単にシグナルの追加です。これらのmemprocessorsは関数をシミュレートすることがわかります $g$ 。

さて、今、結果を読み取るために、信号に特定の周波数があるかどうかを確認する必要があります。 FFTを実装する代わりに、彼らは与えられた周波数のみを通過させる鉄片を作りました（ここでは私も方法をよく理解していませんでしたが、エレクトロニクスの私の知識は責任がある）。

合計時間漸近 $O（1）$ 、memprocessorsの漸近的な動作は $O（n）$ 。発射しましょうか？急がないでください。

いくつかのモデルの問題

実際、著者はタスクの「困難な」部分を巧みにシフトしました。これにより、出展者はソフトウェアから技術に移行しました。以前の記事では、それについてまったく言葉がありませんが、7月の記事では、数行でそれを認めています。

シグナルのコーディングがすべてです（ここで明確な説明を見つけました）。アナログ信号をエンコードし、個別の信号発生器を使用するという事実により、信号レベルの決定には指数関数的な精度が必要になります（所望の周波数を分離する鉄片で）。これには指数関数的な時間が必要になる場合があります。

著者は、この迷惑は、離散信号発生器の代わりにアナログを使用することで回避できると主張しています。しかし、私はあなたがすべてのためにアナログ回路を使用できるという大きな疑問を持っています $n$ 同時に、ノイズにdrれないようにしました（かつて彼らはアナログコンピューターを捨て、デジタルコンピューターを使い始めたのは彼らのためでした）。

まとめ

奇跡的な魔法は起こりませんでした。 NP完全問題の計算は依然として困難です。では、なぜこれをすべて書いたのですか？主に、物理的な実装が複雑であるにもかかわらず、モデル自体が非常に興味深いと思われるため、それらの研究が必要です。すぐに（まだではないにしても）同様のモデルが多くの科学分野で非常に重要になります。

たとえば、前述したように、ニューラルネットワークはUMMの特殊なケースです。わずかに異なるマットを使用して、反対側からそれらを見ると、ニューラルネットワークについてもう少し学ぶ可能性があります。装置。

チューリングマシンの代替としての汎用Memcomputingマシン