こんにちは私は可算性に疑問があります。特定のものが可算であるかどうかを調べる必要があるのはなぜですか。それを見つけることに使用はありますか？また、数えられないことがある場合、それを解決するチューリングマシンがないことを意味しますか？
2266 次
3 に答える
4
あなたの質問に答えることで、あなたが試験問題に答える手助けをしているのではないことを願っています。
可算性とチューリング マシンは、ほぼ同じコインの裏表です。これらは、問題が「計算可能」かどうかを判断するための補完的な方法です。計算可能性を示す他の同等の方法もあります (そろばん機械、可算関数、計算可能関数などを検索します)。定義上、チューリング マシンで解決できることを実証できれば、その問題は計算可能であると示されます。あるいは、可算無限集合からの解の全単射があることを示すことができれば、問題が計算可能であることを示すことができます。
ちなみに、可算無限集合とは「小さい」無限集合、つまり集合 ℵ₀ です。(素人の言葉で言えば、小さな無限または可算無限セットは整数のセットです。整数、奇数、または偶数は同じカーディナリティ、つまり小さな無限セットを持ちます。ℵ₀ で始まり上に行く、無限セットの無限の階層があります。 ℵ_∞ へ. ℵ₀, 整数の集合は最小の無限集合. ℵ₁ は ℵ₀ のスーパーセット. R , 実数の集合は ℵ₁ と同じカーディナリティを持ちます.) 階層があることの理解の無限大は、計算可能性を示すために何を証明する必要があるかを理解するのに役立ちます。
基本的なチューリング マシンには小さな無限のテープがあります。問題がチューリング マシンで計算できることを示すということは、その問題が小さな無限の時間と空間によって制限された解を持つことを示すことを意味します。チューリング マシンには、シンボルを保持できる無限のセルを持つテープがあります。整数のセットがどちらの方向にも無限であるように、どちらの方向にも無限のセルがあります (小さな無限)。テープに関連付けられている読み取り/書き込みヘッドは、テープ上を左または右に移動でき、移動ごとに 1 つのシンボルを読み書きできます。問題が「計算可能」であることを示すために、テープのヘッドを初期状態から最終的な停止状態または終了状態に移動させる一連の命令を示します。チューリング マシンでは問題を解決できないことを証明することは、可算無限の時間やリソースを与えるかどうかに関係なく、問題が計算可能ではないことを証明することです。ところで、時間と空間は補完的です。可算無限空間を使用して有限時間で問題を解決できる場合、または有限空間を消費して可算 (つまり、小さい) 無限時間で問題を解決できる場合は、その問題が計算可能であることを示します。
于 2012-04-02T06:36:23.153 に答える
3
ちょっとした答えを教えてあげましょう (申し訳ありませんが、計算理論は少ししか知りません)。
チューリングマシンは数え切れないほどしかありません。したがって、数え切れない問題のセットがある場合、そのセットには、それを解決するチューリング マシンが存在しない問題が少なくとも 1 つあることがわかります。
したがって、たとえば、一連の問題が
ある関数 f:N -> N に対して、与えられた n に対して f(n) を計算するプログラムを書きなさい
fそのようなプログラムが無数にあるため、そのようなプログラムを指定できないものが少なくとも 1 つあることをご存知でしょうf。
ただし、この分析が停止問題に適用できるとは思えません。なぜなら、停止問題は、「チューリング マシンのコードが与えられたとき、空白のテープが与えられたときに最終的に停止するかどうかを判断する」という 1 つの問題だけで構成されているからです。これは数え切れないほど多くの可能な入力がある問題の 1 つにすぎないため、数えるだけで解決できる可能性があるように見えます。解決できないという別の方法で議論する必要があります。
もちろん、可算性と不可算性の重要性は、この 1 つの例よりもはるかに多様です。他の人がもう少し供給してくれることを願っています。
于 2012-03-17T09:17:36.873 に答える
0
可算性は、チューリング マシンに関しては非常に重要であり、数学や科学の他の多くの場所でも重要です。A チューリングマシンは操作を順番に実行する必要があるため、各ステップにカウント番号を割り当てることができます。プロセスが永遠に続く場合、プロセスは可算無限です。
チューリング マシンが不適切な演算の例は、1 と 2 の間のすべての数の 2 乗を合計することです。この間隔内の有理数のリスト全体が、これは、すべての数字をカウント番号で 1 対 1 でマッピングできます。したがって、この数字のリストで一度に 1 つの手順を実行することは、チューリング マシンによって実行できます。ただし、この間隔の無理数では、数が多すぎるため、これを行うことができませんでした。無理数のリストを順序付けられた (可算) リストに入れることができないことは (それほど簡単ではありませんが) 示すことができます。したがって、間隔のすべての数値をリストする順序はありません。つまり、無限の時間が与えられたとしても、チューリング マシンはタスクを達成できませんでした。
于 2012-04-02T04:15:25.130 に答える