問題タブ [turing-complete]

ウィキペディアで、任意の実数/有理数のフィールドで定義されたニューラルネットワーク関数（アルゴリズムスキーマ、および投機的な「トランス再帰」モデルとともに）は、現在使用しているコンピューターよりも計算能力が高いことを読みました。もちろん、それはロシアのウィキペディア（ru.wikipedia.org）のページであり、適切に証明されていない可能性がありますが、そのような噂の唯一の情報源ではありません。

さて、私が本当に理解していないのは、文字列書き換えマシン（NNはTuringマシンとまったく同じように文字列書き換えマシンであり、プログラミング言語のみが異なる）がユニバーサル機能のUマシンよりも強力である理由は何でしょうか。

はい、説明的な手段は実際には異なりますが、実際には、そのようなクラスの機能は（簡単かどうかにかかわらず）合法的なチューリングマシンに変えることができます。私が間違っている？重要なものが恋しいですか？

それを言う人の原因は何ですか？決定不可能性の現象が今日広く受け入れられていることは知っていますが（私が読んだ内容によれば一貫して証明されていませんが）、NNがその特定の問題を解決できる可能性はほとんどありません。

アドイン：Not consistently proven according to what I've read-90年代半ば以降のA. Zenkin（ロシアの数学者）の論文を見てみてください。彼は、超限集合、非可算集合、対角化など、G。Cantorの概念の誤りを説得力を持って仮定しています。方法（Turingによる決定不能性の証明に使用される方法）および多分他の方法。ゲーデルの不完全な定理でさえ、たった21世紀で正しい方法で証明されました。それは、Zenkinの仕事をポストにつなぐためだけのものです。なぜなら、その知識がCSコミュニティにどれほど広まっているのかわからないので、それがばかげているように見えたら許してください。

ありがとうございました！

これは、アプレットLogiCell 1.0のスクリーンショットであり、ここで見つけたリンクです。

左下隅に示されているように、これは合計を実行して0+1おり、結果は01b（右下）です。

表示されているものを入力と出力にリンクすることができません。たとえば、この場合-スナップショットを見て、入力が0と1であり、出力がであるとどのように判断します01か？

さまざまな評価戦略に関する記事を読んでいます（wikiで記事をリンクしましたが、英語ではない別の記事を読んでいます）。そしてそれは、戦略とは異なり、call-by-name戦略はチューリング完全ではないと言っています。call-by-needcall-by-value

誰か説明してもらえますか、なぜそうなのですか？可能であれば、plsの例を追加してください。

通常は組版言語と考えられている言語を使用して、興味深いことを行うことができます。たとえば、postscript を使用してマンデルブロ集合を作成できます。

このMathOverflowの質問では、LaTeXがチューリング完全である可能性があることが示唆されています。これは、任意のプログラムを作成できることを意味します (簡単ではないかもしれませんが!)。このような言語で非常に珍しいことを行う LaTeX のプログラムの具体的な例を知っている人はいますか?

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

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

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

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

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

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

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

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

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

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

Boost プリプロセッサの機能を発見した後、私は疑問に思いました: C99 プリプロセッサのチューリングは完全ですか?

そうでない場合、資格がないために何が欠けていますか?

最近、手続き型コードを SQL に変換する作業に興味を持っています。完全な手続き型言語ですべてを表現できるわけではないことはわかっています。

しかし、特別な目的の手続き型言語がある場合はどうなるでしょうか? たとえば、次のように変換します。

これに：

このようなものに名前はありますか？

また、私の疑似コードでは、それは不変であり、ANSI SQL への (簡単な) 変換が明らかにないrowようなことを行うことは不可能であると想定しています。Table[0].FirstName...

誰かこれに名前をつけてくれませんか?

最近、仕事で Makefile から別のビルド システムへの変換を行っています。いくつかの場所で、関数マップ、フィルター、および foreach 構成要素を使用するかなり毛むくじゃらの Make コードを見てきました。ビルド スクリプトはできるだけ宣言的であるべきだと思うので、これには驚きました。

とにかく、これは私に考えさせました: Makefile 言語 (具体的には最新の GNU make と言います) チューリングは完全ですか?

チューリング完全でない言語が世の中にあり、私が大学でComp Sciを勉強していなかったとすると、チューリング不完全言語（Coqなど）ではできないことを誰かが説明できますか？

それとも、実際の利害関係がない（つまり、実際にはあまり違いがない）完全性/不完全性ですか？

編集-私はあなたの線に沿って答えを探していますX、またはそのようなもののために非チューリング完全言語でハッシュテーブルを構築することはできません！

チューリングマシンとチューリング完全言語とは何かについて少し知っていますが、よりよく理解するために、誰かがチューリング完全ではない言語の例を挙げてもらえますか？（たぶん、チューリングではないマシンでも？）