問題タブ [decidable]

私の問題: 単語の 2 つのセット P と Q (つまり、2 つの問題) を次のように定義します。

K-Complexity がリダクションを使用して解決できないことの証明を教えてください。

例えば：

PCP(2) <= PCP(3)

PCP(3) が解けないことは、PCP(2) に還元することで証明できます (すべてのインスタンスをマッピングすることにより)。

K-Complexity を別の既知の決定不能な問題 (停止問題など) に減らす方法がわかりません。つまり、X <= K-Complexity

その証拠を教えてください。少なくともアイデアを提供してください ( X )。

前もって感謝します

私は読んでいて、ツルーイングマシンに関する削減を理解しようとしています. これは私がそれをどのように理解しているかです: それは問題 A を問題 C に還元することを意味します。例を見てみましょう：

言語 L が与えられた場合:

リダクションを使用して証明する方法Atm < L.

私の解決策：

M は、任意の文字列を受け入れ、その文字列で停止するチューリング マシンです。D は DFA hast で、言語 L とそれに相当する TM M を受け入れます。 Atm は TM であり、文字列wを受け入れる M です。

という直接還元を使ってどのように証明できますか?Atm < L??

初めての投稿です、間違っていたらすみません。

Coq では、Stream のような帰納的型には決定可能な等価性がないのではないかと思います。つまり、2 つのストリーム s と t が与えられた場合、s=t か ~(s=t) かを識別することはできません。これは、Coq のすべての導帰型に当てはまると思います。

スタック交換による簡単なグーグル検索と検索では、確認は得られません。誰かがこれを確認したり、私を修正したりできますか?

言語の長さが 2 で割られることを簡約法を使用して証明するにはどうすればよいですか? L={ | は |L(M)|= 0 mod 2 のチューリング マシンです}

私には2つのアイデアがありますが、間違ったものに従うことを恐れています0 mod 2 。

2) NOT HALT でリダクション法を使用し、チューリングマシンは入力を拒否すると言うので、チューリングマシンの長さは 0 になり、上記の条件を満たします!

なにか提案を ？

Agdaにサブセットのこの定義があるとします

そして私はセットを持っています

q のすべてのサブセットが決定可能であることを証明することは可能ですか?またその理由は?

Decidable は次のように定義されています。

やあ。上記の L2 が決定可能であることを示すアルゴリズムを作成しています。そして、ヒントは次のように与えられます。

L2 が決定可能であることを示すには、与えられた TM M を最大 10 の長さのすべての入力文字列で、それぞれ 10 ステップでテストします。テストする文字列は無限にあるため、このアルゴリズムは常に終了することに注意してください。M が 10 ステップ以内の任意の入力文字列 w で停止する場合、w' を長さ 10 の w のプレフィックスとします。M は 10 ステップ以内の入力 w' でも停止するため、上記の決定アルゴリズムはそれを見つけます。

このヒントだけでは理解できません。

私が作成した上記のアルゴリズムをご覧のとおり、上記の L2 定義とヒントから適切なアルゴリズムを作成する方法がわかりません。

正しく書くための助けが必要です（アルゴリズムを書くあなたのスタイルを使用してください。主なアイデアが正しい場合、スタイルは問題ではないと思います.私が得られないのはそのアイデアです.）

お手数ですが、よろしくお願いいたします。

そのため、この問題に関するメモを確認していますが、この問題がどのように機能するのか理解できません。M があり、M はすべての非停止状態を訪問する入力を受け入れます。

この問題は決定可能であると確信しましたが、そう証明するのに苦労しています。私の答えの大まかな概要は次のとおりです。停止状態が1つしかないTM Tがあり、すべての状態を通過したい場合は、この停止状態を通過する必要があり、それらがどのように循環するかを何らかの形で示す必要があると仮定しますそのようなすべての州。

どんな助けでも有益です、ありがとう！