56

リカレントニューラルネットのチューリング完全性に関するいくつかの論文（例：ニューラルネットを使用したチューリング計算可能性、HavaT.SiegelmannおよびEduardoD.Sontag、1991）を読んでいると、そこで与えられた証明は実際にはそうではないと感じました。実用的。たとえば、参照されている論文には、ニューロンの活動が無限に正確でなければならないニューラルネットワークが必要です（有理数を確実に表すため）。他の証明には、無限のサイズのニューラルネットワークが必要です。明らかに、それは実際にはそれほど実用的ではありません。

しかし、私は今、チューリング完全性を求めることがまったく意味があるのか​​どうか疑問に思い始めました。厳密な定義によれば、今日のチューリング完全なコンピューターシステムはありません。これは、無限のテープをシミュレートできるコンピューターシステムがないためです。

興味深いことに、プログラミング言語の仕様は、チューリング完全であるかどうかにかかわらず、ほとんどの場合オープンのままです。結局のところ、彼らが常により多くのメモリを割り当てることができるかどうか、そして関数呼び出しのスタックサイズが無限であるかどうかという問題に要約されます。ほとんどの仕様は実際にはこれを指定していません。もちろん、ここでは利用可能なすべての実装が制限されているため、プログラミング言語のすべての実用的な実装はチューリング完全ではありません。

つまり、すべてのコンピューターシステムは、有限状態マシンと同じくらい強力であり、それ以上ではないということです。

そして、それは私に質問をもたらします：チューリングという用語は完全にどれほど有用ですか？

そしてニューラルネットに戻る：ニューラルネット（私たち自身の脳を含む）の実際の実装では、無限の数の状態を表すことはできません。つまり、チューリング完全性の厳密な定義によって、チューリング完全ではありません。では、ニューラルネットがチューリング完全であるかどうかという質問はまったく意味がありますか？

それらが有限状態マシンと同じくらい強力であるかどうかという質問は、すでにずっと以前に回答されており（1954年、ミンスキーによる回答、もちろん：はい）、回答も簡単なようです。つまり、少なくとも理論的には、それはすでに他のコンピュータと同じくらい強力であるという証拠でした。

私が本当に知りたいことについてのいくつかの他の質問：

  • コンピュータの計算能力についてより具体的なことを言うことができる理論用語はありますか？（限られたメモリスペースを考えると）

  • ニューラルネットの実際の実装の計算能力をコンピューターとどのように比較できますか？（チューリング完全性は、上記で論じたように有用ではありません。）

4

11 に答える 11

53

数学モデルがチューリング完全であると述べることのポイントは、モデルの特定の実装にそれらのリソースがあるかどうかを示すのではなく、十分な量のリソース（つまり無限）が与えられた場合に、任意の計算を実行するモデルの機能を明らかにすることです。非チューリング完全モデルは、十分なリソースがある場合でも、特定の一連の計算を処理できません。これは、リソースが限られている場合でも、2つのモデルの動作方法の違いを明らかにします。もちろん、このプロパティを証明するには、モデルが無限の量のリソースを使用できると想定する必要がありますが、モデルのこのプロパティは、リソースが限られている場合でも関連性があります。

于 2010-06-07T14:49:28.677 に答える
14

現代のコンピューターがチューリング完全であると言われるとき、説明されている無限のストレージデバイスチューリングには暗黙の例外があります。これは明らかに有限の物理計算デバイスでは不可能です。計算デバイスがチューリングマシンが実行できるすべてのことを実行できる場合（無限のストレージに耐えられない）、すべての実用的な目的と目的に対してチューリング完全です。チューリング完全性のこのそれほど厳密ではない定義によって、はい、多くのニューラルネットワークがチューリング完全である可能性があります。

もちろん、チューリング完全ではないものを作成することは可能です。

于 2010-06-07T14:40:51.083 に答える
13

チューリング-リカレントニューラルネットワークの完全性とは、次のことを意味します。（有限状態ヘッドと無限テープを備えた）すべてのチューリングマシンの（有限）遷移表は、有限リカレントニューラルネットワーク（有限数のニューロンと有限数のニューロン）によってモデル化できます。状態、特に2つの状態のみ）。遷移表は、次の3つの機能を定義します。

  • next-state（current-state、current-symbol）

  • next-symbol（current-state、current-symbol）

  • 方向（現在の状態、現在の記号）

これは、リカレントニューラルネットワークがこのタスクを実行する方法です（非常に生のスケッチです）。

ここに画像の説明を入力してください

緑のニューロンは現在のセルのシンボルを読み取り（バイナリ表現で）、灰色のニューロン（最初はミュート）は現在の状態を決定し、赤のニューロンは新しいシンボルを現在のセルに書き込み、黄色のニューロンは左に行くか右に行くかを決定します。青いニューロンは内側のニューロンです（最初はミュート）。

