すべてのチューリングマシンのセットはカウント可能です。無限バイナリシーケンスのセットは数えられません。

Question

最終的に勉強しようとすると、カウント可能性と混乱します。

いずれのチューリングマシンも文字列として説明できます。私たちは有限の数の入力（Σ）を持っています。各長さの文字列の組み合わせを計算することができます。

256個の異なる入力シンボルがあるとします。

文字列の長さが1：256の組み合わせの場合。

文字列の長さが2の場合：256^2の組み合わせです。

文字列長がkの場合、256^kの組み合わせがあります。

これらすべての組み合わせに番号を付けます。

1、2 ... 256、^ 2 257、258 ... 256 + 256 ...

自然数は可算なので、全単射マッピングがあります。そのため、すべてのチューリングマシンのセットは数えられます。

私の質問は、すべての無限バイナリシーケンスで同じことをすることができなかった理由です。私は各長さのすべての組み合わせを見つけ、それらに番号をつけて、私は全容写像を得るでしょう。

多くの感謝！

Answer 1

カンターの対角引数について聞いているようです。一連の無限シーケンスが与えられれば、セットに含まれていないシーケンスを作成することができます。

これは、あなたが無理数を数えることができない引数と非常によく似ています。あなたは、セットが数字/文字列/ etcで構成されている場合、常にセットにない数字を作ることができます。無限の長さです。

あなたの議論の最大の欠陥は、「私は各長さのすべての組み合わせを見つける」と言うことですが、これは無限の長さの文字列を考慮すると不可能です。