問題タブ [computation-theory]

チューリングマシンの同等物のリストに関するウィキペディアの記事を見つけました。ただし、特定のマシンがチューリングマシンと同等であるかどうかを判断する方法はわかりません。

それを証明するためにチューリングマシンの定義を使用する必要がありますか？例を挙げていただけますか？

ありがとう。

私はいくつかの計算理論について（宿題ではなく）ブラッシュアップしていて、この問題に遭遇しました：

通常の言語のセットが文脈自由言語のセットの適切なサブセットであることをどのように証明できますか。

これで、言語が有限オートマトンによって受け入れられれば、その言語は規則的であることがわかりました。

また、プッシュダウン オートマトンによって受け入れられる言語は文脈自由であることも知っています。

しかし、私は解決策が何であるかわかりません。

計算理論をブラッシュアップしようとしていますが、これに対する解決策がわかりません：

NP問題の発見とα因数分解の問題の縮小の発見に関係しているのではないかと感じています。

いくつかの改訂を試みていますが、これについてはわかりません：

有限のアルファベット上のすべての言語の集合が数えられないことを証明してください。

カントール対角化法を使用する必要があると感じていますが、この問題にどのように使用するかはわかりません。

私はオートマトン理論の授業を受けており、今はポンピング補題を学んでいます。「L もその補集合も無限の正規部分集合を持たないように言語 L を設計しますか?」という演習問題があります。しかし、私は質問を理解していません。無限正部分集合とは? この要件を満たす言語を見つけるにはどうすればよいですか?

誰でもこの質問に光を当てることができますか?

ありがとう！

任意の数のテープシンボルを含むチューリングマシンMは、{0、1、B}（B =空白）の3つのテープシンボルのみを含む1つのM'でシミュレートできます。

Mは、テープシンボルが2つしかないM "、たとえば{1、B}でシミュレートできますか？

その言語では、n は力ですが、書き方がわかりませんでした。

有限状態マシンと状態マシンに違いがあるかどうかわかりませんか? 私はこれについてあまりにも難しいことを考えていますか？

アルファベット { a } を持つ言語Lの定義は、次のように与えられます。

L = {a ^nk | k > 0; n は正の整数定数です }

Lを認識するために DFA で必要な状態の数は?

私の意見では、k + 1 にする必要がありますが、よくわかりません。

これについてどうやって行くかについて私にいくつかのアイデアを教えてください

少なくとも4つの重要な（つまり、拒否されない）状態と少なくとも6つの重要な（つまり、拒否されない）遷移を持つチューリングマシンを（Sipser表記を使用して）描画します。