主張は、すべてのチューリングマシンにそのようなリカレントニューラルネットワークがあるということです。

与えられた遷移表からそのようなネットワークを構築する体系的な方法があるのだろうか。

于 2015-03-04T10:30:17.157 に答える
12

通常のフィードフォワードニューラルネットワークは完全ではありません。これらは、事実上、非常に多くの計算を実行する可能性があるが、ループやその他の制御フロー操作を実行する機能を持たない単一の複雑な数学関数と同等です。

ただし、ステートフル環境にアクセスするための何らかの方法でニューラルネットワークを接続すると、チューリング完全なマシンにすることができます。

最も簡単な例として、次のようなクラシックスタイルのチューリングマシンを再現できます。

  • ニューラルネットワークへの入力は、テープ上の値と前の状態です
  • ニューラルネットワークの出力は次の状態とアクションです

次に、ニューラルネットワークをトレーニングして、任意のチューリングマシンの状態テーブル/構成のアクションをエミュレートできます（おそらく、別のチューリングマシンのアクションに関する教師あり学習によって？）

注：何らかの形式の状態フィードバックを使用してフィードフォワードネットを繰り返し実行するという考え方は、基本的にリカレントニューラルネットワークと同等です。したがって、リカレントニューラルネットワークとそれを繰り返し実行するロジックは、チューリング完全であると考えることができます。チューリング完全性を確保するには、終了、繰り返し、IOなどを処理する必要があるため、（ネットワーク自体に加えて）追加のロジックが必要です。

于 2014-01-06T12:55:37.960 に答える
10

2番目の質問に部分的に対処するには：

ニューラルネットワークには、普遍近似器であるという特性があります。つまり、任意の関数を任意の精度で近似できます。ニューラルネットワークが無限である必要がないようにするのは、「精度の程度」の部分です。

于 2010-06-07T14:47:54.620 に答える
10

何年も経って、この質問に自分で答えさせてください。

チューリング完全性

  • チューリングマシン（TM）と同じくらい強力です。
  • 無限のメモリが必要です。つまり、実際には、物理​​的なデバイスでチューリング完全になることはできません。
  • 通常のパーソナルコンピュータ（PC）を考えてみましょう：
    • 特定の物理インスタンスは有限のメモリを持っているため、チューリング完全ではありません。
    • ただし、PCの概念は、オンデマンドでメモリを追加できるものと考えてください。メモリを追加しても、すべてのプログラムは同じように機能します。任意の入力、および任意のプログラムに対して、それが機能するように最大量のメモリがあります。（メモリアドレスの制限などについては、今は衒学者ではありません。これらは技術的な制限であり、たとえば大きなintなどによって解決できます。）したがって、PCの概念はチューリング完全int64であると言えます。
  • チューリング完全性は、実際には主にメモリの概念に関するものです。有限状態マシン/オートマトン（FSA）、および外部メモリへのアクセスを検討してください。メモリのタイプに応じて、チョムスキー階層のさまざまなクラスになります。

リカレントニューラルネットワーク（RNN）

ニューラルネットの計算能力について

よく引用される論文は、ニューラルネットの計算能力について、Siegelmann＆Sonntag、1992年で、RNNはチューリング完全であると述べています。このペーパーでは、分母/分母に制限のない有理数があることを前提としています。つまり、無限メモリは有理数、または無限精度の浮動小数点数としてエンコードされます。こちらもご覧ください。通常、有理数（無制限）で動作する方法でNNをモデル化することはありません。有限の精度の重みとアクティベーションを持つ（R）NNに制限すると、論文の証明は適切になり、適用されなくなります。したがって、この論文はそれほど関連性がありません。

より最近の論文、言語認識のための有限精度RNNの実用的な計算能力について、Weiss et al、2018があり、これは正確にこれに対処しています。

普遍近似定理

ほとんどの標準NNが普遍近似定理であることはよく知られています。これは、任意の関数（非定数、有界、連続）が与えられ、許可されたしきい値が与えられた場合、許可されたしきい値内でこの関数を近似するNNを作成できることを示しています。これは有限次元のベクトル空間についてです。計算可能性について話すとき、シーケンスについて話すので、無限の次元のベクトル空間があります。したがって、このプロパティはそれほど関連性がありません。

外部メモリなし

したがって、明示的に述べると、外部メモリがないと、標準のRNN、およびLSTMはチューリング完全ではありません。また、必要に応じてメモリを追加できるRNNの概念を定義する簡単な方法もありません。RNNのメモリは、最新の非表示のアクティベーションです。メモリを追加するとは、NNを変更することを意味します。つまり、新しいニューロンを追加して、その内部動作を追加します。これは、プログラム自体を変更するようなものです。

