問題タブ [computability]

Poly-time 関数を定義すると、最大多項式 (n) 時間 (n は入力のサイズ) でチューリング マシンによって計算できる関数です。これらの関数のクラスは再帰的に列挙可能ですか?

計算可能性と複雑性を扱うアプリケーションの開発を考えています。機能の最初のリストは次のとおりです。

1. 関数を受け取り、それが計算可能かどうか (つまり、R,RE,coRE に属しているかどうか) をチェックします。
2. 計算可能な関数を受け取り、それがどの複雑度クラスに属しているかを確認します。

そしてもう少し、これは多かれ少なかれ方向です。
このようなアプリケーションに精通していますか?
もしそうなら、このプログラムの機能は何ですか?どこで見つけることができますか?また、このプログラムに欠けている、またはうまく機能しない新しい機能について考えることはできますか?

この記事で、筆者は次のように主張しています。

...プログラムは、テンプレートのインスタンス化メカニズムが、コンパイル時に重要な計算を実行できるプリミティブな再帰言語であることを示しました。

原始再帰関数の理論を掘り下げる計算理論のクラスを教えるのを手伝っているので、これはかなり興味深いと思いました。しかし、テンプレート メタプログラミングはチューリング完全であるという印象を受けました。これは、原始的な再帰的であると言うよりも厳密に強いステートメントです...そして結局のところ、停止に失敗するテンプレート メタプログラムを作成することはそれほど難しくありません。 .

何か不足していますか？Template Metaprogramming は厳密にプリミティブな再帰言語ですか、それともより広い範囲のプログラムをカバーすると信じているのは正しいですか?

私は、Ken Thompson の古典的な論文Reflections on Trusting Trustを読みました。この論文では、彼の主張の導入としてユーザーにQuineを書くよう促しています (強くお勧めします)。

quine は、入力を受け取らず、独自のソース コードのコピーを唯一の出力として生成するコンピューター プログラムです。

素朴なアプローチは、単に言いたいことです：

しかし、これは不可能であることがすぐにわかります。Python を使用して自分で作成することになりましたが、「トリック」を説明するのにまだ問題があります。クワインが可能である理由の優れた説明を探しています。

便利なタスクを実行するプログラムがあります。ここで、元のタスクの実行に加えて、コンパイルされた実行可能ファイルの実行時にプレーンテキストのソース コードを生成したいと考えています。これはクワインではありませんが、おそらく関連しています。

この機能は一般的には便利ですが、私の特定のプログラムは Fortran 90 で書かれており、Mako テンプレートを使用しています。コンパイルすると、元のソース コード ファイルにアクセスできますが、ユーザーが実行可能ファイルを実行するときにソースが存在することを確認できるようにしたいと考えています。

これを達成することは可能ですか？

以下は、単純なタスクを実行する単純な Fortran 90 の例です。

このプログラムを変更して、同じタスクを実行し (コンパイル時に文字列を出力する)、ソースを含む Fortran 90 テキスト ファイルを出力することはできますか?

前もって感謝します

NPOの定義を理解しようとしています。

ここで定義を読みました：http://www.nada.kth.se/~viggo/wwwcompendium/node2.html

最小の頂点カバーを見つけようとすると、I、sol(x)、および m は何ですか? (目標は最小)

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

チューリングマシン M1、M2、M3 が存在し、それらが認識する言語はそれぞれ L(M1)、L(M2)、L(M3) であるとします。次の言語 L = {(M1, M2, M3) : L(M1), L(M2), L(M3) は等しくない} 言語は決定可能ですか? 再帰的に列挙可能？それともどちらでもない？

カントールの対角線を使用して、すべての1つの引数関数の集合を可算できないことを証明できます。例えば

すべての関数f1からfnに対して、すべての引数を渡すことができ、いくつかのnに対して1からnを渡すことができます。次に、対角値を取得し、対角値に1を追加すると、1つの引数関数をすべてカウントできないことを証明できます（対角値を変更すると、リストされていない一意の行が生成されるため）

2つの引数関数も数える特定の方法があるのだろうか??..

ありがとう..

たとえば、独自のエンコーディングを受け入れないチューリング マシンの言語は、どのチューリング マシンでも受け入れることができません。