問題タブ [turing-complete]

私の理解では、静的に型付けされた言語で書かれたプログラムに特定の（小さな）欠陥のサブセットがないことを正式に証明するプログラムを書くことができる可能性があるということです。

これに関する私の問題は次のとおりです。

AとBの2つのチューリング完全言語があると仮定します。Aは「タイプセーフ」であると推定され、「B」はそうではないと推定されます。Aで書かれたプログラムの正しさをチェックするためにプログラムLが与えられたとしましょう。Lを適用してBで書かれたプログラムをAに翻訳するのを防ぐにはどうすればよいですか。PがAからBに翻訳される場合、なぜPLaではないのですか。 Bで書かれたプログラムの有効な型チェッカー？

私は代数の訓練を受けており、CSの勉強を始めたばかりなので、これが機能しない明らかな理由があるかもしれませんが、私は非常に知りたいです。この「型安全性」全体は、しばらくの間私にとって魚臭いものでした。

したがって、言語が何らかの基準を満たしていれば、その言語はチューリング完全であると言うことができ、別のチューリング完全言語が実行できることは何でも実行できます。

理論的には、JavaScript またはBrainf_ckを使用して Google を実装できるということですか?

(通常のプログラミング言語とは対照的に) UML がチューリング完全でないことはよく知られている事実です。しかし、UML は従来の言語よりも柔軟性が高いように思えます。C++ (fe) のような言語で記述でき、同時に UML で記述できない問題を想像することはできません。それどころか、UML には存在するが C++ (Java、Delphi、VB など...) では信頼できない構造を想像する方がはるかに簡単です。本当に釣れない。

私はウェブを検索してきましたが、やや矛盾した答えを見つけています。一部の情報源は、条件付き分岐と無条件分岐の両方がある場合にのみ、言語/マシン/あなたが持っているものはチューリング完全であると主張します(これは一種の冗長だと思います)。必要とされている。

ドイツのZ3とENIACについて読むと、ウィキペディアは次のように述べています。

ドイツの Z3 (1941 年 5 月に稼働中) は、コンラート ツーゼによって設計されました。これは最初の汎用デジタル コンピューターでしたが、すべての機能にリレーを使用していたため、電子的ではなく電気機械的でした。バイナリ演算を使用して論理的に計算しました。パンチテープでプログラムできましたが、条件分岐がありませんでした。チューリング完全性のために設計されたわけではありませんが、1998 年に発見されたように、偶然にもそうでした (ただし、このチューリング完全性を利用するには、複雑で巧妙なハックが必要でした)。

正確には、どのような複雑で巧妙なハックですか?

R. Rojas による 1998 年の論文 Abstract にも次のように記載されています (この論文はまだ読んでいないことに注意してください。IEEE からの抜粋です)。

1938 年から 1941 年の間に Konrad Zuse によって構築されたコンピューティング マシン Z3 は、パンチ テープにコード化された浮動小数点算術演算 (加算、減算、乗算、除算、および平方根) の固定シーケンスのみを実行できました。コンピューティングの歴史の観点から興味深い質問は、これらの操作が普遍的な計算に十分かどうかということです。この論文は、実際に、これらの算術命令を含む単一のプログラム ループで、特定の有限サイズのテープを使用する任意のチューリング マシンをシミュレートできることを示しています。これは、条件付き分岐と間接アドレス指定を純粋に算術的にシミュレートすることによって行われます。したがって、Zuse の Z3 は、少なくとも原則として、制限されたアドレス空間を持つ今日のコンピューターと同じくらい普遍的です。

要するに、SOers の皆さん、チューリング完全性のために正確に必要とされるタイプの分岐は何ですか? goto無限のメモリを想定すると、またはjmp分岐構造のみ (ifまたは構造なし)を持つ言語は、jnzチューリング完全と見なすことができますか?

Scalaの型システムはチューリング完全であるという主張があります。私の質問は次のとおりです。

1. これの正式な証明はありますか？

2. Scala型システムでの単純な計算はどのようになりますか？

3. これはScala（言語）にとって何かメリットがありますか？これにより、チューリング完全型システムのない言語と比較して、Scalaは何らかの形でより「強力」になりますか？

これは一般的に言語と型システムに当てはまると思います。

私は最近、Stata でいくつかの統計作業を行っていますが、あまり楽しんでいません。

「適切な」プログラミング言語のようには感じません。特に、条件が満たされるまでループする方法はないと思います。

私の感覚は正しいのでしょうか、それとも Stata は本当にチューリング完全なのでしょうか?

チューリング完全性の観点から、単純なループはネストされたループと同じくらい強力ですか？

正規表現は、完全ではない言語の古典的な例としてしばしば指摘されます。たとえば、チューリング完全ではない言語を探すこのSOの質問に対する答えとして、「正規表現」が示されています。

ターニングの完全性の概念についての私の、おそらくある程度基本的な理解では、これは、「バランスの取れた」パターンをチェックするために正規表現を使用できないことを意味します。バランスの取れた意味には、終了文字と同じ数の開始文字があります。これを行うには、開始文字と終了文字を一致させるために、何らかの状態が必要になるためです。

ただし、正規表現の.NET実装では、バランスの取れたグループの概念が導入されています。この構成は、前のグループが一致したかどうかをさかのぼって確認できるように設計されています。これは、.NET正規表現が次のことを意味します。

次のようなパターンに一致する可能性があります。

これは、.NETの正規表現がチューリング完全であることを意味しますか？または、言語をチューリング完全にするために必要な、不足している他のものはありますか？

XまたはY がプログラミング言語である(またはそうでない)ことを示すために必要な基準または基本的な機能は何ですか?

私はいくつかの読書を行いました ( HTML はプログラミング言語と見なされますか?、チューリング完全、およびその他)、言語または構文がプログラミング言語と見なされるにはチューリング完全である必要があるという結論に達しました。これは正しいです？それは十分ですか？

また、何かがチューリング完全かどうかを判断するにはどうすればよいですか? 具体的な基準はありますか？

フロー制御構造 (条件ステートメントとループ) を持つことは、チューリングが完全であると見なすのに十分ですか?

私の息子は最近リトルビッグプラネット2をプレイしていますが、ゲームエディタでANDゲート、ORゲート、NOTゲートが許可されていることに気付きました...チューリングは完了しましたか？もしそうなら、誰かがそれらのプリミティブをより高いレベルの条件付きのようなものに変えることを学ぶための情報源を推薦できますか？