問題タブ [computation-theory]

私は削減について多くのことを研究しましたが、それには悪い問題があります：私はこれをCLRSから取っています：

「...問題Aの解決を問題Bの解決に「減らす」ことにより、Bの「容易さ」を使用してAの「容易さ」を証明します。」

そして、私はこれを「クリストスH.パパディミトリオウによる計算の複雑さ」から取っています。

「...問題Aは、BがAに減少した場合、少なくとも問題Bと同じくらい困難です。」

私はこれらの2つの概念と混同しました：簡単さを使用すると、問題Xは問題Yに還元され、Yの多項式時間アルゴリズムがあり、還元プロセスが多項式時間で行われる場合、問題Xは多項式時間で解くことができ、XはYより簡単か、少なくともYより難しくはありません。

しかし、硬さを使用すると、問題Xは問題Yに還元され、YはXよりも簡単であるか、少なくともXよりも難しくはありません。

私は本当に混乱しました、助けてください。特別な感謝。

非決定性アルゴリズムの簡単な説明が必要です。非決定性アルゴリズムを並列プロセッサを搭載したコンピュータと比較できますか? 非決定性アルゴリズムについて誰か正確に説明してください

私は今、計算理論のコースを取っています。概念はよく理解できます。私は問題を解決することができます。そして、実際のアプリケーションについて講師に尋ねたところ、これらの概念はコンパイラーの設計において確実に有用であり、不可欠であるとのことでした。しかし、少なくとも有意義な調査を行うには、これらの概念をコーディングでどのように使用できるかについての説明が必要です。

たとえば、独自の grep を設計したい場合。C で文字列関数を使用します。コーディングで正規表現を使用する方法がわかりません。

同じケースがチューリングマシンにも当てはまります。

2 つの数値を追加したい場合、なぜそれらの単項概念に従う必要があるのですか。ハードウェアはそれらの概念を実装していますか?

正規表現のリスト、またはいくつかのドキュメントと調査を並べ替えることができるものを探しています。

それらの特異性/厳格さに応じて

しかし、どうですか

どちらがもう一方よりも具体的ではありませんか？

前もって感謝します

私は文脈自由文法を研究していますが、星のある矢印と星のない矢印がパートfとgで何を意味するのか興味があります。

• fはfalseです。
• gは真です。

で終わる言語の補語を見つけるのを手伝ってくれませんかabab - (a|b)*abab (over an alphabet {a,b})

補数には、abab で終わらないすべての文字列が含まれている必要があると思います。を補完するために DFA を構築した後、Rij-Algorithm でそれを試みること(a|b)*ababができますが、Automaton と Rij なしでどのように機能するかを理解するのを手伝ってください (Automaton には 5 つの状態があるため)。

わかりました、単語を で終わらせることはできませんabab。末尾の's と's の4 文字は 2 ^{4通りあります。}よし、消さなきゃいけないから組み合わせは15通り。補語が.( と を除いたすべての組み合わせの和集合) であることを意味しますか? でも最初から変わらないの？ababab(a|b)*ababab(a|b)

これを理解してください。

「Hello world tester」プログラムが決定不能な問題であることは、理論的なコンピューター サイエンスではよく知られています
。逆の問題を解決できますか:
入力と出力のセットが与えられた場合、与えられた入力と出力の間で 1 対 1 のマッピングを実現するプログラムを作成するプログラムを作成するためのアルゴリズムはありますか? 私はメタプログラミング
について知っていますが、私の質問はより理論的な興味深い一般的なケースに適用できるもの。

私はこの答えに近いと思いますが、それでも確認するために、実数の計算に取り組み、正確な結果を得ることができるチューリングマシン（少なくとも原理的には）を作成できますか？**たとえば、整数の平方根を見つけます。（その出力は実数になります）そのようなマシンを開発できないという私の論理は、実数は数え切れないほど無限であり、数え切れないほど無限の言語ではチューリングマシンを作成できないということです。

右から5番目の記号として「1」を持つ文字列を受け入れるためにDFAで必要な状態の最小数はいくつですか。文字列はアルファベット{0,1}の上に定義されます。

タイトルごとに、HTMLで（自明ではない）クワインを作成することは可能ですか？

HTMLクワインの私の定義：

自明ではないHTMLクインとは、HTMLファイル内の一部の文字列がブラウザによってプレーンテキストとしてレンダリングされることを前提として、nullではなく少なくとも1つのHTMLタグを使用するクインです。HTMLクインはq.html 、標準ブラウザによってレンダリングされたasの出力がそれ自体のコンテンツになるように定義されq.htmlます。

（私はこの定義についてのコメントを受け付けています、私は今それをちょっとハックしました）

HTMLはチューリング完全ではないため、不動点定理を適用して、それが実際に可能であることを証明することはできません。

ただし、これは必ずしもHTMLクワインが不可能であることを意味するわけではありません。それとも、HTMLクワインが不可能であることを実際に証明できますか？