外部メモリ付き

ニューラルチューリングマシン（NTM）と、ある種の外部メモリを備えたいくつかの同様のモデルがあります。ここでは、オンデマンドでメモリを追加するNTMの概念について考えるのは簡単です。したがって、NTMの概念はチューリング完全であると言えます。

頭の中で使用される注意のタイプのようないくつかの詳細があり、それはいくつかの適応が必要です。モデルのフォローアップがあります。これは、これに明示的に対処し、メモリを追加するための明示的なメカニズムも備えた微分可能ニューラルコンピューター（DNC）です。

学習/トレーニング

私たちは主に理論的な計算能力について話しました。非常に異なる問題は、NNがそのような機能を学習できるかどうかです。つまり、トレーニング（勾配探索）が計算可能関数を学習したNNにつながるかどうか。

人間の脳

人間の脳（または任意の脳）を一種の複雑なニューラルネットワークとして解釈する場合があります。人間の脳（モデル）がチューリング完全であるかどうかという質問もできます。たとえば、ここを参照してください。この質問は難しい質問です。直感的には、あらゆる種類の計算を実行できると言えます。したがって、人間の脳はチューリング完全です。ただし、ここで概説した議論は、RNNがチューリング完全ではないことを示しています。ここでも重要なのはメモリー効果です。ある時点で、人間の脳の記憶容量は、ある入力を操作するのに十分ではありません。したがって、外部メモリが必要になります。したがって、人間の脳と外部メモリは、明らかにチューリング完全です。

ただし、人間の脳の記憶には、標準のRNNとは少し異なる側面があります。それは高度に一般化でき、特定のアクティベーションにアクセスするためのアドレス指定メカニズムが異なります。また、ある種の適応重みがあります（ただし、有限の情報しか格納できません）。

于 2018-10-27T14:02:59.323 に答える
7

チューリング完全性の概念は、特定のコンピューターが特定のタスクを実行できるかどうかを示すことを意図したものではないと思います。

むしろ、特定の言語が特定のタスクを表現できるかどうかを判断することを目的としています。つまり、それは実際にはそれを実行しないアルゴリズムを表現することだと思います。

ニューラルネットワークには言語がないため、ニューラルネットワークの機能ではなく、ニューラルネットワークの観点からアルゴリズムを表現することが問題になります。だから私はあなたの質問の最後のビットへの答えを知りません！

于 2010-06-07T14:55:05.293 に答える
4

チューリングマシンの重要なポイントは、与えられた入力とプログラムに対して、マシンがしばらく停止すると仮定すると、マシンは有限量のテープしか必要としないということだと思います。そのため、「チューリング完全」という用語が役立ちます。特定の入力で1つの特定のチューリング完全プログラムを実行するために必要なのは有限のメモリだけです（プログラムが停止した場合）。ただし、チューリング完全ではないマシン/言語/テクノロジーを使用している場合は、追加するメモリの量に関係なく、特定のアルゴリズムをシミュレートできません。

于 2010-06-07T15:27:15.990 に答える
3

ほとんどの場合、システムがチョムスキー階層のどのクラスであるかを知っておくと便利です。これは、正規言語/有限オートマトンと文脈自由言語など、より制限されたクラスで特に重要です。また、解決しようとしている問題がどのクラスにあるかを認識するスキルも重要です。そうしないと、正規表現のみを使用してHTMLやXMLを解析するなど、ばかげたことをしようとする可能性があります。これは不可能です。

あなたの形式主義またはシステムが完全にチューリングしているという知識を持っていることは、あなたがそれであなたが望むものを何でも構築することができるという声明を出します。それは実用性については何も述べておらず、問題を解決する可能性または不可能性についてのみ述べています。チューリング陥穷を考えるとき、これは痛々しいほど真実ですが、生産現場での汎用作業に誰も使用することを夢見ることのない、ニッチな目的のために特別に作られたチューリング完全システムもたくさんあります。

つまり、チョムスキー階層に関する十分な知識は、適切なタイプのパーサーを選択するだけでなく、非常に多くの状況で役立ちます。正規表現、プッシュダウン、CFG、またはより強力ですが、一般的なプロセスを表現するための適切なタイプのマシンまたは形式を選択するためにも使用できます。

于 2010-06-07T14:53:08.680 に答える
-1

基本的には、チューリング完全なプログラミング言語またはアーキテクチャを
使用すると、さまざまなアルゴリズムを実行できることを意味します。

非Turing言語は、潜在的に非常にタイトです。

于 2010-06-07T14:27:01.193 に答える
-2

答えはとても簡単です。NORまたはNANDゲートをエミュレートできる場合、残りは物事を組み合わせるだけの問題であると仮定すると、チューリング完全です。

于 2015-11-27T23:14:15.967 に答える