問題タブ [turing-complete]

Scala は System F ω に基づく型システムを使用しますが、これは通常強力に正規化されていると言われています。強く正規化するということは、非チューリング完全性を意味します。

それにもかかわらず、Scala の型システムはチューリング完全です。

正式なアルゴリズムやシステムと比較して、Scala の型システムをチューリング完全にする変更/追加/修正はどれですか?

ラムダ計算がチューリング完全であるという事実をどのように主張しますか（可能な限り最も簡単な方法で）？

英数字の x86 オペコードの最小限の、計算上普遍的なサブセットを作成しようとしています。最終的には、サブセットに含まれる命令をできるだけ少なくしたいと考えており、最小サブセットが複数ある場合は、それも知りたいと考えています。サブセットは、英数字命令のセット全体で作成できるプログラムをシミュレートできる必要があります。命令は、文字「AZ」、「az」、および「0-9」に対応する命令のみをカバーする必要があります。

これまでのところ、 、 、 、 、 で十分だと思いますpushがpop、incもっとdec小さいcmpセットjeがあると確信しています。私が生成したセットが、すべての英数字命令を使用して任意のプログラムをシミュレートできることを証明するにはどうすればよいでしょうか? そのようなセットが最小であることをどのように証明できますか? そのような命令サブセットが存在するかどうかは誰にもわかりませんか?

単純なロジック ソルバーのプログラミングに 1 ～ 2 週間を費やしました。それを構築した後、私はそれが解決する言語がチューリング完全であるかどうか疑問に思っていました。そこで、SKI コンビネーター計算で有効な式をすべて受け入れ、その式の正規形を含む結果セットを生成する小さな一連の方程式をコード化しました。SKIはチューリング完全であるため、私の言語が SKI を実行できることを証明することは、そのチューリング完全性を実証することになります。

ただし、不具合があります。ソルバーは通常の順序で式を縮約しません。実際に行うことは、考えられるすべての削減順序を試すことです。これは、ソリューション セットが通常巨大であることを意味します。正規形があればどこかにあるのですが、どこにあるのかわかりにくいです。

これは私に2つの質問をもたらします:

• 私の言語はチューリング完全ですか? それとも、より良い証拠を見つける必要がありますか?

• 解の数は入力の計算可能な関数ですか?

(最初は、解集合のサイズは入力サイズの指数または階乗であると想定していました。しかし、よく調べてみると、これは正しくありません。すでに正規形になっている巨大な式と、終了しない小さな式を書くことができます。解集合のサイズを決定することは、停止問題を解くことと同等かもしれないと感じていますが、完全にはわかりません...)

C++ テンプレートは turing-completeであり、CSS は turing-complete (!) であり、C# のオーバーロードの解決は(ジェネリックがなくても) NP 困難であるというよく知られた事実があります。

しかし、C# 4.0 (co/contravariance、generics など)のコンパイル時のチューリングは完了していますか?

ウィキペディアの記事やここでの回答が何を言っているのか、頭を悩ませることはできません。だれかルール 110 を簡単に説明できますか? チューリングの完全性をどのように保証しますか?

Wolframは「知識ベースのプログラミング言語」をリリースしようとしていますが、C#やJavaなどと同じように本当にプログラミング言語なのでしょうか?

これが主観的になりすぎるのを避けるために、「真のプログラミング言語」とはつまり、チューリングが完全であるかどうかを明確にします。